Тема 12. Математическая комбинаторика

Изучив данную тему, студент должен знать:

1. Правило произведения.

2. Правило суммы.

3. Факториал и его свойства.

4. Размещения.

5. Размещения с повторениями.

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

7. Перестановки с повторениями.

8. Сочетания и их свойства.

9. Сочетания с повторениями.

Уметь:

10. Вычислять по различным комбинаторным формулам.

Рассмотрим ряд примеров, иллюстрирующих применение комбинаторных формул в задачах.

1. Упростить выражение .

Было бы неправильным просто вычислить все факториалы, после чего перейти к арифметике ‑ слишком большие числа. Используем, где возможно, расчленение факториалов:

;

;

.

Следовательно, .

2. Упростить выражение .

Напомним, что ; и , тогда

.

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

Известно, что любое число может быть записано с использованием десяти цифр ‑ 0, 1, ..., 9. Так как телефонные номера обычно не начинаются с 0, то задача состоит в вычислении числа комбинаций из девяти различных цифр по 7. Очевидно, что это ‑ размещение по семи различным местам семи из девяти различных цифр, т.е.

номеров.

Даже если на проверку одного номера тратить 1 минуту, то на все
уйдет 3024 часа или 126 суток. Таким образом, следователь ‑ не прав.

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

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

способов.

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

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

способов.

6. В розыгрыше первенства по футболу среди вузов принимает участие 16 команд, при этом любые две команды играют между собой только один матч. Сколько всего календарных игр?

Данная задача ‑ о числе выборок из 16 по 2. Таким образом,

игр.

7. Изменим условия примера 3. Пусть стало известно, что в телефонном номере преступника встречаются только цифры 2, 4, 5 и 7. Насколько уменьшится перебор всех возможных номеров?

Таким образом, в семизначном телефонном номере встречаются только четыре цифры, остальные три, очевидно, повторяют какие-то из имеющихся. Следовательно, имеем задачу о размещениях из четырех цифр по семи,
т.е. с повторениями.

Решение:

(повт.) = 4⁷ =16384 номера.

Перебрать все эти номера можно примерно за 11 суток, что почти в 10 раз меньше, чем в примере 3.

8. Сколькими способами можно разложить в ряд две зеленые и четыре красные папки?

Так как названия папок не указываются, а критерием является цвет, то задача состоит в расположении шести цветных папок двух цветов. Имеем случай перестановок с повторениями. Следовательно,

способами.

9. Сколькими способами можно переставить буквы в слове «какао», чтобы получились все возможные различные наборы букв?

В заданном слове ‑ 5 букв, причем «к» и «а» повторяются по два раза, а «о» встречается один раз. Таким образом,

способов.

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

Ясно, что можно выбрать как различные виды пирожных, так и пов-торяющиеся и даже составить набор из четырех одинаковых пирожных. Так как порядок следования пирожных в наборе не имеет значения, то эта задача относится к классу сочетаний с повторениями.

Следовательно,

(повт.) способами.