Комбинаторика. Факториал.

Актуализация опорных знаний.

Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из раздела множеств. Типичной задачей комбинаторики является задача перечисления комбинаций, составленных из нескольких предметов.

3.Решить задачу

В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется

выделить четырех мальчиков и трех девочек. Сколькими способами это

можно сделать?

№ 744

Будем рассматривать сборники как одну книгу, тогда на полке будет стоять

не 12 книг, 8 книг

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

Решение: Будем искать решение с помощью дерева возможных вариантов.

Ответ: 6 комбинаций.

Пример основан на общем правиле умножения:

Пусть имеется n элементов и требуется выбрать из них один за другим к элементов. Если первый элемент m₁выбрать n₁ способами, после чего второй элемент m₂ выбрать n₂ способами из оставшихся, затем третий элемент m₃ выбрать n₃ способами из оставшихся и т.д., то число способов могут быть выбраны все к элементов, равно произведению

Применим это правило к задаче.

Выбор верхней полосы - из 3-х цветов, т.е. n₁₌3; средняя полоса – из 2-х цветов, т.е.n₂=2; нижняя полоса – из 1-го цвета, т.е. n₃=1.

В этой задаче даны 3 объекта, нужно составить из них все возможные комбинации, переставляя их между собой. Такие комбинации называются перестановками из n элементов.

Итак, перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке (т.е. перестановки отличаются друг от друга только порядком расположения элементов). Для 3-х элементов (n=3) мы получили 6 перестановок, т.е.

А если объектов 4? (n=4). То

А если объектов 5? (n=5). То 5·

А если n? То n·(n-1)·(n-2)·…·3·2·1.

Это произведение выражает количество перестановок из nэлементов и обозначают P_n.

P_n=1·2·3·(n-2)·(n-1)· n.

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

а) 4! = 1*2*3*4 = 24;
б) 5! = 1*2*3*4*5* = 120;
в) 4! + 5! = 1*2*3*4 + 1*2*3*4*5 = 24+120 = 144;
г) 5*4! =5* 1*2*3*4 = 5! = 120;

д) 4! * 5! = 1*2*3*4 *1*2*3*4*5 = 24 * 120 = 2880;

е);

з)

и) к).

Принято считать: 1!=1, 0!=1.

Факториалы растут удивительно быстро. Вы можете понаблюдать за их изменением, рассмотрев таблицу в учебнике, в которой приведены факториалы чисел от 1 до 10:

А значение выражения 15!, которого нет в таблице, превосходит 10¹⁵, а именно 15!=1 307 674 368 000. Может быть, именно из-за быстрого роста факториалов восхищенный изобретатель этого выражения использовал восклицательный знак.

Разберём решение следующих задач.

1. Пример 1. В расписании 7 класса на четверг должно быть 6 предметов: русский язык, литература, алгебра, география, физика, физкультура. Сколькими способами можно составить расписание на этот день?

Решение. Число способов, которыми можно составить расписание, равно числу перестановок из шести элементов: P₆=6!=1*2*3*4*5*6=720.

2. Пример 2. Сколькими способами можно составить расписание из тех же 6 предметов, если требуется, чтобы урок физкультуры был последним?

Решение. У урока физкультуры фиксированное место, поэтому расписания отличаются порядком остальных 5 предметов. Значит, число таких расписаний равно числу перестановок из 5 элементов: P₅=5!= 120.

3. Пример 3. Сколькими способами из тех же 6 предметов можно составить такое расписание, в котором русский язык и литература стоят рядом?

Решение. Будем рассматривать русский язык и литературу как один предмет, тогда всего предметов будет пять. Число способов, которыми можно составить расписание из 5 предметов, равно P₅=5!. Но в каждой из этих перестановок русский язык и литература могут меняться местами. Поэтому искомое число расписаний вдвое больше. Оно равно 5!*2=240.

ПРИМЕРЫДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:

Пример 1. Сколькими способами можно расставить 8 участниц финального забега на 8 беговых дорожках?

Пример 2. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6?

Пример 3. Имеется девять различных книг, четыре из которых – учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

Пример 4. Вычислить. а) ; б) ; в) ; г) ;

д) ; е) ж) ;

3.Решить задачу

В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется

выделить четырех мальчиков и трех девочек. Сколькими способами это

можно сделать?