Sokszínű matematika 11.

4. Binomiális együtthatók, ismétléses kombináció
Algebrában tanultuk kéttagú összegek négyzetét, köbét. Most vizsgáljuk ezt általánosabban.
1. példa
Figyeljük meg a kéttagú összeg hatványaiban a tagok együtthatóit. Mit állapíthatunk meg?
Megoldás
Megfigyelhetjük, hogy a kéttagú összeg hatványaiban a tagok együtthatói a Pascal-háromszög megfelelő soraiban levő számok.
kéttagú összeg hatványai Pascal-háromszög

Az ( a + b ) 4 = ( a + b )·( a + b )·( a + b )·( a + b ) szorzás elvégzése során úgy kapunk egy tagot, hogy mindegyik tényezőből vagy a -t vagy b -t kiválasztjuk, és összeszorozzuk őket. Így minden tagban a és b kitevőjének összege 4 , és a választási lehetőségek száma adja a megfelelő együtthatót.
a 4 -t úgy kapunk, ha 4 tényezőből az a -t választjuk és 0 tényezőből választjuk a b -t, és ezeket szorozzuk össze. Ezt = 1 -féleképpen tehetjük meg.
a 3 b -t úgy kapunk, hogy 3 tényezőből az a -t választjuk és 1 tényezőből a b -t, ezt = 4 -féleképpen tehetjük meg.
a 2 b 2 -t úgy kapunk, hogy 2 tényezőből a -t választjuk és 2 tényezőből a b -t, ezt = 6 -féleképpen tehetjük meg.
ab 3 -t úgy kapunk, hogy 1 tényezőből a -t választjuk és 3 tényezőből a b -t, ezt = 4 -féleképpen tehetjük meg.
b 4 -t úgy kapunk, hogy 0 tényezőből az a -t választjuk és 4 tényezőből a b -t, ezt = 1 -féleképpen tehetjük meg.
Ez alapján
Általánosan is igaz a következő:
Binomiális tétel:
binomiális tétel
Az ábrán látható a Pascal-háromszög 12 . századi kínai ábrázolása. Ez alapján nevezhetnék Csu Si-csie-háromszögnek is.
Bizonyítás
Az ( a + b ) n -t írjuk fel n tényezős szorzatként:
A szorzás elvégzése során úgy kapunk egy tagot, hogy mindegyik tényezőből vagy a -t vagy b -t kiválasztjuk, és összeszorozzuk őket. Így a és b kitevőjének összege minden tagban n .
a n k b k -t úgy kapunk, ha n k tényezőből az a -t választjuk, k tényezőből választjuk a b -t, és ezeket szorozzuk össze. Ezt -féleképpen tehetjük meg, ezért ez lesz az a n k b k együtthatója a hatvány összeg alakjában.
A kéttagú összeg hatványaiban a tagok együtthatóit binomiális együtthatóknak nevezzük a binom = kéttag szó alapján.
Megjegyzés: A binomiális együtthatókat Indiában már a Kr. e. 2 . században alkalmazták a sakkjátékkal kapcsolatos kombi­natorikai feladatok megoldására, és a 12 . századra már ismerték a binomiális tételt is.
Az összeg mindig
2 hatvány.
2. példa
A Pascal-háromszögben soronként számítsuk ki az összeget, ha
a)
a számok közé mindenhova + jelet írunk.
b)
a számok közé felváltva - majd + jelet írunk.
Magyarázzuk meg a szabályosságot!
Megoldás (a)
Az a) rész 5. sorára vonatkozó egyenlőség indoklásához írjuk fel a binomiális tételt a = 1 , b = 1 , n = 5 esetre:
Megoldás (b)
A váltakozó előjelű összeg
mindig 0 .
Minden második sorban a szimmetria miatt nyilvánvalóan 0 az összeg.
A b) rész 5. sorára vonatkozó egyenlőség indoklásához írjuk fel a binomiális tételt a = 1 , b = –1 , n = 5 esetre:
Ezzel a módszerrel a fenti szabályosság általánosan is igazolható.
Ha tetszőleges n1 egész kitevőre a = 1 és b = 1 esetre, majd
a = 1 és b = –1 esetre felírjuk a binomiális tételt, megkapjuk a binomiális együtthatókra vonatkozó következő tételt:
Tétel: Minden n 1 egész számra:
binomiális együtthatók összege
3. példa
a)
Hány 3 elemű részhalmaza van egy 5 elemű halmaznak?
b)
Hány részhalmaza van egy 5 elemű halmaznak?
c)
Hány részhalmaza van egy n elemű halmaznak?
Felhasználjuk, hogy a halmazokban az elemek sorrendje nem számít.
Megoldás (a)
A halmaz 5 eleme közül 3 -at kell kiválasztani a részhalmazba úgy, hogy az elemek választásának sorrendje nem számít, ezt = 10 -féleképpen tehetjük meg.
Tehát egy 5 elemű halmaznak darab 3 elemű részhalmaza van.
Megoldás (b)
I. módszer
Az 5 elemű halmaz részhalmazainak száma annyi, ahány 0, 1, 2, 3, 4 vagy 5 elemű részhalmaza van összesen.
0 elemű részhalmaz darab van, ez az üres halmaz.
1 elemű részhalmaz darab van, egy elemet 5 -féleképpen választhatunk.
2 elemű részhalmaz ugyanannyi van, mint 3 elemű, .
4 elemű részhalmaz annyi van, ahányféleképpen 4 -et kiválaszthatunk vagy egy elemet kihagyhatunk:
5 elemű részhalmaz darab van, ez maga a halmaz. Így az 5 elemű halmaz részhalmazainak száma összesen:
II. módszer
Egy részhalmaz kiválasztását úgy végezzük, hogy a kiválasztott elemek alá + jelet írunk, a többi elem alá jelet. Így a halmaz minden eleme alá vagy + vagy jelet írtunk.
Az 5 elemű { a ; b ; c ; d ; e } halmaz részhalmazai például:
a + – + – – jelsorozatnak megfelelően { a ; c } ,
a – – + + – jelsorozatnak megfelelően { c ; d } ,
a + + – + + jelsorozatnak megfelelően { a ; b ; d ; e } .
Mivel minden részhalmazhoz egyértelműen tartozik egy jelsorozat, és minden jelsorozathoz egyértelműen tartozik egy részhalmaz, a halmaznak ugyanannyi részhalmaza van, ahányféleképpen az elemei alá + vagy jelet írhatunk.
Minden elemnél két lehetőség közül választhatunk, így a lehetséges jelsorozatok száma, azaz az 5 elemű halmaz részhalmazainak száma: 2 5 = 32 .
Az 5 elemű halmaz részhalmazainak számára a két módszerrel ugyanazt az eredményt kell kapnunk, ezért
Megoldás (c)
I. módszer
Az n elemű halmaznak annyi k elemű részhalmaza van, ahányféleképpen n elemből k darabot ki lehet választani úgy, hogy eltekintünk a sorrendtől, ez .
Az n elemű halmaz részhalmazainak száma annyi, ahány
0, 1, 2, … , n – 1 vagy n elemű részhalmaza van összesen, ez
II. módszer
Az n elemű halmaz egy részhalmazának kiválasztásakor minden elemét vagy kiválasztjuk (alá + jelet írunk), vagy nem választjuk ki (alá – jelet írunk). Mivel minden részhalmazhoz egyértelműen tartozik egy jelsorozat, és minden jelsorozathoz egyértelműen tartozik egy részhalmaz, a halmaznak ugyanannyi részhalmaza van, ahányféleképpen az elemei alá + vagy jelet írhatunk. Minden elemnél két lehetőség közül választhatunk, így a lehetséges jelsorozatok száma, azaz az n elemű halmaz részhalmazainak száma: 2 n .
Az n elemű halmaz részhalmazainak számára a két módszerrel ugyanazt az eredményt kell kapnunk, ezért
így kombinatorikai meggondolásokkal is sikerült bizonyítani az előbbi tételt.
Továbbá igazoltuk a következőt:
Tétel: Minden n természetes szám esetén az n elemű halmaz részhalmazainak száma:
n elemű halmaz részhalmazainak száma
Ismétléses kombináció
*4. példa
Egy kertészeti újságban ötféle növényt kínálnak akciós áron, petúniát, muskátlit, rózsát, szarkalábat, levendulát. Eszter 12 növényt rendel. Hányféleképpen teheti ezt meg, ha egy növényből többet is rendelhet?
Megoldás
Egy lehetséges rendelést ábrázoltunk a táblázatban: a + jelek számával jelöltük, hogy az egyes növényekből hány darabot rendelt. Az egyforma + jelekkel biztosítjuk azt, hogy a növények rendelésének sorrendje lényegtelen, csak az a fontos, hogy melyik sorban hány darab + jel van.
virág petúnia muskátli rózsa szarkaláb levendula
darab ++++ ++++++ ++

