Тема 1. Комбінаторика

Література : [3], гл. 6, § 6.1; [7], гл. 10, § 30; [12], розділ 2, § 2.1; [13].

При розв’язанні задач теорії ймовірностей часто доводиться підраховувати кількість усіх ймовірних способів розташування деяких елементів або здійснення деякої події. У таких випадках використовують поняття комбінаторики, основними з яких є перестановки, розміщення і комбінації (сполучення), а також комбінаторне правило множення.

Розглянемо деякі типові задачі.

Приклад 1.Скількома способами можна поставити на полку 5 різних книг ?

Розв’язання. Першою можна поставити будь-яку з 5 книг. Другою – будь-яку з 4, що залишилися, і т. д. Таким чином, кількість способів, якими можна поставити на полку 5 різних книг, дорівнює числу перестановок з 5 елементів, тобто

.

Приклад 2.Студент повинен скласти три іспити протягом семи днів (не більше, ніж один іспит у день). Скількома способами це можна зробити?

Розв’язання.Кількість способів дорівнює числу упорядкованих підмножин з трьох елементів (дні складання конкретних іспитів), що можна взяти з множини з семи елементів (дні, які відведені для складання іспитів), тобто

.

У додаток відзначимо, що у випадку, коли, припустимо, відомо, що останній іспит повинен бути складеним на сьомий день, кількість способів буде дорівнювати

.

Приклад 3.Скільки чоловік брало участь у шаховому турнірі, якщо відомо, що кожні два шахісти зустрічалися один раз, а всього було зіграно 210 партій?

Розв’язання.Кількість партій, які були зіграні, дорівнює числу невпорядкованих 2-елементних підмножин, що можна взяти з множини ізnелементів, тобто

,

де n– кількість шахістів, які брали участь у турнірі. Тоді

,,.

Оскільки , то.

Приклад 4.Скількома способами можна призначити варту з 9 солдатів, 2 сержантів та 1 офіцера, якщо в підрозділі 14 солдатів, 3 сержанти і 4 офіцери.

Розв’язання.Дев’ять солдатів можна вибрати

способами,

два сержанти

способами,

одного офіцера

способами.

Таким чином, за правилом множення варту можна призначити

способами.