Комбинаторика – это раздел математики, посвященный задачам выбора и расположения предметов из различных множеств.
Учащиеся 8 класса знакомятся с правилом умножения, перестановками и факториалом числа, числом сочетаний.
Правило умножения
Если число предметов первого типа равно m, а число предметов второго типа равно n, то число их комбинаций равно mn.
Задача 1. Из села А в село Б ведут четыре дороги, а из села Б в село В – три дороги. Сколькими способами можно добраться из А в В через село Б?
Решение. Если из А в Б добираться по первой дороге, то продолжить путь есть три способа:
Получаем по три способа продолжить путь, начав добираться и по второй, и по третьей, и по четвёртой дороге.
Значит, всего получается 4 · 3 = 12 способов добраться из А в В.
Задача 2. Из пункта А в пункт В ведут пять дорог, а из пункта В в пункт С – шесть дорог. Сколькими способами можно добраться из А в С через В?
Решение. Из А в В можно проехать по пяти дорогам, а из В в С по шести дорогам. Значит, всего 5· 6 =30 различных способов пути из А в С.
Задача 3. На вершину холма ведут пять тропинок. Сколько существует способов подняться на холм и спуститься с него, если подниматься и спускаться по разным тропинкам?
Решение. Подняться можно по одной из пяти тропинок, а спуститься по одной из четырёх оставшихся (кроме той, по которой поднялись).
Всего 5 · 4 = 20 способов.
Задача 4. Сколько трёхзначных чисел можно составить из цифр 3, 4, 5, 8, если цифры в записи числа не повторяются?
Решение. Первой цифрой числа может быть любая из четырёх данных цифр, второй – любая из трёх других, а третьей – любая из двух оставшихся.
Всего из данных цифр можно составить 4 · 3 · 2 = 24 трёхзначных числа.
Задача 5. Сколько трёхзначных чисел можно составить из цифр 0, 1, 3, 5, если цифры в записи числа не повторяются?
Решение. Первой цифрой числа может быть любая из трёх цифр: 1, 3, 5, второй – любая из трёх других, а третьей – любая из двух оставшихся.
Всего из данных цифр можно составить 3 · 3 · 2 = 18 трёхзначных чисел.
Задача 6. Сколько различных трёхзначных чисел можно составить при помощи цифр 1, 5, 9, 4, если цифры в числе не могут повторяться и на месте десятков может быть только чётное число?
Решение. Первую цифру можно выбрать тремя способами, т.к. четвёрку брать нельзя. На втором месте может стоять только четвёрка, значит одним способом.
Третью цифру можно выбрать двумя способами, т.к. цифры в числе не повторяются.
Получается 3 · 1 · 2 = 6 различных трёхзначных чисел.
Задача 7. Сколько существует трёхзначных чисел, в записи которых нет цифры 5?
Решение. Мы можем использовать девять цифр: 0, 1, 2, 3, 4, 6, 7, 8, 9.
Первую цифру мы можем выбрать восемью способами, т.к. нельзя брать 0 и 5. Вторую цифру можем выбрать девятью способами, столькими же способами и третью цифру.
Получается 8 · 9 · 9 = 648 трёхзначных чисел.
Задача 8. Сколько четырёхзначных чисел можно составить из нечётных цифр, если цифры в записи числа не повторяются?
Решение. Всего нечётных цифр пять: 1, 3, 5, 7, 9.
Первой цифрой числа может быть любая из пяти данных цифр, второй – любая из четырёх оставшихся, третьей – любая из трёх оставшихся, а четвёртой – любая из двух оставшихся.
Получается 5 · 4 · 3 · 2 = 120 различных четырёхзначных чисел.
Задача 9. Сколько различных шифров можно набрать в автоматической камере хранения, если шифр составляется с помощью любой из 28 букв русского алфавита с последующим набором трёхзначного цифрового кода?
Решение. Первой цифрой шифра может быть любая из десяти цифр, второй – любая из десяти цифр, третьей – любая из десяти цифр, а буква может быть любая из двадцати восьми.
Получается 28 ∙ 10 · 10 · 10 = 28 000 вариантов различных шифров.
Перебор возможных вариантов
Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.
Задача 10. Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5, если цифры могут повторяться?
Решение.
11, 12, 13, 14, 15,
21, 22, 23, 24, 25,
31, 32, 33, 34, 35,
41, 42, 43, 44, 45,
51, 52, 53, 54, 55.
Задача 11. В финальном забеге на 100 м участвуют Иванов, Громов и Орлов. Назовите возможные варианты распределения призовых мест.
Решение.
Иванов |
Иванов |
Орлов |
Орлов |
Громов |
Громов |
Громов |
Орлов |
Иванов |
Громов |
Иванов |
Орлов |
Орлов |
Громов |
Громов |
Иванов |
Орлов |
Иванов |
Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода – дерево возможных вариантов.
Задача 12. Запишите все трёхзначные числа, для записи которых употребляются только цифры 1 и 3.
Решение. В записи числа на первом слева месте (в разряде сотен) может стоять цифра 1 или цифра 3. На втором месте (в разряде десятков) в каждом случае также одна из двух цифр – 1 или 3. На третьем месте (в разряде единиц) в каждом из полученных четырёх случаев также можно записать либо 1, либо 3.
Получили восемь чисел: 111, 113, 131, 133, 311, 313, 331, 333.
Задача 13. Какие трехзначные числа можно составить из цифр 0, 2, 4, если цифры могут повторяться?
Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе.
Получили 18 чисел: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.
Задача 14. Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.
Решение. Построим дерево возможных вариантов, обозначив М – математика, Р – русский язык, И – история, А – английский язык, Ф физкультура.
На рисунке перечислены все 24 возможных варианта расписания.
Перестановки, факториал
Задача 15. Семье, состоящей из бабушки, папы, мамы, дочери и сына, подарили 5 разных чашек. Сколькими способами можно разделить чашки между членами семьи?
Решение. У первого члена семьи (например, бабушки) есть пять вариантов выбора, у следующего (пусть это будет папа) остаётся четыре варианта выбора, следующий (например, мама) будет выбирать уже из трёх чашек, следующий – из двух, последний же получает одну оставшуюся чашку.
Получили, что каждому выбору чашки бабушкой соответствует четыре возможных выбора папы, т.е. всего 5 · 4 способов. После того как папа выбрал чашку, у мамы есть три варианта выбора, у дочери – два, у сына – один, т.е. всего 3 · 2 · 1 способов. Окончательно получаем, что для решения задачи надо найти произведение 5 · 4 · 3 · 2 · 1.
Заметим, что получили произведение всех натуральных чисел от 1 до 5. Такие произведения записывают короче: 5 · 4 · 3 · 2 · 1 = 5!
Итак, ответ задачи: 5! = 120, т.е. чашки между членами семьи можно распределить ста двадцатью способами.
Перестановкой множества из n элементов называется расположение элементов в определенном порядке.
Число перестановок n предметов равно n!.
n!=1 · 2· 3 · 4·…·(n -1) ·n.
Задача 16. В четверг в седьмом классе пять уроков: алгебра, физкультура, история, русский язык и география. Сколько различных вариантов расписания на четверг можно составить?
Решение. Существует пять вариантов выбора первого урока. Для каждого выбранного первого существует четыре варианта выбора второго урока. После того как первый и второй уроки уже выбраны, существует три варианта выбора для третьего урока. Для четвёртого урока – два варианта, а для пятого – один вариант.
Итак, 5! = 5 · 4 · 3 · 2 · 1 = 120, т.е. на четверг можно составить 120 различных вариантов расписания.
Задача 17. Саша, Ваня, Петя и Олегпришли к врачу. Сколькими способами они могут встать в очередь?
Решение. У первого пациента есть четыре варианта выбора, у следующего остаётся три варианта выбора и т.д.
Итак, 4! = 4 · 3 · 2 · 1 = 24, т.е. мальчики могут встать в очередь к врачу 24 способами.
Треугольник Паскаля.
Треугольник Паскаля – это бесконечная числовая таблица «треугольной формы», в которой по боковым сторонам стоят единицы и всякое число, кроме этих боковых единиц, получается как сумма двух предшествующих чисел.
Треугольник Паскаля в прямоугольной форме.
1
11
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Паскаль подробно исследовал свойства «треугольника».
Вот некоторые из них:
1) На главной нисходящей диагонали и на первой вертикали стоят единицы.
2) На каждой из параллельныхглавной нисходящей диагонали располагается та же последовательность чисел, что и по соответствующей вертикали.
3) Каждое число равно сумме чисел предшествующего горизонтального ряда, стоящего над ним и предшествующего ему.
Существует связь между рядом Фебоначи и «треугольником Паскаля». Если записать для каждой восходящей диагонали сумму всех стоящих на ней чисел, получим: 1 , 1, 2 , 3 , 5 , 8, 13, … - числа Фебоначи.
При помощи «треугольника Паскаля» можно находить биномиальные коэффициенты. Возьмем бином (a+b) и будем возводить его в 0, 1, 2, 3, и т.д. степени.
Строки коэффициентов разложения совпадают с соответствующими строками «треугольника Паскаля». Таким способом можно возвести бином в произвольную натуральную степень n.
Число сочетаний.
Пусть дано множество из n элементов.
Сочетанием из n элементов по k называется любое подмножество, содержащее k элементов, взятых из данных n элементов без учета порядка выбора элементов, обозначается 
.
Свойства числа сочетаний:
Число различных сочетаний из n элементов по k можно найти по формуле:
Задача 18. Из группы в 25 человек нужно выделить 3 человека на дежурство. Сколькими различными способами это можно сделать?
Решение. Число всех элементов множества равно 25. Выделенные 3 человека дежурных образуют трехэлементное подмножество из общего числа в 25 элементов (n = 25, k = 3). Поэтому, по определению имеем сочетание из 25 элементов по 3.
Задача 19. В урне находятся 10 белых, 15 черных, 20 красных шаров. Сколькими различными способами можно вынуть 9 шаров, среди которых 2 белых, 3 черных и 4 красных шара?
Решение. Чтобы получить 9 шаров, из которых 2 белых, 3 черных и 4 красных, надо последовательно выполнить три действия:
- взять 2 белых шара из общего числа 10 белых шаров,
- взять 3 черных шара из общего числа 15 черных шаров,
- взять 4 красных шара из общего числа 20 красных шаров.
Число способов:
Задача 20. В коробке находятся 50 деталей, из которых 10 бракованных. Найти число различных способов взять ровно пять деталей, среди которых три бракованных.
Решение. Чтобы получить множество из пяти деталей, содержащих три бракованных, нужно последовательно совершить два действия: взять три бракованные изделия из общего числа 10 бракованных деталей, взять две доброкачественные детали из 40 доброкачественных деталей.
По правилу умножения оба действия можно совершить:
способами.
Комбинаторика в вероятностных задачах.
Задача 21. На стеллаже в случайном порядке расставлены десять учебников по экономике и пять – по математике. Миша наудачу берет три учебника. Найти вероятность того, что хотя бы один из взятых учебников будет по математике.
Решение. Рассмотрим событие – ни один из взятых учебников не будет по математике.
- вероятность 
.
- вероятность того, что хотя бы один из взятых учебников будет по математике.
Задача 22. Из коробки, в которой лежат пять пирожных «эклер» и семь — «наполеон», достали пять пирожных. Найти вероятность того, что среди них два «эклера» и три «наполеона».
Решение. Всего пирожных 5+7=12. Количество возможных исходов опыта представляет собой число сочетаний из 12 по 5:
Число благоприятных исходов является произведением количества способов, которыми можно выбрать два «эклера» из пяти имеющихся, т.е. 
, и числа наборов по три «наполеона» изсеми, т.е. 
.
Итак, 
Следовательно, вероятность равна 