Цель: Рассмотреть основные понятия комбинаторики.

Ход уроков

I. Сообщение темы и цели уроков

II. Повторение и закрепление пройденного материала

1. Ответы на вопросы по домашнему заданию (разбор нерешенных задач).

2. Контроль усвоения материала (письменный опрос).

Вариант 1

1. Достоверное событие и его вероятность.

2. Найти вероятность того, что на игральной кости выпадет четное число очков.

3. Найти вероятность того, что при подбрасывании двух костей

суммарное число очков окажется равным 8.

Вариант 2

1. Невозможное событие и его вероятность.

2. Найти вероятность того, что на игральной кости выпадет нечетное число очков.

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

III. Изучение нового материала

При рассмотрении простейших вероятностных задач нам приходилось подсчитывать число различных исходов (комбинаций). Для небольшого числа элементов такие вычисления сделать несложно. В большинстве случаев такая задача представляет значительную сложность. Комбинаторикой Называют область математики, которая изучает вопросы о числе различных комбинаций (удовлетворяющих тем или иным условиям), которые можно составить из данных элементов. Первоначально комбинаторика (и теория вероятностей) возникла в XVI в. в связи с распространением различных азартных игр. В настоящее время комбинаторика используется в теории информации (кодировка и декодировка), линейном программировании (составление расписаний уроков, грузоперевозок) и т. д.

Сначала рассмотрим некоторые задачи комбинаторики.

Пример 1

Сколько существует двузначных чисел?

При образовании чисел используются десять цифр: 0, I, 2, ..., 9. Так как число двузначное, то число десятков может принимать одно из девяти значений: 1,2,3, ..., 9. Число единиц принимает те же значения, и еще 0 (10 вариантов).


204

Глава 9. Элементы Математической Статистики


Если цифра десятков 1, то цифра единиц может быть любой из десяти: 0, 1,2, ..., 9. Если цифра десятков 2, то цифра единиц вновь может быть любой из десяти: 0, 1, 2, ..., 9, и т. д. Тогда получаем, что возможно 9 • 10 = 90 вариантов (чисел). Разумеется, их легко выписать: 10, 11, 12, ..., 99.

Пример 2

Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Очевидно, что на первом (соответственно, и на последнем) месте может стоять любая цифра (кроме нуля) - 9 вариантов. На втором (соответственно и на предпоследнем) месте может стоять любая цифра - 10 вариантов. На третьем месте (в середине) также может стоять любая цифра - 10 вариантов. Тогда получаем, что возможно 9 • 10 • 10 = 900 вариантов (чисел).

Из рассмотренных примеров можно сформулировать Комбинаторное правило умножения. Пусть имеется П Элементов, и надо выбрать из них один за другим К Элементов. Если первый элемент можно выбрать Щ Способами, после чего второй элемент можно выбрать и2 способами из оставшихся, затем третий элемент можно выбрать и3 способами из оставшихся и т. д., то число способов, которыми могут быть выбраны все К Элементов, равно произведению Щ-пг'Щ - ... • Щ.

Пример 3

В спортивных соревнованиях участвуют 10 команд. Сколькими способами могут быть распределены золотая, серебряная и бронзовые медали, если любая команда может получить только одну медаль?

Начнем распределять медали с наименее ценной. Бронзовую медаль может получить одна из 10 команд (10 вариантов). После этого серебряную медаль получит одна из оставшихся 9 команд (9 вариантов). Наконец, золотую медаль получает одна из оставшихся 8 команд (8 вариантов). Следовательно, общее число способов, которыми могут быть распределены золотая, серебряная и бронзовая медали, равно 10 • 9 * 8 = 720.

Пример 4

В 9 классе изучается 10 предметов. Во вторник должны быть проведены 6 различных уроков. Сколькими способами можно составить расписание занятий на вторник?

По аналогии с примером 3 на первом уроке изучается любой из 10 предметов, на втором уроке - любой из оставшихся 9 предметов, на третьем уроке - любой из оставшихся 8 предметов и т. д. Таким образом, расписание можно составить 10-9*8-7-6-5=151 200 способами.


Перестановки

Введем некоторые необходимые понятия.

Соединением Из П Элементов по К Назовем выборку К Элементов из П Различных элементов (к < п).

