Definíció n egymástól megkülönböztethető elem egy sorrendjét az n elem egy (ismétlés nélküli) permutációjának nevezzük

Villamosmérnök Szak, Távoktatás

Matematika segédanyag

9. Kombinatorika 9.1. Permutációk

Definíció n – egymástól megkülönböztethet˝o – elem egy sorrendjét az n elem egy (ismétlés nélküli) permutációjának nevezzük. Tétel: n elem ismétlés nélküli permutációinak száma: Pn = n! = 1 · 2 · 3 · . . . · n. Bizonyítás: Az els˝o helyre bármelyik elemet választhatjuk – ez n lehet˝oség. Az n lehet˝oség mindegyikét n − 1-féleképpen folytathatjuk, hiszen a megmaradt elemek bármelyikét a második helyre állíthatjuk. Így az els˝o két elem kiválasztása után n (n − 1)-féle állapothoz juthatunk. Ezek mindegyikét n−2-féleképpen folytathatjuk, hiszen az els˝o két elem rögzítése után még ennyi elem áll rendelkezésre. A gondolatmenetet folytatva az összes elem elhelyezése után n (n − 1) (n − 2) · . . . · 3 · 2 · 1 számú sorrendhez jutunk. Megjegyzés: Az n! = 1 · 2 · 3 · . . . · n szorzat neve n faktoriális. Példa: Hányféleképpen rendezhet˝o sorba 3 elem? Az els˝o helyen a 3 elem bármelyike állhat. Ez 3 lehet˝oség. Ezek mindegyike kétféleképpen folytatható, mert a második helyen a megmaradó 2 elem egyike állhat. Végül a harmadik helyre a megmaradt harmadik elem kerül, tehát az el˝obbi 3 · 2 = 6 eset mindegyike csak egyféleképpen folytatható. Tehát a lehetséges sorrendek száma: 3 · 2 · 1 = 6. A fenti gondolatmenet megértését el˝osegítheti a következ˝o ábra: 1 2 3

Készítette: Vajda István

1 1 2 2 3 3

2 3 3 1 1 2

3 3 1 1 2 2

2 3 3 1 1 2

3 1 1 2 2 3

129



Példa: Hányféleképpen rendezhet˝o sorba 4 elem? Az el˝oz˝o feladat gondolatmenetéhez hasonlóan az els˝o helyre 4-féleképpen, a másodikra, 3féleképpen, a harmadikra 2-féleképpen, a negyedikre pedig csak egyféleképpen választható elem, tehát a sorrendek száma: 4 · 3 · 2 · 1 = 24.

1 2 1

1 3 1 4 2 3

2

2 4 2 1 3 4

3

3 1 3 2 4 1

4

4 2 4 3

1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4

2 2 3 3 4 4 3 3 4 4 1 1 4 4 1 1 2 2 1 1 2 2 3 3

3 4 2 4 2 3 1 4 1 3 3 4 1 2 2 4 1 4 2 3 1 3 1 2

1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4

2 2 3 3 4 4 3 3 4 4 1 1 4 4 1 1 2 2 1 1 2 2 3 3

3 4 2 4 2 3 1 4 1 3 3 4 1 2 2 4 1 4 2 3 1 3 1 2

4 3 4 2 3 2 4 1 3 1 4 3 2 1 4 2 4 1 3 2 3 1 2 1

Példák: • Egy hat f˝os társaságot 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720 féleképpen lehet sorbaállítani. • Ha egy teremben 40 szék található és éppen 40 embert kell leültetnünk úgy, hogy minden székbe pontosan egy ember ül, akkor 40! = 40 · 39 · . . . · 3 · 2 · 1 = 815915283247897734345611269596115894272000000000 féle ültetés lehetséges. • Az 1, 2, 3, 4, 5 számjegyekb˝ol pontosan 5! = 120 olyan ötjegy˝u szám képezhet˝o, amelyben a fenti öt jegy mindegyike el˝ofordul. Megjegyzés: Legyünk óvatosak a faktoriálisokkal való számolások során. 3! = 6, 4! = 24, így 3! + 4! = 30, 3! · 4! = 6 · 24 = 144, tehát egyik sem 12! = 479001600.


130



Definíció Ha n elem között vannak olyanok, amelyeket nem tudunk megkülönböztetni egymástól, akkor olyan sorrendjeiket, amelyek egymásból a nem megkülönböztethet˝o elemek felcserélésével el˝oállíthatók, azonosnak tekintjük. Az n elem egy sorrendjét ebben az esetben az n elem egy ismétléses permutációjának nevezzük. Tétel: Tegyük fel, hogy n elem közül k1 darab egyforma (nem különböztethet˝o meg), k2 darab ugyancsak egyforma, de az el˝oz˝o csoporttól megkülönböztethet˝o, k2 darab egyforma, de különbözik az el˝oz˝o két csoport mindegyikének elemeit˝ol stb. Ekkor az n n! k ,k ,...,k elem ismétléses permutációinak száma Pn1 2 r = . k1!k2! . . . kr! Példák: • Az 1, 2, 2, 3, 3, 3, 3 számjegyekb˝ol

7! = 105 különböz˝o hétjegy˝u szám írható fel. 2! · 4!

8! • Nyolc vasúti kocsi közül 4 magyar, 2 német, 1 osztrák és 1 szlovák. A kocsik = 4! · 2! 840-féle sorrendben kapcsolhatók össze egy szerelvénnyé, ha az azonos országból származó kocsikat nem különböztetjük meg.

