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

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!.

3. Комбінації без повторень

Означення. Комбінація по 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! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є =. Ця кількість позначається або .

4. Перестановки з повтореннямиОзначення. Перестановка з повтореннями по 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.