Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Перестановки з повтореннями
|
|
Означення. Перестановка з повтореннями по m елементів множини A ={ a 1, a 2, …, an } складу (k 1, k 2, …, kn) – це послідовність довжини m = k 1+ k 2+…+ kn, в якій елементи a 1, a 2, …, an повторюються відповідно k 1, k 2, …, 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 різних ящиках так, що в першому ящику k 1 кульок, у другому – k 2 кульок, …, у n -му – kn кульок, причому m = k 1+ k 2+…+ kn. Пронумеруємо кульки від 1 до m, ящики – від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру кульки номер ящика, куди вона потрапила. Отже, маємо послідовність довжини m = k 1+ k 2+…+ kn, в якій номери 1, 2, …, n повторюються k 1, k 2, …, kn разів відповідно. Очевидно, що така функція відповідає розкладу кульок взаємно однозначно. Таким чином, розклад подається як перестановка з повтореннями складу (k 1, k 2, …, kn).
Кількість перестановок з повтореннями з елементів множини A ={ a 1, a 2, …, an } складу (k 1, k 2, …, kn) позначається P (k 1, k 2, …, kn) і виражається формулою:
P (k 1, k 2, …, kn)= 
.
Доведемо її за допомогою математичної індукції за n.
1. База індукції. При n =2 будь-якій перестановці складу (k 1, k 2) взаємно однозначно відповідає підмножина тих номерів місць із {1, 2, …, k 1+ k 2}, на яких розташовано елементи a 1. Але ці підмножини є комбінаціями з k 1+ k 2 по k 1, і їх 
. Отже, P (k 1, k 2)= 
, і базу доведено.
2. Індукційний перехід. За припущенням індукції,
P (k 1, k 2, …, kn)= .
Поставимо довільній перестановці складу (k 1, k 2, …, kn, kn +1) у відповідність пару вигляду
(підмножина номерів місць, де розташовано елементи an+ 1,
перестановка з повтореннями решти елементів по інших місцях).
За принципом добутку та за припущенням індукції, кількість таких пар є
Оскільки очевидно, що відповідність між перестановками складу (k 1, k 2, …, kn, kn +1) та наведеними парами є взаємно однозначною, то правильність формули для P (k 1, k 2, …, kn) доведено.
За означенням, перестановки складу (k 1, k 2, …, kn) є послідовностями довжини m = k 1+ k 2+…+ kn, тобто розміщеннями з повтореннями окремого вигляду, а саме, з фіксованими кількостями елементів a 1, a 2, …, an. Таким чином, послідовності чисел (k 1, k 2, …, kn), таких, що k 1+ k 2+…+ kn = m, взаємно однозначно відповідає підмножина множини розміщень. Перебираючи всі можливі послідовності чисел (k 1, k 2, …, kn), ми перебираємо всі можливі розміщення.
Наведені неформальні міркування демонструють зв'язок між перестановками й розміщеннями з повтореннями та обгрунтовують формулу:
nm = 
.