Комбінаторика

Комбінато́рика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай, скінченної множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.

Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття.

Комбінаторика пов'язана з багатьма іншими розділами математики.

Термін «комбінаторика» ввів Ляйбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».

Іноді під комбінаторикою розуміють ширший розділ дискретної математики, що включає теорію графів.

Основні положення

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

З комбінаторикою мають справу хіміки при вивченні різних можливих типів зв'язків атомів у молекулах; біологи, наприклад, у процесі знаходження послідовностей амінокислот у білкових сполуках; кібернетики при розв'язанні задач кодування й побудові обчислювальних пристроїв, математики — при розв'язанні багатьох різних задач, особливо в теорії ймовірності. Також комбінаторику використовують у своїх моделях фізики, архітектори, економісти й представники багатьох інших наук.

Комбінаторні задачі

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

Після розв'язання першої задачі комбінаторики розв'язується не менш важлива друга — задача переліку комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами?

Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується третя задача комбінаторики — це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу 30 студентів на 30 місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх комбінаторних конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість.

Четверта і остання задача комбінаторики — це задача про пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до оптимуму. Це на сьогодні досить нелегка для розв'язання загальна задача. Вона містить задачі комбінаторної оптимізації, наприклад, задачу комівояжера, яка на сьогодні ще не має остаточного розв'язання.

Правило суми

В основі розв'язання багатьох задач комбінаторики лежать два простих правила — правило суми та правило добутку.

Правило суми стверджує, що якщо є можливість вибрати елемент з деякої множини елементів А ${\displaystyle n}$ способами, а елемент з множини В, яка не має спільних елементів з множиною А, — ${\displaystyle k}$ способами, то вибрати елемент множини А або елемент множини В можна ${\displaystyle n+k}$ способами.

Це правило зручно продемонструвати з допомогою такої моделі. Якщо маємо дві урни і в одній з них знаходиться ${\displaystyle n}$ куль, а в іншій ${\displaystyle k}$, то кількість способів, якими можна буде вийняти кулю з тієї чи іншої урни, дорівнюватиме ${\displaystyle n+k}$. Дійсно, з першої урни кулю можна вийняти ${\displaystyle n}$ способами, але якщо з першої урни кулю не виймати, то тоді з другої урни її можна вийняти ${\displaystyle k}$ способами. Тому загальна кількість способів, якими можна вийняти одну кулю з двох урн, буде дорівнювати ${\displaystyle n+k}$.

У загальному випадку правило суми може бути сформульоване таким чином.

Якщо треба виконати якусь дію n₁ , n₂, … або n_k способами, то кількість можливих способів реалізації цієї дії буде дорівнювати

N = n₁ + n₂ + … + n_k.

Особливістю цього правила є те, що воно використовує сполучник або, який протиставляє різні дії одна одній.

Приклад 1. На денне чергування в студентському гуртожитку може піти або студент з кімнати 1, де проживають три студенти, або студент з кімнати 2, де проживають чотири студенти. Скількома способами можна вибрати одного студента на денне чергування в гуртожитку?

Розв'язання. Загальна кількість способів, якими можна вибрати одного студента або з кімнати 1 або з кімнати 2 на денне чергування, згідно з правилом суми буде 3+4=7.

Правило добутку

Правило добутку використовується тоді, коли кожний елемент множини А може бути вибраний разом з елементом множини В. Відповідно до кожного способу вибору елемента множини А буде зіставлятися ${\displaystyle k}$ способів вибору елемента множини В. Тоді загальна кількість способів сумісного вибору елементів множини А з елементами множини В, очевидно, дорівнюватиме ${\displaystyle n\cdot k}$.

Модель урн можна застосувати і для ілюстрації правила добутку. У цьому випадку розглядаються дві урни, у першій з яких знаходиться ${\displaystyle n}$ куль, а в другій ${\displaystyle k}$. Будемо вважати, що будь-якій кулі першої урни може відповідати будь-яка куля з другої урни. А оскільки в першій урні знаходиться ${\displaystyle n}$ куль, то й кількість способів вибору куль з першої урни разом з різними кулями з другої урни буде дорівнювати ${\displaystyle n\cdot k}$.

У загальному вигляді правило Добутку буде мати такий вигляд.

Якщо треба виконати якусь дію, що може бути виконана к сумісними діями, перша з яких може бути виконана n₁ способами, друга — n₂ і т. д. до к-ї дії, яку можна виконати n_k способами, то основна дія може бути виконана М способами, де

М = n₁ • n₂ • … • n_k.

У цьому правилі важливу роль відіграє сполучник і, який об'єднує різні дії в одну.

Приклад 2. На денне чергування в студентському гуртожитку вибирається два студента — один студент із трьох, що проживають у кімнаті 1, і один студент із чотирьох, які проживають у кімнаті 2. Скільки існує можливих способів формування різних пар з двох студентів для чергування?

Розв'язання. Кількість способів чергувань двох студентів з різних кімнат відповідно до правила добутку буде 3*4=12.

Історичний нарис

Базові поняття комбінаторики і розраховані результати з'явилися ще в стародавньому світі. В 6-му столітті до н. е., індійській лікар Сушрута в праці Сушрута Самхіта наводить, що із 6-ти різних смаків можна утворити 63 різні комбінації, якщо спочатку взяти по одному, потім поєднати по два, і т. д., таким чином знайшов всі 2⁶ − 1 можливих комбінацій. Грецький історіограф Плутарх обговорює дискусію між Хрісіппом (3-тє століття до н. е.) і Гіппархом (2-ге століття до н. е.) досить делікатної задачі нумерації, згодом було показано що вона тісно пов'язана із числами редера-Гіппарха^[en][1][2]. У своїй праці Остомахіон^[en] Архімед (3-тє століття до н. е.) розглядає головоломку на замощення^[en].

