Комбинаторика - знакомство

Ребята, мы переходим к изучению новой темы. На сегодняшнем уроке, мы будем изучать комбинаторные задачи. Раздел комбинаторики можно выделить как самостоятельный раздел, но он также является очень важным для изучения наших дальнейших тем математической статистики и теории вероятности.

Так что же такое комбинаторика? И какими задачами она занимается? Комбинаторика и слово комбинация очень похожи и имеют прямое отношение друг к другу. В комбинаторике изучают различные комбинации элементов множества и отношения на этих множествах. Впервые термин "комбинаторика" ввел Лейбниц, который в 1666 году опубликовал большой труд "Рассуждения о комбинаторном искусстве".

Примеры использовании комбинаторики

Давайте рассмотрим пример. Сколько чисел можно составить из цифр: 1,2,3?
Нужно найти количество комбинаций из трех чисел. Давайте найдем их. Напрямую переберем все цифры и возможные получающиеся числа. Подойдем к этой задаче осознано и последовательно составим числа от наименьшего к наибольшему.
Очевидно, что наименьшее число будет начинаться с единицы, тогда у нас два варианта: 123, 132. Теперь поставим на первое место цифру два и у нас также два варианта: 213, 231. У нас осталась цифра три: 312, 321. Мы получили шесть комбинаций: 123, 132, 213, 231, 312, 321. Метод, которым мы воспользовались, называется методом перебора, причем перебор организованный: мы брали числа не произвольно, а придумали правило, по которому будем составлять числа.

Пример. Из цифр 1,4,6 составить трехзначные числа, в которых одна цифра не может повторяться более двух раз.
а) Найти наименьшее число.
б) Найти наибольшее число.
в) Сколько чисел, начинающихся с 6, можно составить?
г) Сколько всего чисел можно составить?
Решение.
а) Чтобы получить наименьшее число, нам нужно на первое место поставить наименьшую цифру, потом на второе и третье - соответственно тоже. Наименьшим числом будет 114 так, как самая маленькая цифра у нас единица, и мы ее можем повторить два раза. А из цифр 4 и 6, которые нам надо поставить на третью позицию, очевидно, что 4 меньше 6.
б) Чтобы получить наибольшее число, нам нужно на первое место поставить наибольшую цифру, потом на второе и третье - соответственно тоже. Наибольшим числом будет 664 так, как самая большая цифра у нас 6, и мы ее можем повторить два раза. 4 больше 1, тогда на последнее место и выберем 4.
в) Назовем числа без повторяющихся цифр. Помним, что все числа должны начинаться с 6. 614 и 641 – без повторяющихся цифр. Теперь рассмотрим числа, в которых повторяется шестерка. 661, 664, 616, 646. Повторяется четверка: 644. Повторяется единица: 611. Всего у нас получилось 8 чисел.
г) Для того, чтобы подсчитать общее количество чисел, которые можно составить, применим тот же способ, что и в пункте в). На первое место поставим цифры 1 и 4, тогда у нас получится еще 16 комбинаций. Учтем, числа начинающиеся с шести, и того 24 комбинации.
Также для решения задачи под пунктом в) можно нарисовать дерево вариантов. Давайте так и поступим. Поместим цифру шесть в верхний прямоугольник, это будет первый уровень дерева. Тогда у нас существует три варианта, куда можно двигаться, соответственно записать - 66, 61 и 62. Таким образом, мы спустились вниз (на один уровень дерева). Далее для каждого из вариантов второго уровня составим возможные комбинации и запишем их в свои ячейки. На третьем уровне у нас получилось восемь ячеек, что и соответствует ответу.

Пример. В урне лежат два белых и один черный шар. На ощупь их различить невозможно. При вытаскивании белого шара его откладывают в сторону, если вытащили черный шар, то его кладут обратно. Шары вытаскивают три раза подряд.
а) Нарисовать дерево событий.
б) В скольких случаях вытащат шар одинакового цвета?
в) В скольких случаях вытащенных белых шаров будет больше?
Решение.
а) В вершине дерева обозначены шары, оставшиеся в урне. На ветвях дерева обозначены вытащенные шары. б) Как видно из рисунка три одинаковых шара можно вытащить только в одном случае, когда они все черные.
в) Три белых шара вытащить невозможно. Значит нам осталось посчитать количество комбинаций с двумя белыми шарами, нам подходят случаи когда на ветвях дерева встречаются две буквы Б. Такие комбинации: ЧББ, БЧБ, ББЧ. Получили, что всего три комбинации.
В нашем примере количество комбинаций сравнительно немного, но бывают случаи, когда комбинации исчисляются сотнями, и рисовать дерево очень проблематично. Как нам тогда поступить?

