ћатематика > ѕочатки комб≥наторики

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

2. Ќехай m однакових кульок розкладаютьс¤ по n р≥зних ¤щиках так, що у першому ¤щику k1 кульок, у другому Ц k2 кульок, Е, у n-му Ц kn кульок, причому m=k1+k2+Е+kn. ѕронумеруЇмо ¤щики в≥д 1 до n. «адамо розпод≥ленн¤ кульок ¤к функц≥ю, ¤ка ставить у в≥дпов≥дн≥сть номеру ¤щика к≥льк≥сть кульок у ньому. ќтже, маЇмо посл≥довн≥сть (k1, k2, Е, kn), що Ї складом. ѕрипишемо кожн≥й кульц≥ номер њњ ¤щика ≥ утворимо посл≥довн≥сть номер≥в вигл¤ду

(1, Е, 1, 2, Е, 2, Е, n, Е, n).

123 123 123

k1 k2 Е kn

як бачимо, множиною елемент≥в, ¤кими утворюЇтьс¤ комб≥нац≥¤ з повторенн¤ми, тут Ї {1, 2, Е, n}.

 омб≥нац≥њ по m елемент≥в множини {a1, a2, Е, an} з повторенн¤ми складу (k1, k2, Е, kn) можна взаЇмно однозначно поставити у в≥дпов≥дн≥сть посл≥довн≥сть довжини m+n-1 ≥з m "1" ≥ n-1 "0":

(1, Е, 1, 0, 1, Е, 1, 0, Е, 1, Е, 1).

123 123 123

k1 k2 Е kn

“ак≥й посл≥довност≥, у свою чергу, взаЇмно однозначно в≥дпов≥даЇ комб≥нац≥¤ номер≥в м≥сць у ц≥й посл≥довност≥, на ¤ких розташован≥ 1 (або 0).  ≥льк≥сть таких комб≥нац≥й Ї , що й Ї к≥льк≥стю вс≥х можливих комб≥нац≥й по m елемент≥в n-елементноњ множини з повторенн¤ми.

6. ‘ормули включень ≥ виключень

 ≥льк≥сть елемент≥в об'Їднанн¤ двох множин, що не перетинаютьс¤, Ї сумою њх к≥лькостей. јле ¤кщо множини перетинаютьс¤, то елементи перетину при цьому додаванн≥ к≥лькостей враховуютьс¤ дв≥ч≥. “ому њх к≥льк≥сть треба один раз в≥дн¤ти:

|AÈB|=|A|+|B|-|AÇB|. (*)

ѕри обчисленн≥ |AÈBÈC| додаванн¤ |A|+|B|+|C| веде до того, що елементи кожного з перетин≥в |AÇB|+|BÇC|+|AÇC| враховуютьс¤ дв≥ч≥, тому њх треба по одному разу в≥дн¤ти. якщо перетин AÇBÇC порожн≥й, то в результат≥ кожний елемент об'Їднанн¤ враховано по одному разу, ≥ все гаразд. якщо н≥, то в результат≥ елементи цього перетину трич≥ додаютьс¤ ≥ трич≥ в≥дн≥маютьс¤, тобто у вираз≥

|A|+|B|+|C|Ц|AÇB|Ц|BÇC|Ц|AÇC|

не врахован≥. ќтже, њх треба додати:

|AÈB|=|A|+|B|+|C|Ц|AÇB|Ц|BÇC|Ц|AÇC|+|AÇBÇC|. (**)

¬ирази (*), (**) навод¤ть на припущенн¤, що в загальному випадку об'Їднанн¤ n множин A1, A2, Е, An

|A1ÈA2ÈЕÈAn|=|A1|+|A2|+Е+|An|Ц|A1ÇA2|Ц|A1ÇA3|ЦЕЦ|An-1ÇAn|+
+|A1ÇA2ÇA3|+Е+|An-2ÇAn-1ÈAn|ЦЕ+(-1)n+1|A1ÇA2ÇЕÇAn|. (1)

як бачимо, к≥лькост≥ елемент≥в ус≥х можливих перетин≥в непарноњ к≥лькост≥ множин додаютьс¤, а парноњ Ц в≥дн≥маютьс¤. ‘ормула (1) називаЇтьс¤ формулою включень ≥ виключень.

ƒоведенн¤ формули (1) можна провести з використанн¤м ≥ндукц≥њ за n, але тут ми його не наводимо.

÷¤ формула даЇ змогу за к≥лькост¤ми елемент≥в у кожн≥й з множин, в ус≥х можливих њх перетинах по дв≥, по три ≥ т.д. множини обчислити к≥льк≥сть елемент≥в об'Їднанн¤.

ѕриклад. ™ група студент≥в, серед ¤ких каву п'ють 12 (це множина A), чай Ц 10 (множина B), йогурт Ц 8 (C), каву ≥ чай Ц 5 (AÇB), каву ≥ йогурт Ц 4 (AÇC), чай ≥ йогурт Ц 3 (BÇC), ус≥ три напоњ Ц 1 (AÇBÇC). “од≥ всього студент≥в у груп≥ 12+10+8-5-4-3+1=19.

«а допомогою формули (1) можна обчислити к≥льк≥сть елемент≥в де¤коњ множини U, що не належать жодн≥й з њњ п≥дмножин A1, A2, Е, An:

|U\(A1ÈA2ÈЕÈAn)|=|U|Ц|A1|Ц|A2|ЦЕЦ|An|+|A1ÇA2|+|A1ÇA3|+Е+
+|An-1 ÇAn|Ц|A1ÇA2ÇA3|ЦЕЦ|An-2ÇAn-1ÈAn|+Е+(-1)n|A1ÇA2ÇЕÇAn|. (2)

