Початки комбінаторики

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то AB містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то AB містить mn елементів, тобто пар.

Кількість елементів множини A будемо далі позначати |A|.

Ці правила мають також вигляд:

Принцип суми. Якщо об'єкт A можна вибрати m способами, а об'єкт B – n іншими способами, то вибір "або A, або B" можна здійснити m+n способами.

Принцип добутку. Якщо об'єкт A можна вибрати m способами і після кожного такого вибору об'єкт B може бути вибраним n способами, то вибір "A і B" в указаному порядку можна здійснити mn способами.

Наведені правила очевидним чином узагальнюються на випадки довільних скінченних об'єднань множин, що попарно не перетинаються, та на скінченні декартові добутки.

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

Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

Означення. Розміщення з повтореннями по m елементів n-елементної множини A – це послідовність елементів множини A, що має довжину m.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Якщо |A|=n, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина Am=AA…A, містить nm елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2m. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини m.

У багатьох комбінаторних задачах об'єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A1, другий – A2, тощо. Але досить часто множина A2 визначається лише після того, як зафіксовано перший член послідовності, A3 – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A1|=10, |A2|=|A3|=…=|A7|=9, і загальна кількість номерів є 1096.

Означення. Розміщення по m елементів n-елементної множини A, де mn – це послідовність елементів множини A, що має довжину m і попарно різні члени.

Приклади.

1. При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c), (b,a), (b,c), (c,a), (c,b).

2. Розподіл n різних кульок по одній на кожний з m різних ящиків, mn. Ящики можна пронумерувати від 1 до m, кульки – від 1 до n. Тоді кожному розподілу взаємно однозначно відповідає послідовність довжини m попарно різних номерів від 1 до n.

Неважко підрахувати кількість послідовностей з прикладу 2. На першому місці може стояти будь-який із номерів 1, …, n. На другому – незалежно від того, який саме був на першому, будь-який із n-1, що залишилися. І так далі. За принципом добутку, таких послідовностей

n(n-1)…(n-m+1),

або n!/(n-m)!. Цей добуток позначається або (n)m або nm.

Означення. Перестановка n елементів множини A без повторень – це розміщення по n елементів, тобто послідовність елементів множини A, що має довжину n і попарно різні члени.

Приклад. При A={a, b, c} усі перестановки –це трійки (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Очевидно, що кількість перестановок n елементів дорівнює кількості розміщень по m при m=n, тобто n!. Отже, nn=n!.

Означення. Комбінація по m елементів n-елементної множини – це її m-елементна підмножина.

Приклади.

1. При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b}, {a,c}, {b,c}.

2. Розподіл n різних кульок по одній на кожний з m однакових ящиків, mn. Оскільки ящики однакові, то розподіл взаємно однозначно визначається підмножиною з m кульок, що розкладаються.

З кожної m-елементної комбінації елементів n-елементної множини можна утворити m! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є =. Ця кількість позначається або .

Означення. Перестановка з повтореннями по m елементів множини A={a1, a2, …, an} складу (k1, k2, …, kn) – це послідовність довжини m=k1+k2+…+kn, в якій елементи a1, a2, …, an повторюються відповідно k1, k2, …, kn разів.

Приклади.

1. При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

2. Нехай m різних кульок розкладаються по n різних ящиках так, що в першому ящику k1 кульок, у другому – k2 кульок, …, у n-му – kn кульок, причому m=k1+k2+…+kn. Пронумеруємо кульки від 1 до m, ящики – від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру кульки номер ящика, куди вона потрапила. Отже, маємо послідовність довжини m=k1+k2+…+kn, в якій номери 1, 2, …, n повторюються k1, k2, …, kn разів відповідно. Очевидно, що така функція відповідає розкладу кульок взаємно однозначно. Таким чином, розклад подається як перестановка з повтореннями складу (k1, k2, …, kn).

Кількість перестановок з повтореннями з елементів множини A={a1, a2, …, an} складу (k1, k2, …, kn) позначається P(k1, k2, …, kn) і виражається формулою:

P(k1, k2, …, kn)=.

Доведемо її за допомогою математичної індукції за n.

1. База індукції. При n=2 будь-якій перестановці складу (k1, k2) взаємно однозначно відповідає підмножина тих номерів місць із {1, 2, …, k1+k2}, на яких розташовано елементи a1. Але ці підмножини є комбінаціями з k1+k2 по k1, і їх . Отже, P(k1, k2)=, і базу доведено.

2. Індукційний перехід. За припущенням індукції,

P(k1, k2, …, kn)=.

