Учебное пособие: Елементи комбінаторики. Початки теорії ймовірностей
ЕЛЕМЕНТИ КОМБІНАТОРИКИ
§ 1. Основні принципи комбінаторики
Досить поширеними є задачі, в яких треба знайти або число можливих розміщень предметів, або число способів, якими можна здійснити деякий вибір, тощо. Такі задачі називають комбінаторними, а галузь математики, яка вивчає теорію скінченних множин, комбінаторикою. Найпростіші задачі комбінаторики вимагають підрахунку числа підмножин заданої множини. Основними принципами (правилами) комбінаторики є принцип суми і принцип добутку.
Принцип суми. Якщо множина A містить п елементів, а множина В -т елементів і А ∩ В = Ø, то множина AUВ містить п + т елементів.
Справді, елементи множини А занумеруємо від 1 до п. Серед них немає елементів з множини В, оскільки А ∩ В = 0. Отже, коли ми переходимо до підрахунку елементів, що належать множині В, то починаємо з номера п +1. Далі буде номер п + 2, п + 3 , ..., п + т, оскільки в множині В за умовою т елементів. Цим усі елементи множини AUВ буде вичерпано, вони дістануть номери від 1 до п + т.
Правило суми можна сформулювати ще й так: якщо якийсь вибір А можна здійснити п способами, а другий вибір В можна здійснити т способами, то вибір А або В можна здійснити п + т способами.
Принцип суми за індукцією поширюється на к множин.
Принцип добутку. Нехай маємо дві множини:
А={a1 ,а2 , ..., an }, В={b1 b2 , ..., bn }.
Тоді множина всіх можливих пар
С={(аi , bi )ا i=1, 2, ..., п; j = 1, 2, ..., m} містить п-т елементів.
Розіб'ємо множину С на множини
С={(а1 , b1 ), (а1 , b2 ), …, (а1 , bm ) }
С={(а2 , b1 ), (а2 , b2 ), …, (а2 , bm ) }
…………………………………
С={(аn , b1 ), (аn , b2 ), …, (аn , bm ) }
Неважко помітити, що множини С1 , С2 , ..., Сn , попарно не перетинаються і C = Cl UC2 U … UCn . Оскільки кожна з підмножин С1 , С2 , ..., Сn ,містить т елементів, то за принципом суми число елементів в об'єднанні їх дорівнює п•т.
Правило добутку можна сформулювати ще й так: якщо якийсь вибір А можна здійснити п різними способами, а для кожного з цих способів деякий другий вибір В можна здійснити т способами, то вибір А і В у вказаному порядку можна здійснити п • т способами.
Приклад 1. З міста А у місто Б веде 6 шляхів, а з міста Б у місто В 4 шляхи (рис. 298). Скількома шляхами можна проїхати з містам у місто В1 Вибравши один із шести шляхів з міста А у місто Б, далі можемо вибрати шлях від Б до В чотирма способами. Тому на підставі правила добутку дістанемо 6 • 4 = 24.
Приклад 2. До міста А, Б і В додамо ще одне місто Г і кілька нових шляхів (рис. 299). Скількома маршрутами тепер можна дістатися з міста А у місто В?
Розглянемо два випадки: шлях проходить через місто Б або через місто Г. Для кожного з цих випадків за правилом добутку неважко під-| рахувати кількість маршрутів (для першого - 24, для другого - 6). За правилом суми маємо остаточно: 24 + 6 = 30. Отже, загальна кількість маршрутів 30.
Приклад 3. У крамниці продають 5 склянок, 3 блюдця і 4 ложки. Скількома способами можна купити два предмети з різними назвами?
Можливими є три випадки: перший - купують склянку з блюдцем, другий - склянку з ложкою, третій - блюдце і ложку. У кожному з цих випадків за правилом добутку неважко підрахувати кількість можливих варіантів: 15, 20 і 12. За правилом суми маємо остаточно: 15 + 20 + 12 = 47.
Сформулюємо тепер принцип (правило) добутку у загальному вигляді.
Нехай треба виконати одну за одною kдій. Якщо першу дію можна виконати n, способами, другу- п2 способами,..., k-ту- пk способами, то всі kдій разом можуть бути виконані n способами, де п =п2 •п2 •...• пk .
§ 2. Перестановки
Нехай треба підрахувати число способів, за якими можна розмістити в ряд nпредметів. Якщо дані предмети розглядати як елементи множини то кожне розміщення є скінченною множиною, елементи якої записано у певному порядку.
Скінченні множини, для яких істотним є порядок елементів, називаються впорядкованими. Вказати порядок розміщення елементів у скінченній множині з п елементів означає поставити у відповідність кожному елементу даної множини певне натуральне число від 1 до п .
--> ЧИТАТЬ ПОЛНОСТЬЮ <--