Комбінаторні принципи

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

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

Комбінаторні з'єднання

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

Деяка сукупність елементів вибраних з заданих множин називається вибіркою. Число елементів у вибірці називається довжиною вибірки.

Приклад 1. Нехай дана множина Х — множина цифр, тобто {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Ця множина складається з 10 елементів. Будь-який набір цифр, що складається, наприклад, з 4 цифр буде вибіркою довжини 4.

Зауваження. Деяку сукупність елементів з цієї кінцевої множини можна вибирати по-різному: якщо при складанні вибірки враховується порядок дотримання елементів у вибірці, тоді вибірка називається впорядкованою; якщо ж при складанні вибірки не враховується порядок дотримання елементів в ній, то вибірка називається невпорядкованою; якщо при складанні вибірки в неї може бути включений один і той же елемент кілька разів, то вибірка називається вибіркою з повтореннями; якщо ж елементи входять у вибірку тільки по одному разу, то вибірка називається вибіркою без повторень.

Приклад 2. Нехай дана множина Х — множина цифр, тобто {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Скласти з цифр п'ятизначне число, цифри в якому не повторюються. Цим п'ятизначним числом може бути, наприклад, число 54321. Переставимо цифри в цьому числі, наприклад, так 45321, в результаті отримаємо інше число (іншу вибірку). Таким чином, при зміні порядку дотримання елементів у вибірці, змінюється сама вибірка, тому кожне п'ятизначне число є впорядкованою вибіркою. Оскільки обидва складені числа не мають у складі однакових цифр, ці вибірки є вибірками без повторень. Проте п'ятизначне число, наприклад, 554331 є впорядкованою вибіркою, але з повтореннями.

Приклад 3. Нехай є листівки 6 видів. Скласти з цих листівок набір, що складається з 4 листівок. Кожен набір з 4 листівок буде вибіркою. Якщо ми поміняємо в наборі місцями дві листівки, то від цього набір листівок не змінитися, тобто вибірка залишиться колишньою. Таким чином, при зміні порядку дотримання елементів у вибірці вибірка не міняється, отже, в даному випадку вибірка невпорядкована. Якщо в складеному наборі будуть однакові листівки, то він буде вибіркою з повтореннями, якщо ж усі листівки в наборі будуть різними, то набір буде вибіркою без повторень.

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

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

Правило множення  є ще одним інтуїтивним положенням про те, що якщо є A можливих результатів події та B можливих результатів для іншої події, тоді існують A · В можливих результатів.

Більш формально, якщо дана послідовність k подій з n₁ можливими результатами першої, n₂ другої, і так далі, аж до n_k можливих результатів останньої події, загальне число результатів послідовності k подій дорівнює твору n₁* n₂*…* n_k.

Завдання 1. У невеликій кондитерській до кінця робочого дня залишилося декілька тістечок: чотири ванільних, два шоколадних і три фруктових. Один покупець збирається купити тістечка перед закриттям кондитерської. Скільки тістечок може вибрати покупець?

Завдання 2. Необхідно вибрати змішану команду, яка представлятиме місцевий тенісний клуб на змаганнях. У спортивному клубі полягають 6 жінок і 9 чоловіків. Скільки різних пар можна вибрати для участі в змаганнях?

Завдання 3. Скільки тризначних чисел починаються з 3 або 4?

Перше завдання вирішується простим підрахунком. Оскільки усі тістечка різні, ми просто можемо скласти їх кількості. Це дає 4+2+3 = 9 тістечок, з яких покупець може зробити вибір. У другому завданні у нас є 6 жінок, з яких ми можемо вибрати представницю клубу, і для кожної з них ми можемо підібрати партнера серед дев'яти чоловіків. Таким чином, загальне число різних пар, які ми можемо скласти, рівне 6*9 = 54. Для вирішення третього завдання необхідно використати, як правило, суми, так і твори. Тризначні числа, про які йде мова в завданні, природним чином розбиваються на два класи, що не перетинаються. До одного з них відносяться числа, що починаються з 3, а до другого з 4. Для підрахунку чисел в першому класі помітимо, що існує один можливий результат для першої цифри (вона має дорівнювати 3), 10 результатів для другої і 10 результатів для останньої цифри. За правилом твору отримуємо, що всього чисел в першому класі налічується рівно 1*10*10 = 100. Аналогічно можна підрахувати кількість чисел в другому класі. Воно теж дорівнює 100. Нарешті, за правилом суми отримуємо, що існує 100+100 = 200 тризначних чисел, що починаються з 3 або 4.

Принцип включення-виключення

Принцип включення-виключення показані на три комплекти

Принцип включення-виключення пов'язаний з розміром об'єднання декількох множин, розміром кожної множини та розміром кожного можливого перетину множин. Найменший приклад, коли є дві множини: кількість елементів в об'єднанні А і B дорівнює сумі кількості елементів в А і B мінус число елементів їх перетину.

Взагалі, згідно з цим принципом, якщо A₁, …, A_n є кінцеві множини, то

${\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

Бієктивне доведення

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

Метод подвійного обліку

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

Принцип Діріхле

Принцип Діріхле говорить про те, що якщо А елементів розташувати в B ящиках, де A > В, то принаймні один з ящиків буде містити більше одного елемента. За допомогою цього методу можна, наприклад, продемонструвати наявність елемента в наборі з деякими специфічними властивостями.

Метод виділеного головного елементу

Метод виділеного головного елемента виділяє «головний елемент» з набору, щоб довести, якийсь результат.

Твірна функція

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

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.$

Рекурентне співвідношення

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

Список літератури

• J. H. van Lint і R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. ISBN 0-521-00601-5