‘ормулу (2) також називають формулою включень ≥ виключень.

7. Ѕ≥ном≥альн≥ коеф≥ц≥Їнти

ќзначенн¤. Ѕ≥ном Ќьютона Ц це вираз вигл¤ду (a+b)n.

Ѕ≥ном розкладаЇтьс¤ в суму одночлен≥в, ¤к≥ Ї добутками де¤ких степен≥в його доданк≥в a ≥ b. Ўкол¤р≥-восьмикласники знають формули розкладу б≥нома Ќьютона в многочлен ≥з степен¤ми a ≥ b при n=2 та 3:

(a+b)2=a2+2ab+b2,

(a+b)3=a3+3a2b+3ab2+b3.

—пробуЇмо розкласти (a+b)n в многочлен у загальному випадку n. «апишемо його у вигл¤д≥, пронумерувавши дужки:

1 2 Е n

(a+b)(a+b)Е(a+b).

ќчевидно, що кожний доданок м≥стить n множник≥в Ц k множник≥в a ≥ n-k множник≥в b, тобто маЇ вигл¤д akbn-k, де k£n, k³0.  ожний такий доданок взаЇмно однозначно в≥дпов≥даЇ п≥дмножин≥ номер≥в дужок, з ¤ких дл¤ утворенн¤ цього доданка ми брали множники a. “аким чином, доданк≥в akbn-k р≥вно ст≥льки, ск≥льки таких п≥дмножин, тобто =. ќтже,

(a+b)n =

 оеф≥ц≥Їнти при akbn-k називаютьс¤ б≥ном≥альними, оск≥льки записуютьс¤ в розклад≥ б≥нома (a+b)n.

Ѕ≥ном≥альн≥ коеф≥ц≥Їнти мають очевидну властив≥сть симетр≥њ:

= =..

–озгл¤немо окрем≥ випадки б≥нома Ќьютона:

при b=1 маЇмо (a+1)n = ,

при a=b=1 маЇмо (1+1)n = 2n = ,

при a= Ц1, b=1 маЇмо (Ц1+1)n = 0n = (Ц1)k.

«а останньою р≥вн≥стю, зокрема, природно означити 00 ¤к 1, сл≥дуючи за ƒоналдом  нутом [****].

«апишемо б≥ном≥альн≥ коеф≥ц≥Їнти дл¤ початкових значень n=0, 1, Е, 5 у трикутну таблицю:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

« таблиц≥ видно, що кожний елемент, ¤кий не Ї першим у своЇму р¤дку, Ї сумою елемента над ним ≥ елемента, розташованого над ним ≥ л≥воруч:

= +

÷¤ тотожн≥сть називаЇтьс¤ правилом додаванн¤. ≤снуЇ багато р≥зних њњ доведень. ќсь "лобове":

ƒоозначимо б≥ном≥альн≥ коеф≥ц≥Їнти при k<0 та k>n ¤к =0. “од≥ правило додаванн¤ справджуЇтьс¤ за будь-¤ких значень k. —користаЇмос¤ цим доозначенн¤м також ≥ дал≥, розгл¤даючи суми, в ¤ких додаванн¤ ведетьс¤ за нижн≥м коеф≥ц≥Їнтом k у виразах вигл¤ду . ÷е дозволить не записувати меж≥, у ¤ких зм≥нюЇтьс¤ k.

ƒоведемо ще одну тотожн≥сть, ¤ка називаЇтьс¤ згорткою ¬андермонда:

.

якщо зам≥нити k на k-m, а n Ц на n-m, то одержимо р≥вн≥сть

.

¬она маЇ назву тотожност≥  ош≥. ƒоведемо спочатку цю р≥вн≥сть. Ќехай Ї r д≥вчат ≥ s юнак≥в. ѕраворуч маЇмо к≥льк≥сть способ≥в вибрати з них ус≥х n ос≥б.  ожний доданок у сум≥ л≥воруч задаЇ к≥льк≥сть способ≥в вибрати n ос≥б так, щоб серед них було k д≥вчат з r ≥ n-k юнак≥в з s. ƒодаванн¤ цих к≥лькостей по вс≥х можливих значенн¤х k даЇ к≥льк≥сть вс≥х способ≥в вибрати з них ус≥х n ос≥б. ќтже, вирази л≥воруч ≥ праворуч задають одну й ту саму к≥льк≥сть, тобто р≥вн≥. якщо тепер зам≥нити назад k на k+m, а n на n+m, одержимо початкову р≥вн≥сть.

“аблиц¤ б≥ном≥альних коеф≥ц≥Їнт≥в зображаЇтьс¤ ще у вигл¤д≥ так званого арифметичного трикутника, або трикутника ѕаскал¤:

1

1 1

1 2 1

1 3 3 1

Е

–озширимо пон¤тт¤ б≥ном≥альних коеф≥ц≥Їнт≥в на д≥йсн≥ значенн¤ n. «гадаЇмо зв'¤зок м≥ж к≥льк≥стю комб≥нац≥й з n елемент≥в по k та к≥льк≥стю њх розм≥щень без повторень: = (n)k/k!, де (n)k=n(nЦ1)Е(nЦk+1). јле останн≥й добуток означений при будь-¤кому д≥йсному значенн≥ n. —л≥дуючи ƒоналду  нуту [****], зам≥сть ц≥лого n розгл¤немо д≥йсне r: (r)k=r(rЦ1)Е(rЦk+1). “од≥ за д≥йсних значень r означимо ¤к (r)k/k!.

1	2

Ќазва: ѕочатки комб≥наторики
ƒата публ≥кац≥њ: 2005-03-03 (1077 прочитано)