Розділ 2. Елементи комбінаторики.

2.1. Місце комбінаторики в математиці. Правила суми та добутку.

Комбінаторика або комбінаторний аналіз  розділ дискретної математики, що вивчає комбінації і перестановку елементів, взаємне розташування частин скінченних множин предметів довільного походження, а також нескінченних множин, які задовольняють деякі умови підпорядкованості. Комбінаторні методи застосовуються в багатьох розділах математики та суміжних з нею наук, зокрема в теорії імовірностей, випадкових процесах, статистиці, математичному програмуванні тощо. Розглядаються задачі, в яких доводиться обирати ті чи інші предмети, розташувати їх у певному порядку і знаходити серед різноманітних комбінацій найкращі. Комбінаторика тісно зв’язана з теоріями чисел, графів, скінченних автоматів. Її досягнення використовуються під час планування та аналізу наукових експериментів, у лінійному та динамічному програмуванні, у математичній економіці, у системах проектування та керування, у комп’ютерних науках та багатьох інших галузях науки і техніки.

Виділяють такі основні задачі комбінаторного аналізу:

1) Задачі на перелічення. В задачах такого типу необхідно визначити кількість розміщень елементів скінченої множини, що задовольняють певні умови. Для розв’язку задач перелічення розроблено різноманітні методи, серед яких слід визначити метод продуктивних функцій.

2) Задачі про існування і побудову. В задачах такого типу розглядається питання: чи має місце визначена конфігурація частин скінченної множини з деякими властивостями; якщо така конфігурація існує, то як її побудувати. При цьому важливу роль відіграють чисельні та алгебраїчні методи.

3) Задачі про вибір. В задачах такого типу досліджують умови, за яких можна здійснити вибір підмножини або деякої сукупності частин множин так, щоб задовольнити певні вимоги. Для розв’язку таких задач крім комбінаторних методів широко використовують алгебраїчний апарат.

У комбінаториці виділяють два основних правила  правило суми та правило добутку. Наведемо комбінаторне формулювання цих правил.

Правило суми. Нехай предмет можна обрати способами, предмет  способами,...,предмет  способами. Тоді вибір предмета , або ,..., або може бути зроблений способами. (тут сполучник „або” вживається у розділовому вмісті, тобто вибір предмету виключає вибір будь-якого іншого предмету).

Правило добутку. Нехай треба впорядковано обрати предметів. Якщо предмет можна вибрати способами, предмет після кожного вибору предмета можна обрати способами, предмет після кожного вибору предметів ,  способами,..., предмет після кожного вибору предметів , ,...,  способами, то вибір упорядкованої множини предметів у вказаному порядку можна здійснити способами. Проілюструємо дію цих правил на наступному прикладі.

Приклад 2.1. Із пункту А в пункт Б можна доїхати на протязі доби 7 способами, із пункту А в пункт В  2 способами, а з пункту В до пункту Б  5 способами (при будь-якому способі прибуття до В із А). Тоді з А до Б можна доїхати або без пересадки, або з пересадкою у В. З пересадкою кількість варіантів . Загальна кількість варіантів . ■

Зауваження. У теорії множин існують твердження, що є аналогічними до правил суми та добутку. Так правилу суми відповідає таке твердження: нехай  скінченна множина, у якої для будь-яких ( ). Тоді . Правилу добутку відповідає наступне твердження: нехай  скінченні множини, а  їх декартовий добуток. Тоді .