Приклади.

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 різних ящиках так, що в першому ящику k₁ кульок, у другому – k₂ кульок, …, у n-му – k_n кульок, причому m=k₁+k₂+…+k_n. Пронумеруємо кульки від 1 до m, ящики – від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру кульки номер ящика, куди вона потрапила. Отже, маємо послідовність довжини m=k₁+k₂+…+k_n, в якій номери 1, 2, …, n повторюються k₁, k₂, …, k_n разів відповідно. Очевидно, що така функція відповідає розкладу кульок взаємно однозначно. Таким чином, розклад подається як перестановка з повтореннями складу (k₁, k₂, …, k_n).

Кількість перестановок з повтореннями з елементів множини A={a₁, a₂, …, a_n} складу (k₁, k₂, …, k_n) позначається P(k₁, k₂, …, k_n) і виражається формулою:

P(k₁, k₂, …, k_n)= .

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

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

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

P(k₁, k₂, …, k_n)= .

Поставимо довільній перестановці складу (k₁, k₂, …, k_n, k_n+1) у відповідність пару вигляду (підмножина номерів місць, де розташовано елементи a_n+1, перестановка з повтореннями решти елементів по інших місцях).

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

Оскільки очевидно, що відповідність між перестановками складу (k₁, k₂, …, k_n, k_n₊₁) та наведеними парами є взаємно однозначною, то правильність формули для P(k₁, k₂, …, k_n) доведено.

За означенням, перестановки складу (k₁, k₂, …, k_n) є послідовностями довжини m=k₁+k₂+…+k_n, тобто розміщеннями з повтореннями окремого вигляду, а саме, з фіксованими кількостями елементів a₁, a₂, …, a_n. Таким чином, послідовності чисел (k₁, k₂, …, k_n), таких, що k₁+k₂+…+k_n=m, взаємно однозначно відповідає підмножина множини розміщень. Перебираючи всі можливі послідовності чисел (k₁, k₂, …, k_n), ми перебираємо всі можливі розміщення.

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

n^m= .

Поняття комбінацій в комбінаториці.

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

<== попередня сторінка	\|	наступна сторінка ==>
Поняття перестановок в комбінаториці	\|	Приклади.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.