Фахівцям різних областей необхідно вирішувати комбінаційні завдання: перестановка цифр, знаків та інших об’єктів. Наприклад, керівникові цеху потрібно розподілити різні види робіт між працюючими верстатами. Комбінаторика – це важливий розділ математики, який, як не важко здогадатися, знаходить свою нішу в самих різних областях і спеціальності: фізика, біологія, лінгвістика, хімія, інженерія, теорія кодування і багато іншого. Принципи комбінаторики також лежать в основі рішення багатьох імовірнісних задач.
Історія
Перші передумови комбінаторики як науки, з’явилися в 16 ст. Сприяло розвитку даної галузі знань великою мірою захоплення людей азартними іграми: в карти, кістки, лотереї програвали не просто золото і коштовності, а палаци та маєтки. Тому, задаючись питанням, наприклад, про те, як часто можна викинути вдалий набір очок на кістках або отримати два туза, люди поступово прийшли до основ комбінаторики та ймовірності. Допомогла комбінаторика комусь вигравати більше або втрачати менше? Питання цікаве, але його розгляд виходить за межі даної статті.
Перший математик, активно займався питаннями комбінаторики – це італієць Тарталья (1499-1557 рр.) Після нього у вивчення даних питань активно занурилися такі імениті вчені, як Паскаль, Ферма, Бернуллі, Лейбніц, Ейлер та ін. Проте варто зауважити, що комбінаторика і раніше залишалася якщо не кумедною грою з числами, то теорією, яка використовується виключно в азартних іграх і не має права застосовуватися де-небудь ще.
Розвиток комбінаторики
Значущі зрушення в питаннях комбінаторики трапилися з появою в 20 ст. обчислювальних машин, програмування, а головне – дискретної математики. У цей період комбінаторика отримує пік свого бурхливого розвитку і стає повноцінною наукою. Комбінаторні методи починають використовуватися повсюдно:
- рішення транспортних завдань;
- складання розкладів;
- підготовка планів виробництва і продажу товарів;
- у теорії випадкових процесів;
- в математичній статистиці та теорії ймовірностей;
- у підготовці та проведення експериментів;
- у шахах;
- в термодинаміці;
- в геометрії;
- і у багатьох інших областей.
Задача про забобонний керівника
Жив та був на світі керівник, який вірив, що число 8 приносить йому суцільні невдачі. Тому він вирішив позбутися від усіх чисел, які містили б вісімку. Працювало під його початком 600 осіб. У кожного був ідентифікаційний номер пропуску на роботу, що складається з трьох чисел. Недовго думаючи, керівник вирішив виключити і з номерів пропусків число 8. І тут він замислився, а чи вистачить різних чисел на 600 осіб з діапазону від 000 до 999, які не включали б 8?
Очевидним рішенням даної задачі є виписування вручну всіх чисел від 000 до 999) і викреслення тих з них, у яких присутні вісім. Чи можна вирішити поставлену задачу більш простим способом? Якщо для 999 чисел завдання з перебором всіх варіантів виглядає здійсненним, то діапазон від 000000 до 999999 вимагає значно більших зусиль. Саме для економії сил і часу покликані формули комбінаторики.
Рішення задачі про забобонний керівника
Інший спосіб рішення виглядає наступним чином. Виключивши 8 з ряду, ми отримаємо, що 0, 1, 2, 3, 4, 5, 6, 7, 9 – дані дев’ять чисел є допустимими. Після цього слід знайти всі двозначні номери, які не містили б 8. Робиться це просто: потрібно взяти будь-яке число з допустимих і дописати до нього також будь-число допустимих. Таким чином ми легко отримаємо всі двозначні цифри, які підходять під умову. В результаті отримаємо, що кожен однозначний номер дасть 9 різних двозначних. Підсумкове число таких цифр буде 9*9 = 92 = 81.
Продовжуючи аналогію, можна укласти, що для одержання всіх тризначних чисел без вісімок, потрібно до наявних двозначних чисел приписати третій розряд, також з допустимих значень. Тоді отримаємо, що число таких цифр буде 92*9 = 9*9*9 = 729. Таким чином ми з’ясували, що наш горе керівник легко зможе забезпечити 600 працівників перепустками, номери яких не будуть містити 8. Спробуйте самостійне вирішити задачу для випадку з п’ятизначними номерами.
А що буде, якщо керівнику не сподобається ще й число 2? Виходить, тоді кількість допустимих чисел буде 8, а саме: 0, 1, 3, 4, 5, 6, 7, 9. Тоді прикинувши кількість комбінацій чисел без 2 і 8, можна зробити висновок, що їх кількість одно 8*8*8 = 512, а цього явно недостатньо, щоб забезпечити 600 осіб перепустками. Комбінаторика – це наука, що допомагає відповідати на подібні питання більш ефективно, ніж це можна зробити методом перебору.
Задача про лото
Всім відома гра. Є мішок, у якому лежать бочонки з номерами від 1 до 90. Всім учасникам роздаються квитки, в яких потрібно зафарбувати деяка кількість клітин з числами. Після чого ведучий лото дістає з мішка один з пронумерованих діжок. Переможцем буде той, у кого в квитку закреслено найбільше чисел, що збігаються з тими, які витягнув ведучий гри.
Як-то раз Ніна, граючи в лото, задумалася. Вона часто спостерігала, як ведучий дістає з мішка один і той же номер. Але в той же час перші два барила виявлялися однаковими значно рідше. Тоді вона задалася питанням, скількома способами можна послідовно дістати з мішка два барила? Елементи комбінаторики допомагають відповісти на її питання.
Рішення задачі про лото
Очевидно, перший бочонок може мати номери від 1 до 90. Іншими словами, існує 90 способів отримати перший бочонок. Але як йдуть справи далі? Якщо, припустимо, барило №63 було витягнуто з мішка, то в поточній грі він більше не повториться.
Вирішити поставлену задачу нам допоможе метод таблиці. Де в головній рядку і в заголовному стовпці будуть виписані номери від 1 до 90. Таким чином, на перетин якої-небудь рядка і якого-небудь стовпця виявиться пара чисел, або пара вилучених з мішка діжок. При цьому на діагоналі таблиці будуть розташовуватися однакові пари чисел. Що неможливо за умовою, так як після вилучення однієї цифри з мішка, її повторення неможливо. Вийде таблиця наступного вигляду:
| 1 | 2 | … | 90 | |
| 1 | x | 1, 2 | … | 1, 90 |
| 2 | 2, 1 | x | … | 2, 90 |
| … | … | … | x | … |
| 90 | 90, 1 | 90, 2 | … | x |
Разом отримуємо таблицю, у якій кількість клітинок дорівнює 90*90 = 8100. При цьому варто пам’ятати, що по діагоналі розташовується 90 пар цифр, неможливих умов. Тоді відповіддю на питання про те, скількома способами можна дістати з мішка 2 барильця – 8100 – 90 = 8010 варіантів.
Розмірковуючи трохи іншим способом можна прийти до такого ж відповіді. Для першого барильця існує 90 варіантів. Після того як перший був витягнутий, для другого барильця залишиться 89 варіантів. Таким чином, загальна кількість варіантів складе 90*89 = 8010. Елементи комбінаторики можуть застосовуватися різними шляхами. Питання лише в простоті і універсальності методу. Так, наприклад, метод таблиць можна використовувати для видобутих трьох поспіль діжок і, очевидно, це буде межа. А що для чотирьох і більше?
Задача про екіпаж корабля
Якщо варіанти вибору залежать від того, які об’єкти були обрані раніше, то такий процес зручно відобразити у вигляді “дерева”. На першому кроці з однієї точки відкладається стільки ліній, скільки існує можливих виборів на першому кроці. На кінцях кожної лінії також проводять стільки додаткових ліній, скільки можна зробити на другому кроці і т. д. В результаті буде намальовано свого роду дерево або граф. Комбінаторика і теорія може звучати досить заплутано і незрозуміло, тому розглянемо на прикладі.
Перед початком експедиційного року у керівництва стоїть завдання – зібрати екіпажі для поїздок. Кожна команда повинна включати в себе три людини: командир, інженера і лікаря. При цьому кількість фахівців у тій чи іншій галузі може змінюватись. Припустимо, наприклад, щоб у дві різні експедиції вирушав один лікар, т. к. лікарів всього двоє, а командирів і інженерів може бути по троє. При цьому укладачеві експедиційного плану необхідно враховувати психологічну сумісність членів команди. Дана характеристика є однією з найбільш важливих в довгих і далеких експедиціях для їх успішного проведення. Виходячи з усіх описаних умов, вимальовується наступна картина:
Де ai – командири, bi – інженери і ci – лікарі. При цьому в ході тестування кожної людини було з’ясовано, що командир a1 психологічно добре ладнає з інженерами b1 і b3, a2 – з b1 і b2, а ось лікар c3 несумісний з інженером b1 і т. д. Питання, які спочатку ставилося перед керівником проекту – скільки екіпажів можна скласти при таких умовах. З складеної діаграми видно, що всього таких екіпажів може бути 10. Але що було б, якщо питання про психологічної сумісності не мав ваги? Тоді виходить, що після вибору командирів ai, існувало б по 3 альтернативи для кожного з них у виборі інженера. Відповідно, для пари командира та інженера також було б 3 варіанти лікарів. Тоді кількість комбінацій досягне 4*3*3 = 36 екіпажів.
Розміщення, перестановки й сполучення
У прикладах вище рішення завдань відбувалося так званим аксиоматическим методом. Тобто, можна говорити, що існує ряд основних завдань, до вирішення яких можуть зводитися багато проблем. Однак точно також як в стереометрії незручно вирішувати завдання, грунтуючись виключно на аксіомах, і для цього використовується більш зручний інструмент під назвою “теорема”, так і в комбінаториці зручніше використовувати більш узагальнені та доведені методи. У ході багатовікового вивчення комбінаторики стало очевидним, що ряд завдань зустрічається набагато частіше інших, і вони були виділені в окремі класи і отримали свої назви, ставши в комбінаторики основними, а саме: розміщення, перестановки й сполучення.
Проблеми комбінаторики
Однією з ключових проблем комбінаторних методів є визначення того, яке коло завдань слід вважати комбінаторні. Строго визначити цього не можна із-за дуже великої різноманітності проблем, які потрапляють в категорію комбінаторних. І потім, багато завдань можуть відноситься як комбінаториці, так і до іншої області, будучи суміжними або прикордонними.
У спрощеному випадку можна виділити, що до комбінаторної математики відносяться завдання, що припускають вибірки та розташування об’єктів. При цьому для комбінаторики характерна робота виключно з кінцевим безліччю об’єктів. Виходячи з цих положень, можна розмежувати такі, характерні для комбінаторики, завдання:
Якщо розглянута задача може бути віднесена до одного з цих типів, то вона є комбінаторної і формули комбінаторики допоможуть її вирішити.