Поставимо довільній перестановці складу (k1, k2, …, kn, kn+1) у відповідність пару вигляду

(підмножина номерів місць, де розташовано елементи an+1,

перестановка з повтореннями решти елементів по інших місцях).

За принципом добутку та за припущенням індукції, кількість таких пар є

Оскільки очевидно, що відповідність між перестановками складу (k1, k2, …, kn, kn+1) та наведеними парами є взаємно однозначною, то правильність формули для P(k1, k2, …, kn) доведено.

За означенням, перестановки складу (k1, k2, …, kn) є послідовностями довжини m=k1+k2+…+kn, тобто розміщеннями з повтореннями окремого вигляду, а саме, з фіксованими кількостями елементів a1, a2, …, an. Таким чином, послідовності чисел (k1, k2, …, kn), таких, що k1+k2+…+kn=m, взаємно однозначно відповідає підмножина множини розміщень. Перебираючи всі можливі послідовності чисел (k1, k2, …, kn), ми перебираємо всі можливі розміщення.

Наведені неформальні міркування демонструють зв'язок між перестановками й розміщеннями з повтореннями та обгрунтовують формулу:

nm=.

Комбінації елементів якоїсь множини – це її підмножини. Але у множинах елементи не повторюються, тому термін "комбінації з повтореннями", що склався в математиці, не можна вважати вдалим.

Розглянемо це поняття за допомогою перестановок із повтореннями. Усі перестановки з повтореннями з елементів множини A={a1, a2, …, an} з тим самим складом (k1, k2, …, kn), де k1+k2+…+kn=m, будемо вважати еквівалентними між собою. Таким чином, множина перестановок розбивається на класи еквівалентності, які взаємно однозначно відповідають усім можливим складам (k1, k2, …, kn). Кожний такий клас еквівалентності й називається комбінацією по m елементів з повтореннями складу (k1, k2, …, kn) [1].

Можна означити комбінації з повтореннями дещо інакше. Серед усіх еквівалентних перестановок складу (k1, k2, …, kn) є перестановка вигляду

(a1, a1, …, a1, a2, a2, …, a2, …, an, an, …, an).

  

k1 k2 … kn

Цю перестановку також будемо називати комбінацією по m елементів множини {a1, a2, …, an} з повтореннями складу (k1, k2, …, kn).

Приклади.

1. При A={a, b, c} усіма комбінаціями по 2 з повтореннями є послідовності (a,a), (a,b), (a,c), (b,b), (b,c), (c,c). Їм відповідають усі можливі склади (2,0,0), (1,1,0), (1,0,1), (0,2,0), (0,1,1), (0,0,2).

2. Нехай m однакових кульок розкладаються по n різних ящиках так, що у першому ящику k1 кульок, у другому – k2 кульок, …, у n-му – kn кульок, причому m=k1+k2+…+kn. Пронумеруємо ящики від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру ящика кількість кульок у ньому. Отже, маємо послідовність (k1, k2, …, kn), що є складом. Припишемо кожній кульці номер її ящика і утворимо послідовність номерів вигляду

(1, …, 1, 2, …, 2, …, n, …, n).

  

k1 k2 … kn

Як бачимо, множиною елементів, якими утворюється комбінація з повтореннями, тут є {1, 2, …, n}.

Комбінації по m елементів множини {a1, a2, …, an} з повтореннями складу (k1, k2, …, kn) можна взаємно однозначно поставити у відповідність послідовність довжини m+n-1 із m "1" і n-1 "0":

(1, …, 1, 0, 1, …, 1, 0, …, 1, …, 1).

  

k1 k2 … kn

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

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

|AB|=|A|+|B|-|AB|. (*)

При обчисленні |ABC| додавання |A|+|B|+|C| веде до того, що елементи кожного з перетинів |AB|+|BC|+|AC| враховуються двічі, тому їх треба по одному разу відняти. Якщо перетин ABC порожній, то в результаті кожний елемент об'єднання враховано по одному разу, і все гаразд. Якщо ні, то в результаті елементи цього перетину тричі додаються і тричі віднімаються, тобто у виразі

|A|+|B|+|C|–|AB|–|BC|–|AC|

не враховані. Отже, їх треба додати:

|AB|=|A|+|B|+|C|–|AB|–|BC|–|AC|+|ABC|. (**)

Вирази (*), (**) наводять на припущення, що в загальному випадку об'єднання n множин A1, A2, …, An

