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

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

Пример. Из цифр 1,4,6 составить трехзначные числа, в которых одна цифра не может повторяться более двух раз. а) Найти наименьшее число. б) Найти наибольшее число. в) Сколько чисел, начинающихся с 6, можно составить? г) Сколько всего чисел можно составить. Решение. а) Чтобы получить наименьшее число, нам нужно на первое место поставить наименьшую цифру, потом на второе и третье соответственно тоже. Наименьшим числом будет 114, так как самая маленькая цифра у нас единица, и мы ее можем повторить два раза. А из цифр четыре и шесть, которые нам надо поставить на третью позицию, очевидно, что 4 меньше. б) Чтобы получить наибольшее число, нам нужно на первое место поставить наибольшую цифру, потом на второе и третье соответственно тоже. Наибольшим числом будет 664, так как самая большая цифра у нас шесть, и мы ее можем повторить два раза. Четыре больше одного, тогда на последнее место и выберем четыре.

в) Назовем числа без повторяющихся цифр. Помним, что все числа должны начинаться с шести. 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 Данное свойство значительно упрощает решение задач, где присутствует факториал. Например, для вычисления задач вот такого типа: Совсем необязательно вычислять все факториалы. Можно все переписать вот в таком виде: Сократив нашу дробь, получим гораздо более простое выражение: 4·9·10=360.

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

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

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