ћатематика > ѕочатки комб≥наторики
ѕочатки комб≥наторики—тор≥нка: 1/2
1. ѕринцип добутку ≥ принцип суми. –озм≥щенн¤ з повторенн¤ми ƒвома основними правилами комб≥наторики Ї: ѕринцип суми. якщо множина 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. 2. –озм≥щенн¤ та перестановки без повторень ќзначенн¤. –озм≥щенн¤ по 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!. 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. 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= . 5. омб≥нац≥њ з повторенн¤ми омб≥нац≥њ елемент≥в ¤коњсь множини Ц це њњ п≥дмножини. јле у множинах елементи не повторюютьс¤, тому терм≥н "комб≥нац≥њ з повторенн¤ми", що склавс¤ в математиц≥, не можна вважати вдалим. –озгл¤немо це пон¤тт¤ за допомогою перестановок ≥з повторенн¤ми. ”с≥ перестановки з повторенн¤ми з елемент≥в множини 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). 14243 14243 14243 k1 k2 Е kn ÷ю перестановку також будемо називати комб≥нац≥Їю по m елемент≥в множини {a1, a2, Е, an} з повторенн¤ми складу (k1, k2, Е, kn). ѕриклади.
Ќазва: ѕочатки комб≥наторики
ƒата публ≥кац≥њ: 2005-03-03 (1077 прочитано) |
.gif){kind=spacer}
