Реферат: Початки комбінаторики
З кожної m -елементної комбінації елементів n -елементної множини можна утворити m ! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m ! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є =. Ця кількість позначається або .
4. Перестановки з повтореннями
Означення . Перестановка з повтореннями по 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 =.
5. Комбінації з повтореннями
Комбінації елементів якоїсь множини – це її підмножини. Але у множинах елементи не повторюються, тому термін "комбінації з повтореннями", що склався в математиці, не можна вважати вдалим.
Розглянемо це поняття за допомогою перестановок із повтореннями. Усі перестановки з повтореннями з елементів множини A ={a 1 , a 2 , …, an } з тим самим складом (k 1 , k 2 , …, kn ), де k 1 +k 2 +…+kn =m , будемо вважати еквівалентними між собою. Таким чином, множина перестановок розбивається на класи еквівалентності , які взаємно однозначно відповідають усім можливим складам (k 1 , k 2 , …, kn ). Кожний такий клас еквівалентності й називається комбінацією по m елементів з повтореннями складу (k 1 , k 2 , …, kn ) [1].
Можна означити комбінації з повтореннями дещо інакше. Серед усіх еквівалентних перестановок складу (k 1 , k 2 , …, kn ) є перестановка вигляду
(a 1 , a 1 , …, a 1 , a 2 , a 2 , …, a 2 , …, an , an , …, an ).
142431424314243
k 1 k 2 … kn
Цю перестановку також будемо називати комбінацією по m елементів множини {a 1 , a 2 , …, an } з повтореннями складу (k 1 , k 2 , …, 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).