Комбінаторика
Комбінато́рика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай, скінченної множинивідповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.
Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття.
Комбінаторика пов'язана з багатьма іншими розділами математики.
Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».
Іноді під комбінаторикою розуміють більш широкий розділ дискретної математики, що включає теорію графів.
Основні положення
Під комбінаторикою звичайно розуміють розділ дискретної математики, присвячений розв'язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами. У результаті створюються необхідні комбінаторні об'єкти чи конфігурації. Характерними властивостями цих об'єктів є те, що вони відповідають деяким обмеженням щодо них, і тому завжди можна розпізнати дозволений комбінаторний об'єкт, який відповідає правилам його побудови, і недозволений, який не відповідає цим правилам.
З комбінаторикою мають справу хіміки при вивченні різних можливих типів зв'язків атомів у молекулах; біологи, наприклад, у процесі знаходження послідовностей амінокислот у білкових сполуках; кібернетики при розв'язанні задач кодування й побудові обчислювальних пристроїв, математики — при розв'язанні багатьох різних задач, особливо в теорії ймовірності. Також комбінаторику використовують у своїх моделях фізики, архітектори, економісти й представники багатьох інших наук.
Комбінаторні задачі
У комбінаториці є декілька задач, які вирішуються послідовно одна за одною. Перша з них спочатку формулює вимоги до класу комбінаторних конфігурацій, які потрібно побудувати. Доводиться, що хоча б одна така конфігурація існує, попри те, що побудувати таку конфігурацію може бути досить непросто. Тому інколи буває достатньо теоретичного доведення її існування.
Після розв'язання першої задачі комбінаторики розв'язується не менш важлива друга — задача переліку комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами?
Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується третя задача комбінаторики — це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу 30 студентів на 30 місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх комбінаторних конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість.
Четверта і остання задача комбінаторики — це задача про пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до оптимуму. Це на сьогодні досить нелегка для розв'язання загальна задача. Вона містить задачі комбінаторної оптимізації, наприклад, задачу комівояжера, яка на сьогодні ще не має остаточного розв'язання.