A diszkrét matematika egyik ága az elemi kombinatorika, most ezzel fogok foglalkozni.
Mivel állunk szemben, mi a feladat, ennek eldöntés e az első lépés! Kombinatorika logika, permutáció, variáció
A kombinatorikai alapfeladatok lényege az, hogy bizonyos elemeket sorba rendezünk, vagy néhányat kiválasztunk belőlük, és esetleg utána rendezzük sorba. Minden ilyen feladatnál fellehet tenni a következő kérdéseket.
Sorba kell-e rendezni az összes elemet? (Permutáció.)
Ki kell-e választani közülük valamennyit? (Variáció vagy kombináció.)
Az elemek különbözőek, vagy azonosak is vannak közöttük? (Ismétlés nélküli vagyismétléses.)
A kiválasztás után számít a sorrend vagy nem? (Variáció vagy kombináció.)
A következőkben a fenti felsorolás zárójelben lévő fogalmait fogjuk pontosan definiálni
Permutáció = sorbarendezés:
Jellemző sajátossága, hogy az összes elemet felhasználod.
Akkor ismétléses, ha egy elem többször előfodul a sorbarendezendők között, akkor le kell osztani az eredményt annyi faktoriálissal, ahányszor előfordul az az elem. ( az összes elemmel el kell játszani ezt).
Ismétlés nélküli permutációra példa, ha 3 ember elmegy a moziba és szeretnénk tudni hány féle képen (sorrend) tudnak leülni
321
312
231
213
123
132
6 féle képpen ülhetnek le
A megoldás 5! (faktoriális) 1*2*3=6
Kombináció:
Jellemzője, hogy egy halmazból ki kell választani elemeket ( általában nem az összeset), de a kiválasztás sorrendje egyáltalán nem számít. Ismétléses, ha egy elemet többször is választhatsz. Példa: ötöslottó
Variáció:
Jellemzője, hogy egy halmazból választasz ki elemeket ( általábannem az összeset), de fontos a kiválasztás sorrendje. Ismétléses, ha egy elemet többször választhatsz. Példának most a Joker húzás jut eszembe.
permutáció
Rakd sorba az alábbi 10 betűt: [10 betű felsorolva]
A felsorolt 10 betű egy permutációját kapod meg így
kombináció
Válassz ki 4-et az alábbi 10 betűből: [10 különböző betű felsorolva]
Amit kiválasztottál, az egy 4 elemű kombinációja a felsorolt 10 betűnek
variáció
Írj fel egy 4 betűs (esetleg értelmetlen) "szót" az alábbi 10 betűből: [10 különböző betű felsorolva]
Amit kiválasztottál z egy 4 elemű variációja a felsorolt 10 betűnek.
A kombináció és a variáció esetében akkor beszélünk ismétlésesről, ha a kiválasztottak között megengedjük, hogy valamelyik többször is szerepeljen. A permutáció esetében pedig akkor, ha a megadott 10 betű között vannak azonosak.
1, Van 10 fiú és 10 lány. Ki akarunk választani kozülük 3 fiút és 4 lányt. Hányféleképp tehetjük ezt meg?
2, Van 10 fiú és 10 lány. Ki akarunk választani kozülük 3 fiút vagy 4 lányt. Hányféleképp tehetjük ezt meg?
Hányféleképpen lehet sorba rakni n különböző dolgot?
P=1·2·...·(n-1)·n=n!
például: hányféle sorrendben ülhet le egymás mellé 5 ember?
5!=1·2·3·4·5=120
Ismétléses permutációra példa ha egyformák vannak benne, mint a 3 alma 2 körte esete
54321
5!/3!*2!=10
Ismétléses permutáció fogalma
Hányféleképpen lehet sorba rakni n dolgot, ha köztük n1, n2, ..., nk darab egyforma van?
(n1+n2+...+nk=n)
például: hányféleképpen lehet sorba rakni 2 kék és 3 piros golyót?
választunk néhányat a dolgokközül (nem számít a sorrend) ismétlés nélküli kombináció
Hányféleképpen lehet n különböző dologból kiválasztani k darabot, ha nem számít a kiválasztás sorrendje és mindegyiket csak egyszer választhatjuk?
például: lottó (90 számból választunk ötöt, nem számít a kiválasztás sorrendje)
Ismétléses kombináció fogalma
Hányféleképpen lehet n különböző dologból kiválasztani k darabot, ha nem számít a kiválasztás sorrendje és egy dolgot többször is választhatunk?
például: a lottóhúzásnál minden alkalommal visszateszem a kihúzott golyót, így egy szám
többször is szerepelhet választunk néhányat a dolgok közül és sorba rakjuk őket
Ismétlés nélküli variációra példa, az úszóverseny első három helyezetjeinek sorrendje
12345678
8*7*6=336
Ismétlés nélküli variáció fogalma
Hányféleképpen lehet n különböző dologból kiválasztani k darabot, ha számít a kiválasztás sorrendje és
mindegyiket csak egyszer választhatjuk?
Másik például: egy 10 csapatos
bajnokságban hányféle sorrend alakulhat ki a dobogón?
Ismétléses variációra jó példa a totó
1,2,3,4,5,6,7,8,9,10,11,12,13,14
3 féle lehet 1,x,2
Tehát 3 14. hatványa a megoldás, ami 4.782.969 variáció.
Ismétléses variáció fogalma
Hányféleképpen lehet n különböző dologból kiválasztani k darabot, ha számít a kiválasztás
sorrendje és egy dolgot többször is választhatunk?
V=nk
például: totó (a 3 lehetséges végeredményből (1, 2, x) képezünk 14 (13+1) hosszúságú sorozatokat)
3 14=4782969
A feladatok jelentős része vegyes típusú, ahol nem a fenti képleteket, hanem a képletek
megalkotásához alkalmazott gondolatmenetet kell használni; vagy egyértelműen valamelyik fenti
típusba tartozik, de "józan paraszti ésszel", képlet használata nélkül egyszerűbben megoldható.
Például:
- hány 5 jegyű szám készíthető az 1, 2, 3, 4, 5 számjegyek egyszeri felhasználásával?
(ismétlés nélküli permutáció)
az első helyre bármelyik számot választhatom az 5 közül, a második helyre a maradék 4-ből, a
harmadikra a maradék 3-ból választhatok stb., így összesen 5·4·3·2·1=120
szám készíthető
- hány 3 jegyű szám készíthető az 1, 2, 3, 4, 5 számjegyek egyszeri felhasználásával?
(ismétlés nélküli variáció)
az első helyre bármelyik számot választhatom az 5 közül, a második helyre a maradék 4-ből, a
harmadikra a maradék 3-ból választhatok, azaz összesen 5·4·3=60 szám készíthető
- hány 3 jegyű szám készíthető az 1, 2, 3, 4, 5 számjegyekből, ha mindegyiket
többször is felhasználhatom?
(ismétléses variáció)
mindhárom helyre bármelyik számjegy kerülhet, így összesen 5·5·5=125 szám készíthető
- hány 4 jegyű szám készíthető a 0, 1, 2, 3, 4 számjegyek egyszeri felhasználásával?
(vegyes feladat)
az első helyre 4 számjegyből választhatok (0 nem állhat az első helyen), a második helyre a
maradék 4-ből bármelyik kerülhet (itt már lehet 0), a harmadikra a maradék 3-ból bármelyik stb.,
azaz összesen 4·4·3·2=96 szám készíthető
- hány 4 jegyű szám készíthető a 0, 1, 2, 3, 4 számjegyekből, ha mindegyiket többször is
felhasználhatom?
(vegyes feladat)
az első helyre 4 számjegyből választhatok (0 nem állhat az első helyen), a második helyre
bármelyik kerülhet (itt már lehet 0), a harmadikra szintén bármelyik stb., azaz összesen
4·5·5·5=500 szám készíthető
Típusfeladatok:
Egy 10 tagú társaságban mindenki mindenkivel kezet fog. Hány kézfogás történik?
(ismétlés nélküli kombináció)
1. megoldás: az első ember 9 másikkal fog kezet, a második 8 emberrel (az elsővel való kézfogását
az első embernél már beszámítottuk), a harmadik 7 emberrel stb., azaz összesen
9+8+7+6+5+4+3+2+1=45 kézfogás történik.
2. megoldás: minden ember 9 másikkal fog kezet, ez összesen 9·10=90. Így azonban minden
kézfogást duplán számolunk (mindkét "kézfogónál" beleszámítjuk), tehát kettővel el kell osztani,
azaz összesen 90/2=45 kézfogás történik.
3. megoldás: annyi kézfogás történik, ahányféleképpen kiválaszthatunk 2 embert a 10-ből. Azaz "10
alatt a 2"=10!/(2!·8!)=45
Egy 12 csapatos labdarúgótornán hányféle sorrend alakulhat ki a dobogón?
(ismétlés nélküli variáció)
Az első helyre a 12 csapatból bármelyik kerülhet, a második helyre a maradék 11-ből, a harmadikra
a maradék 10-ből választhatunk, azaz összesen 12·11·10=1320-féle sorrend lehetséges.
Egy 5 házból álló házsort szeretnénk kifesteni. Hányféle kifestés létezik, ha 4-féle festékünk van?
(Egy házhoz csak egyféle festéket használunk, a festékeket nem lehet keverni.)
(ismétléses variáció)
Mind az 5 házhoz használhatjuk bármelyiket a 4-féle festék közül, azaz összesen 4·4·4·4·4=1024
lehetőség van.
Egy 5 házból álló házsort szeretnénk kifesteni. Hányféle kifestés létezik, ha 7-féle festékünk van, és
minden háznak különböző színűnek kell lenni?
(Egy házhoz csak egyféle festéket használunk, a festékeket nem lehet keverni.)
(ismétlés nélküli variáció)
Az első házhoz 7-féle festékből választhatunk, a másodikhoz a maradék 6-ből, a harmadikhoz a
maradék 5-ből stb., azaz összesen 7·6·5·4·3=2520 lehetőség van.
Egy 5 házból álló házsort szeretnénk kifesteni. Hányféle kifestés létezik, ha 4-féle festékünk van, és a
szomszédos házak nem lehetnek egyforma színűek?
(Egy házhoz csak egyféle festéket használunk, a festékeket nem lehet keverni.)
(vegyes feladat)
Az első házhoz 4-féle festékből választhatunk, a másodikhoz a maradék 3-ből, a harmadikhoz
szintén 3-ből (a második ház színét nem választhatjuk, de az elsőét igen), az összes továbbihoz is 3
színből, azaz összesen 4·3·3·3·3=324 lehetőség van.
Hányféleképpen lehet sorba rakni egy fehér, egy zöld, egy kék, egy piros és egy sárga golyót?
(ismétlés nélküli permutáció)
Az első helyre 5 színből választhatunk, a másodikra a maradék 4-ből, a harmadikra a maradék 3-ből
stb., azaz összesen 5·4·3·2·1=120 lehetőség van.
Hányféleképpen lehet sorba rakni egy fehér, két zöld és három kék golyót?
(ismétléses permutáció)
Ha mind a 6 golyó különböző színű lenne, akkor 6·5·4·3·2·1=720 lehetőségünk volna. A két zöld
golyót 2·1=2, a három kéket pedig 3·2·1=6-féleképpen lehet sorba rakni. Mivel az azonos színűeket
egyformának tekintjük, az egymás közötti sorrendjeiket nem különböztetjük meg, tehát a 720
lehetőséget 2-vel, ill. 6-tal el kell osztani, azaz összesen 720/(2·6)=60 lehetőség van.
ISmétlés nélküli kombinációra példa a lottó
35 számból 7 (külömböző) számot választunk ki
90
5
Kilépés a tartalomba
Matek Neked!
Főoldal
Blog
Magántanár vagyok, hirdetni szeretnék!
Kombináció
A permutáció és a variáció mellett a kombinatorika harmadik fontos fogalma a kombináció. Az alábbiakban megnézzük, hogy mi az az ismétléses kombináció, mi az az ismétlés nélküli kombináció és mi a kettő között a különbség. A definíciók mellett pedig mindegyikre hoztunk több példát is.
Ismétlés nélküli kombináció
Legyen n egymástól különböző elemünk. Ha ezekből k (k \leq n) elemet kiválasztunk minden lehetséges módon úgy, hogy a kiválasztott elemek sorrendjére nem vagyunk tekintettel, akkor az n elem k-ad osztályú ismétlés nélküli kombinációját kapjuk. Jelölése: C_{n}^{k}.
Most már tudjuk, hogy pontosan mit is értünk ismétlés nélküli kombináción, azonban azt még nem láttuk, hogy hogyan lehet ezt kiszámolni. Ebben a következő tétel lesz segítségünkre:
Az n elem k-ad osztályú összes ismétlés nélküli kombinációjának száma n alatt a k:
C_{n}^{k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)}{k \cdot (k-1) \cdot \ldots \cdot 2 \cdot 1} = \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}.
Most pedig nézzük meg néhány példán keresztül, hogyan tudjuk felhasználni a fent leírtakat.
Ismétlés nélküli kombináció segítségével megoldható feladatok
Feladat: Határozzuk meg, hogy hányféleképpen lehet kitölteni egy ötöslottó szelvényt!
Segítség: Az ötöslottó számok kiválasztásánál 90 számból kell kiválasztanunk 5 számot. A kiválasztás során a sorrend nem számít, de egy számot csak egyszer választhatunk, így ismétlés nélküli kombinációról beszélünk.
Megoldás: Esetünkben 90 szám közül kell kiválasztanunk 5 számot, vagyis n = 90 és k = 5. Tehát a C_{90}^{5}-t keressük. A képletbe behelyettesítve a megoldás:
C_{90}^{5} = \frac{90 \cdot 89 \cdot 88 \cdot \ldots \cdot 86}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{90!}{5! \cdot 85!} = \binom{90}{5}=43949268.
Nézzük most meg a következő feladatot.
Feladat: Egy ötfős társaságban mindenki kezet fog mindenkivel. Hány kézfogás történik összesen?
Segítség: A kézfogások száma megegyezik azzal, ahányféleképpen kiválaszthatunk 5 ember közül 2-t. Azaz 5 elem másodosztájú ismétlés nélküli kombinációjáról beszélünk.
Megoldás: n=5 és k=2. A képletbe behelyettesítve a megoldás:
C_{5}^{2} = \binom{5}{2} = \frac{5!}{2! \cdot 3!} = 10.
Ismétléses kombináció
Legyen n egymástól különböző elemünk. Ha ezekből k elemet kiválasztunk minden lehetséges módon úgy, hogy a kiválasztott elemek sorrendjére nem vagyunk tekintettel és ugyanazt az elemet többször is kiválaszthatjuk, akkor az n elem k-ad osztályú ismétléses kombinációját kapjuk. Jelölése: C_{n}^{k,i}.
Az ismétlés nélküli kombinációhoz hasonlóan ebben az esetben is a kiszámításra vonatkozó tétellel folytatjuk, majd pedig megnézünk egy feladatot.
Az n elem k-ad osztályú összes ismétléses kombinációjának száma n+k-1 alatt a k:
C_{n}^{k,i} = \frac{(n+k-1)!}{k! \cdot [(n+k-1)-k)]! } = \frac{(n+k-1)!}{k! \cdot (n-1)! } = \binom{n+k-1}{k}.
Ismétléses kombináció segítségével megoldható feladatok
Feladat: Egy 24 fős osztályban kisorsolunk 5 könyvet. Minden könyv egyforma és egy ember több könyvet is kaphat. Hányféleképpen tehetjük ezt meg?
Segítség: A feladatban 24 ember közül akarunk kiválasztani 5 embert úgy, hogy egy embert többször is választhatunk. A könyvek mind egyformák, vagyis ismétléses kombinációról van szó.
Megoldás: n= 24 és k=5. A megoldás így:
C_{24}^{5,i} = \frac{(24+5-1)!}{5! \cdot [(24+5-1)-5)]! } = \frac{(24+5-1)!}{5! \cdot (24-1)! } = \frac{28!}{5! \cdot 23!} = \binom{24+5-1}{5} = \binom{28}{5}=98280.
Másik példa egy 10 fős társaságban 4 könyvet osztunk szét. Hányféleképpen tehetjük meg, ha minden könyv
különböző, és mindenki csak egy könyvet kaphat?
(ismétlés nélküli variáció)
Az első könyvet a 10 ember közül bárkinek adhatjuk, a második könyvet a maradék 9, a harmadikat
a maradék 8 közül bármelyiknek stb., azaz összesen 10·9·8·7=5040 lehetőség van.
Egy 10 fős társaságban 4 könyvet osztunk szét. Hányféleképpen tehetjük meg, ha a könyvek
egyformák, és mindenki csak egy könyvet kaphat?
(ismétlés nélküli kombináció)
A kérdés az, hogy hányféleképpen választhatjuk ki a 10 ember közül azt a négyet, aki könyvet kap
(mivel a könyvek egyformák, a kiválasztás sorrendje nem számít). Összesen "10 alatt a 4" = =
10!/(4!·6!)=210 lehetőség van.
Egy 10 fős társaságban 4 könyvet osztunk szét. Hányféleképpen tehetjük meg, ha minden könyv
különböző, és mindenki több könyvet is kaphat?
(ismétléses variáció)
Mind a 4 könyvet kaphatja a 10 közül bármelyik ember, azaz összesen 10·10·10·10=10000
lehetőség van.
Egy 10 fős társaságban 4 könyvet osztunk szét. Hányféleképpen tehetjük meg,
ha a könyvek egyformák, és mindenki több könyvet is kaphat?
(ismétléses kombináció)
1. megoldás: az ismétléses kombináció képlete nem érettségi anyag, de a következő gondolatmenet
alapján megalkothatjuk az általános képletét. Szemléltessük a kiosztást a következőképpen: a 10
embert jelképezze 10 fehér golyó, a 4 könyvet pedig 4 fekete golyó. Rakjuk sorba a 10 fehér golyót,
és mindegyik elé tegyünk annyi feketét, ahány könyvet kap a neki megfelelő ember. Pl. az első
ember 1 könyvet kap, a negyedik kettőt, a tizedik pedig egyet: ●○○○●●○○○○○○●○
a lerakási szabályunk miatt a 10. fehér golyó után semmiképpen nem állhat fekete, így azt el is
hagyhatjuk: ●○○○●●○○○○○○●
A könyveket tehát annyiféleképpen oszthatjuk ki, ahányféleképpen lehet 9 fehér és 4 fekete golyót
sorba rendezni. Ezt 13!/(9!·4!)=715-féleképpen tehetjük meg (ha az összes golyó különböző színű
lenne, akkor 13·12·...·2·1=13! lehetőség volna. A 9 fehér golyót 9·8·...·2·1=9!, a 4 feketét pedig
4·3·2·1=4!-féleképpen lehet sorba rendezni. Mivel az azonos színűeket egyformának tekintjük, az
egymás közötti sorrendjeiket nem különböztetjük meg, tehát a 13! lehetőséget el kell osztani 9!-sal
és 4!-sal).
2. megoldás: Vegyük sorra az összes lehetőséget:
Ha mind a 4 könyvet ugyanaz az ember kapja, akkor 10-féleképpen oszthatjuk ki.
Ha egy ember kap 3 könyvet, egy másik pedig 1-et, akkor 90-féleképpen oszthatjuk ki: a 3-
könyvest 10, az 1-könyvest pedig a maradék 9 emberből választhatjuk ki, azaz összesen 10·9=90
lehetőség van.
Ha 2 ember kap 2-2 könyvet, akkor 45-féleképpen oszthatjuk ki :"10 alatt a 2"= =10!/(2!·8!)=45-
féleképpen választhatjuk a 10-ből azt a 2 embert, aki könyvet kap.
Ha 4 ember kap 1-1 könyvet, akkor 210 lehetőség van :"10 alatt a 4"=10!/(4!·6!)=210-féleképpen
választhatjuk ki a 10-ből azt a 4 embert, aki könyvet kap.
Ha egy ember kap 2 könyvet, 2 pedig 1-1 könyvet, akkor 360 lehetőségünk van: a 2-könyvest 10
emberből választhatjuk ki, a két 1-könyvest pedig a maradék 9-ből ("9 alatt a 2"=9!/(2!·7!)=)36-
féleképpen, azaz összesen 10·36=360-féleképpen választhatjuk ki a 3 emberünket.
Összesen tehát 10+90+45+210+360=715 lehetőség van.
Példa
4 üveget 5 rekeszbe hányféleképpen rakhatunk bele?
kiválasztás 5 elem 4 ismétlés nélküli kombináció!
Ismétlés nélküli variáció n különböző elem közül k elemet kell kiválasztani (k ≤ n). Egy elem csak egyszer választható, a sorrend számít. 4 elemből {a,b,c,d} kettőt választva:
Ismétléses variáció
n különböző elem közül k elemet kell kiválasztani. Egy elem töbször is kiválasztható, a sorrend számít.
A különböző kiválasztások száma:4 elemből {a,b,c,d} ki kell választani kettőt, úgy hogy az elemek ismétlődhetnek:
Az összes lehetséges eset száma tehát:
Binomiális tétel
Ismétlés nélküli permutáció
n különböző elemet kell az összes lehetséges módon sorba rendezni.
Pn=n!
Ismétléses permutáció
n olyan elemet kell sorba rendezni az összes lehetséges módon, amelyek között ismétlődő elemek is vannak. Az ismétlődő elemek száma:
7 elemet: {a,a,a,a,b,b,c} elem sorbarakása esetén láthatjuk hogy az első elem négyszer, a második elem kétszer ismétlődik:
Az összes lehetséges rendezés száma tehát:
Ismétlés nélküli kombináció
n különböző elem közül k elemet kell kiválasztani (k ≤ n). Egy elem csak egyszer választható, a sorrend nem számít.
A különböző kiválasztások száma:5 elemből {a,b,c,d,e} kettőt választva:
Ismétléses kombináció
n különböző elem közül k elemet kell kiválasztani. Egy elem töbször is kiválasztható, a sorrend nem számít.
A különböző kiválasztások száma:4 elemből {a,b,c,d} ki kell választani kettőt, úgy hogy az elemek ismétlődhetnek:
Az összes lehetséges eset száma tehát:
Ismétlés nélküli variáció
n különböző elem közül k elemet kell kiválasztani (k ≤ n). Egy elem csak egyszer választható, a sorrend számít.
A különböző lehetőségek száma:4 elemből {a,b,c,d} kettőt választva:
Fogalmak
Faktoriális tétel!
Binominális tétel!
Szitaformula!
Polinominális tétel!
Nincsenek megjegyzések:
Megjegyzés küldése