Для подсчета комбинаций существует правило умножения: Для того, чтобы найти количество возможных исходов двух независимо проведенных испытаний А и Б, нужно умножить число всех исходов испытания А на число всех исходов испытания Б.

Правила в комбинаторике

Давайте посмотрим правило умножения на примере.
Пример. Петя может доехать до школы четырьмя способами: на трамвае, на автобусе, на троллейбусе и маршрутке. Оплатить проезд можно тремя способами:

• купив билет на остановке,
• купив билет у кондуктора,
• воспользоваться проездным.

Сколько существует всего комбинаций проезда и оплаты у Пети?
Решение.
Возможностей проезда у нас - четыре, способов оплаты - три. Тогда по правилу умножения у нас $4*3=12$ комбинаций. Давайте проверим с помощью таблицы все возможные комбинации. Выбор способа оплаты и способа проезда независимы. В каждую ячейку ставим по одному из событий, получаем 12 возможных ячеек. Наш ответ совпал с тем, что получили по правилу умножения.
Выбор способа решения задачи всегда остается за вами, ребята. Но правило умножения во многом облегчает решение многих задач, так как рисование дерева событий или таблицы возможных вариантов очень неудобно при большом количестве событий.

Правило умножения приводит к важному понятию факториала. Давайте на примере разберем это понятие.
Пример. Сколько существует комбинаций из шести букв: А, Б, В, Г, Д, Е. Буквы не повторяются.
Решение.
На первое место мы можем поставить шесть букв, на второе место - уже пять, так как буквы не повторяются, на третье - соответственно четыре, на четвертое - три, на пятое - две, и на шестое - букву.
Используем правило умножения: 6*5*4*3*2*1=720.
Ответ: 720 способов расстановки букв без повторения.

Определение. Произведение подряд идущих первых n натуральных чисел обозначают n! (n факториал): $n!=1*2*…*(n-1)*n$, n факториал – состоящий из n множителей.

Заметим важное свойство факториала: $n!=(n-1)!*n$.
Данное свойство значительно упрощает решение задач, где присутствует факториал.
Например, для вычисления задач вот такого типа: $\frac{4!*10!}{8!*3!}$.
Совсем необязательно вычислять все факториалы.
Можно все переписать вот в таком виде: $\frac{3!*4*8!*9*10}{8!*3!}$.
Сократив нашу дробь, получим гораздо более простое выражение: $4*9*10=360$.

Пример.
а) Сколько существует способов развесить на указанные места на елке пять различных шаров?
б) Вове надо выполнить четыре домашних задания: по математике, физике, русскому языку и истории. Сколько существует способов очередности выполнения домашнего задания?
Решение.
а) В нашей задаче шары не повторяются. Тогда на первое место претендуют пять шаров, на второе - уже четыре, на третье - соответственно три, на четвертое - два и на последнее - один. $5*4*3*2*1=5!=120$.
б) Существует четыре варианта: с какого задания начать. Выполнив первое задание, Вове останется выбрать, что делать дальше из трех заданий, после - из двух и в конце останется только одно задание. $4*3*2*1=4!=24$.

Условия наши задачи совершенно разные, но способ решения у них один.
Давайте выведем общее правило решения таких задач: N различных предметов можно расставить, без повторения элементов, на N различных места ровно N! способами.

В математике принято называть наше утверждение, как количество перестановок из N элементов без повторений. Обозначают как: $P_{n}=n!$.

Задачи для самостоятельного решения

1. Из цифр 2,7,9 составить двухзначные числа, в которых цифры не повторяются.
а) Найти наименьшее число.
б) Найти наибольшее число.
в) Сколько чисел, начинающихся с 2, можно составить?
г) Сколько всего чисел можно составить?

2. В урне лежат два белых и два черных шара. На ощупь их различить невозможно. При вытаскивании белого шара его откладывают в сторону, если вытащили черный шар, то его кладут обратно. Шары вытаскивают четыре раза подряд.
а) Нарисовать дерево событий.
б) В скольких случаях вытащат шары одинакового цвета?
в) В скольких случаях белые шары появятся раньше?

3) Саша может выбрать обед из трех блюд: суп, плов, рис с котлетой и из пяти напитков: сок, чай, кофе, лимонад, компот.
Сколько всего комбинаций из блюд может выбрать Саша?

4. Стрелок стреляет по шести мишеням из шести орудий. В одну мишень производится только один выстрел. Выстрелив один раз из орудия, стрелок откладывает его в сторону. Сколько комбинаций выстрелов по мишеням у него имеется?