A táblázat elhagyásával is lehetséges ez a jelölés, ha a 12 darab + jel közé 4 darab | elválasztó jelet teszünk, ezzel különítve el a növényfajtákat. Ezzel a módszerrel a táblázat szerinti rendelés
| + + + + | | + + + + + + | + +
formában írható fel.
A jelsorozat elején (vagy végén) az elválasztó jel azt jelenti, hogy az első (vagy utolsó) fajta növényből nem rendelt. Két elválasztó jel között a + jelek száma azt jelenti, hogy a megfelelő fajta növényből annyit rendelt. Ha két elválasztó jel egymás mellett van, akkor abból a növényből nem rendelt.
Minden rendelés egyértelműen leírható egy ilyen jelsorozattal, és minden jelsorozathoz egyértelműen tartozik egy rendelés. Tehát a lehetséges rendelések száma annyi, ahányféleképpen a 12 darab + jelet és a 4 darab | elválasztó jelet sorba lehet rendezni.
A 12 + 4 = 16 jel összes lehetséges sorrendje, ha közülük 12 egyforma és 4 egyforma van:
ismétléses kombináció
Definíció: Ha n -féle elemből választunk k darabot úgy, hogy a választás sorrendje nem számít és mindegyikféle elemből többet is választhatunk, az n -féle elem k tagú ismétléses kombinációját kapjuk.
Tétel: n -féle elem k tagú ismétléses kombinációinak
         száma:
A példában alkalmazott kölcsönösen egyértelmű megfelelte­tést használva n -féle elem k tagú ismétléses kombinációinak száma ugyanannyi, mint k darab + jelnek és n – 1 darab | elválasztó jelnek összes lehetséges sorrendje, azaz
Kosárba helyezve!