Комбінаторний аналіз

Комбінаторний аналіз

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

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

Приклади комбінаторних конфігурацій і завдань

Для формулювання і розв'язання комбінаторних задач використовують різні моделі комбінаторних конфігурацій. Прикладами таких конфігурацій є:

• Розміщенням із n елементів по k називається впорядкований набір із k різних елементів деякої n-елементної множини.
• Перестановкою з n елементів (наприклад чисел 1, 2, ..., n) називається такий упорядкований набір із цих елементів. Перестановка також є розміщенням із n елементів по n.
• Сполученням з n по k називається набір k елементів, вибраних із даних n елементів.
• Композицією числа n називається таке подання n у вигляді впорядкованої суми цілих позитивних чисел.
• Розбиттям числа n називається таке подання n у вигляді невпорядкованої суми цілих позитивних чисел.

Приклади задач з комбінаторики:

1. Скількома способами можна розмістити n предметів по m скриньках, щоб виконувалися задані обмеження?
2. Скільки існує різних перестановок з 52 гральних карт?
3. Відповідь: 52! (52 факторіал), тобто, 80658175170943878571660636856403766975289505440883277824000000000000 або приблизно 8,0658 × 10⁶⁷.
4. При грі в кості кидаються дві кістки, і випали певні значення; скільки існує комбінацій, у яких сума очок на верхніх гранях дорівнює дванадцяти?

Рішення: Кожен можливий результат відповідає функції F: {1, 2 } to {1, 2, 3, 4, 5, 6} (аргумент функції — це номер кістки, значення — значення на верхній грані). Очевидно, що лише 6 + 6 дає нам потрібний результат 12. Таким чином, існує лише одна функція, яка ставить у відповідність 1 число 6, і 2 число 6. Або, іншими словами, існує всього одна комбінація, при якій сума очок на верхніх гранях дорівнює дванадцяти.

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

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

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

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

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

Правило суми

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Розділи комбінаторики

Перелічувальна

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

Кількість конфігурацій, утворених декількома маніпуляціями над множиною, підраховується згідно з правилами додавання і множення.

Типовим прикладом задач цього розділу є підрахунок кількості перестановок.

Структурна

До цього розділу відносяться деякі питання теорії графів, а також теорії матроїдів.

Екстремальна

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

Теорія Рамсея

Теорія Рамсея вивчає наявність регулярних структур у випадкових конфігураціях елементів. Прикладом твердження з теорії Рамсея може служити наступне:

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

Імовірнісна

Цей розділ відповідає на питання виду: яка ймовірність присутності певної властивості у заданої множини.

Топологічна

Докладніше: Топологічна комбінаторика

Застосовує ідеї та методи комбінаторики в топології, при вивченні дерева прийняття рішень, частково впорядкованих множин та ін.

Інфінітарна

Застосування ідей і методів комбінаторики до нескінченних (у тому числі, незліченних) множин.

Відкриті проблеми

Комбінаторика, і зокрема, теорія Рамсея, містить багато відомих відкритих проблем, часом через нескладне формулювання. Наприклад, невідомо, при якому найменшому N в будь-якій групі з N чоловік знайдуться 5 осіб, або попарно знайомих один з одним, або попарно незнайомих. [1]

Історія

Джироламо Кардано написав математичне дослідження гри в кості яке було опубліковане посмертно. Теорією цієї гри займалися також Тарталья і Галілей. В історії зароджувалась теорія ймовірностей яка увійшла з листування запеклого гравця Шевальє де Мере з П'єром Ферма і Блез Паскаль, де були порушені кілька тонких комбінаторних питань. Крім азартних ігор, комбінаторні методи використовувалися (і продовжують використовуватися) в криптографії — як для розробки шифрів, так і для їх злому. Блез Паскаль багато займався біноміальними коефіцієнтами і відкрив простий спосіб їх обчислення: «трикутник Паскаля». Хоча цей спосіб був уже відомий на Сході (приблизно з X століття), Паскаль, на відміну від попередників, суворо виклав і довів властивості цього трикутника. Поряд з Лейбніцем, він вважається основоположником сучасної комбінаторики. Сам термін «комбінаторика» придумав Лейбніц, який в 1666 (йому було тоді 20 років) опублікував книгу «Міркування про комбінаторне мистецтво». Правда, термін «комбінаторика» Лейбніц розумів надмірно широко, включаючи в нього всю скінченну математику і навіть логіку [2]. Учень Лейбніца Якоб Бернуллі, один із засновників теорії ймовірностей, виклав у своїй книзі «Мистецтво припущень» безліч відомостей з комбінаторики.

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

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

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

• задача про хід коня;
• задача про сім мостів, з якої почалася теорія графів;
• побудова греко-латинських квадратів;
• узагальнені перестановки.

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

Примітки

1. ↑ Виленкин Н. Я., 1975, с. 19
2. ↑ O'Connor, John; Edmund Robertson. Abraham de Moivre. The MacTutor History of Mathematics archive (06 2004).
3. ↑ Weisstein, Eric W. Числа Рамсея (англ.) На сайті Wolfram MathWorld.

Література

• Андерсон Джеймс. Дискретна математика і комбінаторика = Discrete Mathematics with Combinatorics. — М.: «Вільямс», 2006. — С. 960. — .
• Виленкин Н.Я. Популярна комбінаторика. — М.: Наука, 1975.
• Ерош І. Л. Дискретна математика. Комбінаторика — СПб .: СПбГУАП, 2001. — 37 c.
• Липський В. Комбінаторика для програміста. — М.: Світ, 1988. — 213 с.
• Раізер Г. Дж. Комбінаторна математика. — Пров. з англ. — М., 1966.
• Райгородский А. М. Лінійно-алгебраїчні і імовірнісні методи в комбінаториці. — Літня школа «Сучасна математика». — Дубна, 2006.
• Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми. Теорія і практика. — М.: Світ, 1980. — 476 с.
• Ріордан Дж. Введення в комбінаторний аналіз. — Пров. з англ. — М., 1963.
• Р. Стенлі. Перечислительную комбінаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — .
• Р. Стенлі. Перечислительную комбінаторика. Дерева, виробляють функції і симметрические функції = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — .

Посилання

• Комбінаторний аналіз [ 20 Квітня 2016 у Wayback Machine.] //ЕСУ