|A1A2…An|=|A1|+|A2|+…+|An|–|A1A2|–|A1A3|–…–|An-1An|+
+|A1A2A3|+…+|An-2An-1An|–…+(-1)n+1|A1A2…An|. (1)

Як бачимо, кількості елементів усіх можливих перетинів непарної кількості множин додаються, а парної – віднімаються. Формула (1) називається формулою включень і виключень.

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

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

Приклад. Є група студентів, серед яких каву п'ють 12 (це множина A), чай – 10 (множина B), йогурт – 8 (C), каву і чай – 5 (AB), каву і йогурт – 4 (AC), чай і йогурт – 3 (BC), усі три напої – 1 (ABC). Тоді всього студентів у групі 12+10+8-5-4-3+1=19.

За допомогою формули (1) можна обчислити кількість елементів деякої множини U, що не належать жодній з її підмножин A1, A2, …, An:

|U\(A1A2…An)|=|U|–|A1|–|A2|–…–|An|+|A1A2|+|A1A3|+…+
+|An-1 An|–|A1A2A3|–…–|An-2An-1An|+…+(-1)n|A1A2…An|. (2)

Формулу (2) також називають формулою включень і виключень.

Означення. Біном Ньютона – це вираз вигляду (a+b)n.

Біном розкладається в суму одночленів, які є добутками деяких степенів його доданків a і b. Школярі-восьмикласники знають формули розкладу бінома Ньютона в многочлен із степенями a і b при n=2 та 3:

(a+b)2=a2+2ab+b2,

(a+b)3=a3+3a2b+3ab2+b3.

Спробуємо розкласти (a+b)n в многочлен у загальному випадку n. Запишемо його у вигляді, пронумерувавши дужки:

1 2 … n

(a+b)(a+b)…(a+b).

Очевидно, що кожний доданок містить n множників – k множників a і n-k множників b, тобто має вигляд akbn-k, де kn, k0. Кожний такий доданок взаємно однозначно відповідає підмножині номерів дужок, з яких для утворення цього доданка ми брали множники a. Таким чином, доданків akbn-k рівно стільки, скільки таких підмножин, тобто =. Отже,

(a+b)n =

Коефіцієнти при akbn-k називаються біноміальними, оскільки записуються в розкладі бінома (a+b)n.

Біноміальні коефіцієнти мають очевидну властивість симетрії:

= =..

Розглянемо окремі випадки бінома Ньютона:

при b=1 маємо (a+1)n = ,

при a=b=1 маємо (1+1)n = 2n = ,

при a= –1, b=1 маємо (–1+1)n = 0n = (–1)k.

За останньою рівністю, зокрема, природно означити 00 як 1, слідуючи за Доналдом Кнутом ****.

Запишемо біноміальні коефіцієнти для початкових значень n=0, 1, …, 5 у трикутну таблицю:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

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

= +

Ця тотожність називається правилом додавання. Існує багато різних її доведень. Ось "лобове":

Доозначимо біноміальні коефіцієнти при k<0 та k>n як =0. Тоді правило додавання справджується за будь-яких значень k. Скористаємося цим доозначенням також і далі, розглядаючи суми, в яких додавання ведеться за нижнім коефіцієнтом k у виразах вигляду . Це дозволить не записувати межі, у яких змінюється k.

Доведемо ще одну тотожність, яка називається згорткою Вандермонда:

.

Якщо замінити k на k-m, а n – на n-m, то одержимо рівність

.

Вона має назву тотожності Коші. Доведемо спочатку цю рівність. Нехай є r дівчат і s юнаків. Праворуч маємо кількість способів вибрати з них усіх n осіб. Кожний доданок у сумі ліворуч задає кількість способів вибрати n осіб так, щоб серед них було k дівчат з r і n-k юнаків з s. Додавання цих кількостей по всіх можливих значеннях k дає кількість всіх способів вибрати з них усіх n осіб. Отже, вирази ліворуч і праворуч задають одну й ту саму кількість, тобто рівні. Якщо тепер замінити назад k на k+m, а n на n+m, одержимо початкову рівність.

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

1

1 1

1 2 1

1 3 3 1

…

Розширимо поняття біноміальних коефіцієнтів на дійсні значення n. Згадаємо зв'язок між кількістю комбінацій з n елементів по k та кількістю їх розміщень без повторень: = (n)k/k!, де (n)k=n(n–1)…(n–k+1). Але останній добуток означений при будь-якому дійсному значенні n. Слідуючи Доналду Кнуту ****, замість цілого n розглянемо дійсне r: (r)k=r(r–1)…(r–k+1). Тоді за дійсних значень r означимо як (r)k/k!.