Джироламо Кардано написав математичне дослідження гральних кубиків, опубліковане посмертно. Теорією цієї гри займалися також Тарталья і Галілей. В історію зароджуваної теорії ймовірностей увійшло листування запеклого гравця Шевальє де Мере з П'єром Ферма і Блезем Паскалем, де було порушено кілька тонких комбінаторних питань. Крім азартних ігор, комбінаторні методи застосовувалися (і продовжують застосовуватися) в криптографії — як для розробки шифрів, так і для їх зламу.

Трикутник Паскаля

Блез Паскаль багато займався біноміальними коефіцієнтами і відкрив простий спосіб їх обчислення: «трикутник Паскаля». Хоча цей спосіб був уже відомим на Сході (приблизно з X століття), Паскаль, на відміну від попередників, суворо виклав і довів властивості цього трикутника. Поряд з Лейбницем, він вважається основоположником сучасної комбінаторики. Сам термін «комбінаторика» придумав Лейбніц, який 1666 року (йому було тоді 20 років) опублікував книгу «Міркування про комбінаторне мистецтво». Щоправда, термін «комбінаторика» Лейбніц розумів надмірно широко, включаючи до нього всю скінченну математику і навіть логіку^[3]. Учень Лейбніца Якоб Бернуллі, один із засновників теорії ймовірностей, виклав у своїй книзі «Мистецтво припущень» (1713 року) безліч відомостей із комбінаторики.

У цей же період формується термінологія нової науки. Термін «комбінація» (англ. combination) вперше зустрічається у Паскаля (1653 року, опубліковано 1665 року). Термін «перестановка» (англ. permutation) вжив у зазначеній книзі Якоб Бернуллі (хоча епізодично він зустрічався і раніше). Бернуллі використовував і термін «розміщення» (англ. arrangement).

Після появи математичного аналізу було виявлено тісний зв'язок комбінаторних і ряду аналітичних задач. Абрахам де Муавр і Джеймс Стірлінг знайшли формули для апроксимації факторіалу^[4].

Остаточно комбінаторика як самостійний розділ математики оформилася в працях Ейлера. Він детально розглянув, наприклад, такі проблеми:

• Задача про хід коня
• Задача семи мостів Кеніґсберґа, з якої почалася теорія графів
• Побудова греко-латинських квадратів^[en]
• Узагальнені перестановки

Крім перестановок і поєднань, Ейлер вивчав розбиття, а також поєднання і розміщення з умовами.

Див. також

• Дискретна математика
• Алгебрична комбінаторика
• Теорема Ділуорса
• Бієктивне доведення

Література

Українською

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)
• Комбінаторика: Навч. посіб. для студ. вищ. навч. закл. / В. М. Бушмакін, В. К. Гануліч, А. З. Мохонько, С. І. Томецька, Н. М. Тимошенко; Нац. ун-т «Львів. політехніка». — Л., 2002. — 195 c. — (Сер. «Математика для інженерів»; № 8). — Бібліогр.: 16 назв.
• Л.Є. Базилевич. Дискретна математика у прикладах і задачах : теорія множин, математична логіка, комбінаторика, теорія графів. — Математичний практикум. — Львів, 2013. — 486 с. — ISBN 9789662645095. (укр.)
• Л.В. Павлова, Р.Л. Дітчук. Елементи комбінаторики і стохастики : навчально-методичний посібник. — Підручники і посібники. — Тернопіль, 2005. — 159 с. — ISBN 9660702396. (укр.)

Іншими мовами

• Chen, Chuan-Chong; Koh, Khee-Meng (1992). Principles and Techniques in Combinatorics. Singapore: World Scientific Publishing Company. с. 312. ISBN 978-9810211394. (англ.)
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001). A course in combinatorics (вид. Second). Cambridge, UK: Cambridge University Press. с. 620. ISBN 978-0521006019. (англ.)
• Grimaldi, Ralph (1998). Discrete and Combinatorial Mathematics: An Applied Introduction (вид. Fourth). Addison Wesley Publishing Company. с. 896. ISBN 978-0201199123. (англ.)
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (вид. Second). Reading, MA: Addison-Wesley Professional. с. xiv+657. ISBN 0-201-55802-5. (англ.)
• Anderson, James A. (2000). Discrete Mathematics with Combinatorics (вид. First). Prentice Hall. с. 799. ISBN 978-0130869982. (англ.)
• Судоплатов С. В, Овчинникова Е. В. Элементы дискретной математики. — НГТУ, 2002. — ISBN 5-7782-0332-2. (рос.)
• Виленкин Н.Я. Популярная комбинаторика. — М. : Наука, 1975. (рос.)

Примітки

1. Stanley, Richard P.; «Hipparchus, Plutarch, Schröder, and Hough», American Mathematical Monthly 104 (1997), no. 4, 344—350.
2. Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; «On the Second Number of Plutarch», American Mathematical Monthly 105 (1998), no. 5, 446.
3. Виленкин Н. Я., 1975, с. 19.
4. O'Connor, John; Edmund Robertson. (06 2004). Abraham de Moivre. The MacTutor History of Mathematics archive. Архів оригіналу за 14 травня 2011. Процитовано 31 травня 2010.

Джерела

• Судоплатов С. В., Овчинникова Е. В. (2002). Элементы дискретной математики. НГТУ. ISBN 5-7782-0332-2.