Пример 5

Пусть даны три различных элемента (п = 3): А, Ъ И С. Перечислим соединения из трех элементов по одному (к= 1): А, Ь, С;

Соединения из трех элементов по два (к = 2): Ab, Ьа, ас, са, Be, Cb;

Соединения из трех элементов по три (к = 3): Abc, Acb, Bac, Bca, Cab, Cba.

В зависимости от того, имеет ли значение порядок элементов или нет, а также от того, входят ли в соединение все П Элементов или только К (при условии К < п), Различают три вида соединений: Перестановки, размещения, сочетания. Комбинаторика изучает Число Таких Соединений (но не сами соединения).

Сначала рассмотрим простейший вид соединений - Перестановки. Соединения, каждое из которых содержит П Различных элементов, взятых в определенном порядке, называются Перестановками Из П Элементов. Другими словами, имеется П Позиций (мест), которые надо заполнить П Различными элементами:

П Мест Пример 6

Рассмотрим перестановки из трех элементов: А, Ь, с.

11еобходимо расположить на три позиции три элемента.

Если на первую позицию поставить элемент А, То возможны перестановки: Abc, Acb.

Если на первую позицию поставить элемент Ь, То возможны перестановки: Bac, Bca.

Если на первую позицию поставить элемент С, То возможны перестановки: Cab, Cba.

Видно, что число перестановок из трех элементов равно 6.

Вообще, Число перестановок Из П Элементов обозначают символом Рп (читается: Р Из П). В данном примере />3 = 6.

Выведем формулу Числа Рп Перестановок Из П Элементов. Используем комбинаторное правило умножения. На первую позицию можно поместить любой из П Элементов, на вторую позицию - любой из оставшихся (п - 1) элементов, на третью позицию - любой из оставшихся (п - 2) Элементов и т. д. В результате получим: Рп =w(w-l)(/7-2)-...-3-2-1. Расположим множители в порядке возрастания. Имеем: Р = 1-2-3-... (w —2)(П — \)п.


206

Глава 9. Элементы Математической Статистики


Для произведения первых П Натуральных чисел используют символ П\ (читается: П Факториал), т. е. П\ = 1 • 2 3-...*(/? - 2)(п - ])п. При этом 1! - 1 (и 0! = 1). Тогда число всевозможных перестановок из П Элементов вычисляется по формуле Р„ — И!.

Пример 7

Вычислим:

А)/э3=:3!^1-2-3=6 (см. пример 6);

^ 9! 1-2-....7-8-9 71-8-9 8-9 Л Л „

Б)------- =-------------------- =----------- =------ = 4-9 = 36;

2!7! 1-2-7! 1-2-7! 2

5! (от + 1)! 3!-4-5-(/w + l)! 4-5-(/я + 1)! Л е „л

В)------------------------------ =--------------------------- =------------------ = 4-5 = 20

Aw(/w + 1) (w-1)! -3! (/w-l)!w(w + l)-3! (w + 1)!

(где Me N).

Пример 8

D /F!-(/I-L)! 1 ,

Решим уравнение —---------- — = — (где «е TV ).

(/7 + 1)! 6

Упростим левую часть уравнения, пользуясь определением факто-

N(N-\)L-(N-\)\ 1 (я-1)!(#?-1) 1 /?-1 1

Риала: ------------------------ = —, или --------------------- =—, или ------------- = —,

(я-1)!-я(и + 1) 6 (я-1)!-л(я+1) 6 л(#? + 1) 6

Или 0 = /Г - 5и + 6. Корни этого квадратного уравнения П = 2 И П = 3 действительно являются натуральными числами и решениями данного уравнения.

Пример 9

Сколькими способами можно расставить на полке семь различных книг?

Число таких способов равно числу перестановок из семи элементов, т. е. Р7 = 7! = 1 -2-3-...- 7 = 5040.

Пример 10

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

Так как справочники должны стоять рядом, то будем рассматривать их как одну книгу. Тогда на полке надо расставить 10 - 3 + 1 =8 книг. Это можно сделать Р8 способами. Д1Я каждой из полученных комбинаций можно сделать Р$ Перестановок справочников. Поэтому число способов расположения книг на полке равно произведению: Р8*Р3 = 8! -31=40 320-6 = 241920.