9.2. Variációk

Definíció Egy n elem˝u halmaz elemeib˝ol képezett k elem˝u sorozatot, amelynek tagjai páronként különböznek egymástól az n elem egy (ismétlés nélküli) k-adosztályú variációjának nevezzük. Megjegyzés: Szokás a variációt olyan „kiválasztásnak” nevezni, ahol „a sorrend számít”.


131



Példák: • Tegyük fel, hogy az országban egy adott évben a különböz˝o fels˝ooktatási intézmények összesen 35 kurzust indítanak leend˝o villamosmérnökök számára. Ezek közül egy felvételiz˝o hatot választ valamilyen sorrendben. (Lényeges, hogy milyen sorrendben, hiszen a hat kurzusközül az els˝o olyanra veszik fel, amelyre elegend˝o a pontja.) Így 35 elem egy 6-odosztályú variációját adta meg. • Öt elem másodosztályú variációinak száma 5 · 4 = 20, mert a 2 elem˝u sorozat els˝o elemét 5-féleképpen, második elemét pedig 4-féleképpen választhatjuk ki.

1

2

3

4

5

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5

2 3 4 5 3 4 5 1 4 5 1 2 5 1 2 3 1 2 3 4

• Öt elem harmadosztályú variációinak száma 5 · 4 · 3 = 60, mert a 3 elem˝u sorozat els˝o elemét 5-féleképpen, második elemét 4-féleképpen, harmadik elemét pedig háromféleképpen választhatjuk ki.


132



Tétel: n elem k-adosztályú ismétlés nélküli variációinak száma: Vn,k =

n! (n − k)!

Bizonyítás: A k hosszúságú sorozat els˝o elemét n-féleképpen választhatjuk, második elemét (n − 1)-féleképpen, stb. A k-adik elemet n − k + 1-féleképpen lehet választani. Így a variációk száma: n (n − 1) (n − 2) · . . . · (n − k + 1) =

n! n (n − 1) (n − 2) · . . . · 3 · 2 · 1 = (n − k) · . . . · 3 · 2 · 1 (n − k)!

Definíció Egy n elem˝u halmaz elemeib˝ol képezett k tagú sorozatot, amelyben a halmaz bármelyik elemét többször is felhasználhatjuk az n elem egy ismétléses k-adosztályú variációjának nevezzük. Példa: A TOTÓ-n 13 mérk˝ozést megjelölünk 1-gyel, 2-vel, illetve X-szel. Tehát egy három elem˝u {1, 2, X} halmazból állítunk el˝o egy 13 tagú sorozatot. Természetesen a halmaz elemeit többször is fel lehet használni a sorozat készítésekor, tehát 3 elem 13-adosztályú ismétléses variációjáról van szó.

Tétel: (i) n elem k-adosztályú ismétléses variációinak száma: Vn,k = nk. Bizonyítás: A k hosszúságú sorozat minden elemét n-féleképpen választhatjuk így a variációk száma: n · n · . . . · n = nk . | {z } k darab

(i) Példa: A TOTÓ-n a 13 mérk˝ozésb˝ol álló tipposzlopot V3,13 = 313 -féleképpen tudjuk kitölteni.


133



9.3. Kombinációk

Definíció Egy n elem˝u halmaz egy k elem˝u részhalmazát, az n elem egy (ismétlés nélküli) k-adosztályú kombinációjának nevezzük. Megjegyzés: Ez abban különbözik a variációtól, hogy a részhalmaz elemei között nincs sorrendiség, ezért szokás azt mondani, hogy a kombináció egy „olyan kiválasztás, ahol a sorrend nem számít”.

Tétel: n elem k-adosztályú ismétlés nélküli kombinációinak száma: Cn,k =

n! k! (n − k)!

Bizonyítás: Rendeljük hozzá az n elem minden k-adosztályú (ismétlés nélküli) variációjához ugyanennek az n elemnek azt a k-adosztályú kombinációját, amely pontosan ugyanabból a k elemb˝ol áll, mint a variáció. vari a iok kombin a i ok

:::

:::

Két különböz˝o variációhoz pontosan akkor rendeljük ugyanazt a kombinációt, ha a két variáció ugyanazon k darab elemb˝ol áll, csak ezek sorrendjében különböznek. Mivel k darab elemnek Pk = k! különböz˝o sorrendje lehetséges, adott k darab elem k! variációt alkothat, de csak egyet-


134



len kombinációt. Így a variációk száma éppen k!-szor több, mint a kombinációké, azaz n!

Cn,k

Vn,k n! (n−k)! = = = k! k! k! (n − k)!

Megjegyzés: A Cn,k számokat binomiális együtthatónak szokás nevezni. ! n Jelölés: A Cn,k jelölés helyett gyakran használják az jelölést is. (Olvasd: „n alatt a k”.) k Példák: ! 5 5! = • Egy ötelem˝u halmaznak C5,3 = = 10 háromelem˝u részhalmaza van. 3 3!2! ! 90 • Az ötöslottó egy szelvényét (szabályosan) = 43949268-féleképpen lehet kitölteni. 5 A kitöltés valójáben egy 90-elem˝u halmaz 5-elem˝u részhalmazának kiválasztását jelenti.


135

Definíció n egymástól megkülönböztethető elem egy sorrendjét az n elem egy (ismétlés nélküli) permutációjának nevezzük

Recommend Documents