Cím: A kombinatorika elemei
Szerző(k):  Iván László 
Füzet: 1952/március, 33 - 50. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Két pont meghatároz egy egyenest. Három pont, mely nincsen egy egyenesen meghatároz 3 egyenest. Eddig minden közvetlenül, könnyen megszámlálható. Kérdés: 17 pont a síkban, melyek közül 3‐3 nincs egy egyenesen, hány egyenest határoz meg ? Itt most a pontpárok közvetlen megszámlálása már igen fáradságos volna és így számlálás helyett, számításhoz kell folyamodnunk. Jelen esetben a következő számítási módszer kínálkozik; számítsuk ki egy 17 szög oldalai és összes átlói számának összegét. Ismert képlet sze

17+17(17-3)2=17⋅2+17⋅142=17⋅162=136.
Ha nem akarunk kész képletekre támaszkodni, rövidebben is célhoz érünk: minden pontot összekötve a többi 16 ponttal, nyilván 17⋅16 összekötést kapunk, de ezek közül 2‐2 ugyanazt az egyenest szolgáltatja, és így az összes különböző egyenesek száma 17⋅162=136. (Ez utóbbi okoskodásnak még az az előnye, hogy térbeli pontokra is alkalmazható, míg az előbbi meggondolás térbeli pontok esetén csak síkra való vetítés közbeiktatásával vezet célhoz.) Az itt közölt két számítási módszer minden további nélkül általánosítható n pont esetére: n+n(n-3)2=n[1+n-32]=n(n-1)2. Itt tehát ha számlálással nem is, de számítással még boldogultunk.
Nem olyan egyszerű az eset, ha arról van szó, hogy n pont, melyek közül 3‐3 nem fekszik egy egyenesen, hány háromszöget határoz meg. Ha a pontokat sorszámozzuk, akkor csak a sorszámok közül kell minden lehető módon hármasokat kiválasztani. A kérdés megoldása tehát ugyanaz, mint a következőé: az 1,2,...,n természetes számokból, hány számhármas választható ki ? n=4 esetén még könnyen megszámlálható a kiválasztható 4 számhármas (123, 124, 134, 234), de ha n elég nagy szám, akkor a megszámlálás már fizikailag is lehetetlenné válik, viszont számításra most nem kínálkozik semmi az eddig tanultakból. Még komplikáltabb lesz feladatunk, ha folytatva az általánosítást azt kérdezzük, hogy n pont (melyek közül 3‐3 nincs egy egyenesen) hány k szöget (k<n) határoz meg, mert k>3 esetén már a sorrend is szerepet játszik.
Egy másik ilyenfajta feladathoz vezet pl. a következő kérdés: (x+1)10-ben mi lesz x4-nek együtthatója ? Ha hatványunkat 10 tényezős szorzatként fogjuk fel, nyilván x4 úgy keletkezik, hogy tetszőleges 4 tényezőből x-et és a többi 6 tényezőből az 1-est szorzunk össze és így nyilván annyi x4 tagot nyerünk, ahányféleképpen 4 tényezőt ki tudunk választani a 10-ből; jelöljük ezt a számot C104-zel. Ezt a C104 számú x4 tagot összevonva, x4-nek együtthatója éppen C104 lesz.
Kissé más természetű a következő feladat: hányféle öt színű zászlót állíthatunk elő 10 különböző színből ? Most nem csak az 5 szín kiválasztása játszik szerepet, de még az is számít, hogy az 5 kiválasztott színt, milyen sorrendben alkalmazzuk. Kicsiny számoknál a számlálás itt is követlenül elvégezhető (pl. 4 színből 12 féle 2 színű zászlót készíthetünk, a négy színt a, b, c, d-vel jelölve a lehetséges összeállítások: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc), de a számok növekedésével a közvetlen megszámlálás módszere itt is csakhamar csődöt mond.
Azt hisszük már ez a kevés példa is meggyőzően mutatja, hogy szükség van általánosan alkalmazható számítási módszerekre, amelyekkel a fenti és ezekhez hasonló feladatokra könnyebben megadhatjuk a választ, mint azt az eddigi példáknál láttuk. Az említett példák tulajdonságát abban fogalmazhatjuk meg, hogy azokban bizonyos szabályok szerint csoportokat alkottunk és a lehetséges csoportok számát akartuk meghatározni. Ehhez gyakran segítséget nyújt az, ha ezeket a csoportokat valamilyen rendszer szerint próbáljuk felsorolni. Az ilyen és hasonló problémákkal foglalkozó ágát a matematikának kombinatórikának nevezik. (Szokták néha magyar néven kapcsolástannak is nevezni.) A kombinatórika néhány egyszerű problémáját fogjuk az alábbiakban ismertetni.
Azokat a tárgyakat, elemeket, amelyekből csoportokat képezünk, leggyakrabban a természetes számsor számaival, vagy az abc betűivel, illetve indexekkel ellátott betűkkel jelöljük. Az elemek egy-egy csoportját füzetnek, vagy komplexionak nevezzük.
Célszerű az elemek közt megállapítani egy alapsorrendet. Az éppen említett elemeknél erre a természetes sorrend kínálkozik. Ebben az elrendezésben a később következő elemet magasabb rangúnak fogjuk nevezni minden előbb következő elemnél, pld. a 4 magasabbrangú, mint a 2, a ,,c'', mint az ,,a'', az a3, mint az a2 stb. A csoportok, füzetek közt is megállapíthatunk ezekután rangsort többféleképpen. Az egyik lehetőség a következő: az a magasabbrangú füzet, amelynél balról jobbfelé haladva előbb fordul elő magasabbrangú elem, pl. 213 magasabbrangú, mint 132, 231 magasabbrangú, mint 213. Legmagasabb rangú az a füzet, ahol alacsonyabb elem nem előz meg magasabb rangút, azaz, ha az elemek fordított sorrendben következnek egymás után pl. 321. Legalacsonyabb rangú az a füzet, melyben magasabb rangú elem nincsen alacsonyabb rangú elem előtt, azaz az elemek természetes sorrendben következnek, pl. 123.
 

Permutációk
 

Az első feladat, amit meg akarunk oldani, az, hogy adott elemeket hány különböző módon lehet sorba rakni, tehát úgy elrendezni, hogy a csoportok az összes elemeket magukban foglalják és legalább egy elem elhelyezésében különbözzenek egymástól. Ez az eljárás permutáció.
Valamely csoport összes permutációit úgy nyerhetjük, hogy felírjuk először az elemek legalacsonyabb rangú permutációját s azután jobbról bal felé haladva azt az első elemet keressük, melynek helyébe a jobbra lévőkből közvetlen magasabbat tehetünk. Az utóbbi elemet az előbbi helyére tesszük, a többit pedig ‐ a balra lévőket változatlanul hagyva ‐ természetes sorrendbe utána írjuk. Így minden lépésnél magasabb csoportot kapunk, mégpedig úgy, hogy a két csoport közé már nem iktathatunk az előbbinél magasabb, de az újabb csoportnál alacsonyabb rangú csoportot. Ennek ismételt alkalmazásával véges számú lépésben eljutunk a legmagasabb rangú csoporthoz. Pl.:
123421343124412312432143314241321324231432144213134223413241423114232413341243121432243134214321

Amint látjuk ezen komplexiókban egymástól különböző elemek fordulnak elő, kereshetjük azonban olyan füzetek számát is, melyekben egyes elemek többször fordulnak elő pl. 1134. Képezzük ezen füzet összes permutációit.
113413413114411311431413314141311314143134114311

Az előbbi ‐ mivel a füzetek azonos elemeket nem tartalmaznak ‐ ismétlés nélküli, az utóbbi ismétléses permutáció, vagy helyesebben permutáció azonos elemekkel.
Lássunk még egy-két példát.
Képezzük az 1, 2, 3, 4, 5, 6 elemeknek 326514 után a föntebb leírt felsorolásban következő 14 permutációját:
326541342156341256342165341265342516341526342561341562342615341625342651341652345126

Alkossuk meg az a, a, a, b, b, c elemeknek abacba után következő 5 permutációját:
a b b a a ca b b a c aa b b c a aa b c a a ba b c a b a   

Adott elemekből készíthető permutációk száma az elemek természetétől nyilván nem függ, csak annyiban, hogy van-e az elemek közt azonos vagy sem. Foglalkozzunk az utóbbi esettel, tehát mikor minden elem különböző. Ez esetben a permutációk száma már csak az elemek számától függ. Jelöljük P1-el az 1 elem permutációinak számát (nyilván P1=1); P2-vel két elem permutációinak számát, általában Pn-nel n elem permutációinak számát. Két elem esetén, mivel a második elem állhat az első vagy második helyen, P2=2=2⋅1. A két elem mindegyik permutációjából 3 háromelemű permutációt képezhetünk, mivel a harmadik elem állhat az első, második vagy harmadik helyen, tehát P3=3⋅P2=3⋅2⋅1=6. Minden háromelemű permutációból 4 négyeleműt csinálhatunk, úgy, hogy a negyedik elemet beiktatjuk negyedik, harmadik, második, vagy első elemként. Így P3 számú háromelemű permutációból P4=4⋅P3=4⋅3⋅2⋅1=24 számú négyelemű permutációt kapunk. Könnyen látható, hogy eljárásunk megad minden permutációt és mindegyiket csak egyszer. Ugyanígy láthatjuk be, hogy P5=5⋅P4=5⋅4⋅3⋅2⋅1=120, P6=6⋅5⋅4⋅3⋅2⋅1=720 és általában Pn=n(n-1)⋅(n-2)...3⋅2⋅1. Különböző elemekből tehát annyi permutációs füzetet alkothatunk, amennyi az 1-től az elemszámig terjedő egészszámok szorzata. A természetes számsor 1-től n-ig terjedő tagjainak szorzatát az ,,n szám faktorialisának'' nevezzük és n!-sal jelöljük (Olvasd: ,,n faktoriális'').
Ebből az is következik, hogy minden elem annyiszor áll az első, második . . . stb. helyen, ha az előtte álló elemek helyét már rögzítettük, ahányszor az utána álló elemek felcserélhetők. Tehát az 1,2,...n elemet tartalmazó füzetben minden elem (n-1)!-szor áll az első helyen; ha az első elemet rögzítettük, minden további elem (n-2)!-szor áll a második helyen . . . stb.
Oldjuk meg most a következő kérdést: a 3241 füzet hányadik permutációja az elemek természetes sorának 1234-nek a füzetek bevezetőben leírt elrendezésében ? A 3-as előtt először az 1-es állt az első helyen, még pedig 3!-szor, mert az 1 addig állt az első helyen, míg az utána következő elemeknek elértük azt a permutációját, melyben nem előz meg egy elem sem nála magasabb rangút. Ez a 3 elem legmagasabb rangú permutációja, előtte a többinek is mindnek elő kellett fordulnia. Hasonló okokból a 2 is 3!-szor állt az első helyen, tehát 2(3!) permutáció elkészítése után került a 3 az első helyre. Mikor a 3 az első helyre került, akkor utána az 1 állt és 2! számú permutációban volt az 1 a második helyen, mert ennyiféleképpen kellett az utána következő két elemet permutálni, míg csökkenő sorrendbe kerültek. Ezután 2 került a második helyre, a harmadikra 1. Ez 1! számú permutációiban állt ott, mert a maradó egy elemnek csak ennyi lehetséges sorrendje van. Ezután a harmadik helyre került a 4 és az 1 ezzel szükségképpen szintén a saját helyére került. A 3241 permutáció tehát ebben az elrendezésben a 2(3!)+1(2!)+1(1!)+1=16-odik.
Gondolatmenetünket rövidebben így foglalhatjuk össze: az első helyen álló 3 megelőz két alacsonyabb rangú elemet. E két elemnek is kellett előbb az első helyen állnia egyenként 3!-szor, mert az utánuk következő elemek 3! füzetet alkotnak mindkét esetben. A második helyen álló 2 csak az 1-est előzi meg. Előbb tehát ez állt a másik helyen 2!-szor, mert az utána következő két elem 2! füzetet alkot. A 4-es az 1-est előzi meg a harmadik helyen, ez tehát előtte állt előbb 1! számú füzetben, majd az utolsó lépésben mindkét elem a végleges helyére került.
Általában, ha ,,n''-nel jelöljük az elemek számát és k1-gyel azt a számot, amely megmutatja, hogy az első helyen álló elem hány alacsonyabbrangú elemet előz meg, ugyanígy k2,k3...kn-1-gyel a többi helyen álló elemek után következő alacsonyabb rangúak számát, akkor a permutáció sorszáma
N=k1(n-1)!+k2(n-2)!+...+kn-1⋅1!+1.

Pl. k a r ó-nak a r ó k a hányadik permutációja ? A ,,róka'' szóban az első, második, harmadik, negyedik helyen a kiindulási ,,karó'' sorrendnek sora a harmadik, negyedik, első és második betűje áll, tehát az a kérdés, hogy az 1 2 3 4 elemeknek hányadik permutációja a 3 4 1 2. A 3-as megelőzi az 1-est és 2-est, a 4-es megelőzi az 1-est és a 2-est, az 1-es nem előz meg alacsonyabb rangú elemet, tehát k1=2, k2=2, k3=0; N=2⋅3!+2⋅2!+1=12+4+1=17.
Fordítsuk most meg a kérdést, határozzuk meg pl. az 1 2 3 4 elemek 19-ik permutációját. Az 1-es, 2-es és 3-as mindegyike 3!-szor állhat az első helyen összesen 3⋅3!=18. A 19-ik permutáció tehát 4-gyel kezdődik s utána az elemek természetes sorrendben következnek, 4 1 2 3.
Mi a k á n t o r szó betűinek 451-ik permutációja ? A betűket rendre 1, 2, 3, 4, 5, 6-tal jelöljük.
Minden elem 5!=120-szor áll az első helyen. 451-et 120-szal osztva a hányados 3 marad 91. Tehát az első helyen a 4 áll.
A megmaradó 1, 2, 3, 5, 6 elemekből mindegyik 4!=24-szer áll a második helyen.
91:24=3,19
tehát a második helyen a maradó számok negyedike, az 5 áll.
Az 1, 2, 3, 6, elemek mindegyike 3!=6-szor áll a harmadik helyen.
19:6=3,1
tehát harmadik helyen a 6 áll.
A megmaradó 1, 2, 3 elemnek első permutációja 123. Tehát a 451-ik permutáció 456123, ami azt jelenti, hogy a k á n t o r szó betűinek 451-ik permutációja t o r k á n.
Ha az adott ,,n'' számú elem között ,,p'' számú egyenlő elem fordul elő, akkor az egymástól különböző permutációk száma kevesebb lesz n!-nál. Hogy szemléletessé tegyük okoskodásunkat, képzeljünk adva ,,n'' számú golyót, melyek közül ,,p'' számú egyforma fehér színű, a többi pedig legyen mind különböző színű. Kérdés, hogy hány különböző sorrendben lehet a golyókat egymás mellé tenni ? Ha minden golyó különböző színű lenne, akkor n! számú permutációt nyernénk. A jelen esetben azonban a fehér golyók felcserélése nem ad új komplexiót, a füzetek száma tehát kevesebb lesz, mint n!, mondjuk x számú komplexiót nyerünk. Különböztessük meg egymástól egy pillanatra a fehér golyókat azzal, hogy az elsőre egy pontot, a másodikra két pontot s. i. t., a p-edikre p pontot teszünk. Ha most egy bizonyos komplexióban lévő megjelölt p számú fehér golyót egymással minden lehető módon felcserélünk, akkor ebből a komplexióból p! új füzet keletkezik. Mivel az összes egymástól különböző komplexiók száma x, s mindegyikből p! új füzet keletkezik, tehát az összes új füzetek száma x⋅p! lesz. A fehér golyók pontozás révén különbözőekké váltak, tehát x⋅p! az a különböző elemből képezett permutációs füzetek számát adja, vagyis n!-t. Tehát x⋅p!=n!, ahonnan x=n!p!, vagy a szokásos jelöléssel Pnp=n!p!.
Általában, ha az n elem között p1 számú azonos (pl. fehér golyók), ezenkívül további p2 számú azonos is van (pl. fekete golyók) és további p3, p4, ..., pr számú azonos elem (p1+p2+...+pr≤n) van, akkor az előbbi okoskodásnak megismétlésével nyertük az ezekből képezhető permutációk Pnp1,p2,...pr számára a
Pnp1,p2,...,pr=n!p1!p2!...pr!
képletet.
Pl. hányféleképpen képezhető különböző csoport négy fehér, három fekete és két sárga golyóból; P94,3,2=9!4!3!2!==1⋅2⋅3⋅4⋅5⋅6⋅7⋅8⋅91⋅2⋅3⋅4⋅1⋅2⋅3⋅1⋅2=5⋅4⋅7⋅9=1260.
Hány különböző 7 jegyű szám írható fel a 0, 0, 0, 3, 5, 7, 7, számjegyekkel ?
Összesen P72,3 csoport alkotható, de a 0-val kezdődő csoportok nem alkotnak 7 jegyű számot, ezért utóbbiak száma levonandó. Az adott 7 elem permutációi között annyi fog 0-val kezdődni, ahány permutációs csoport képezhető a 0, 0, 3, 5, 7, 7, elemekből, vagyis P62,2. Tehát a keresett szám
P72,3-P62,2=7!2!3!-6!2!2!==1⋅2⋅3⋅4⋅5⋅6⋅71⋅2⋅3⋅1⋅2-1⋅2⋅3⋅4⋅5⋅61⋅2⋅1⋅2==2⋅5⋅6⋅7-3⋅2⋅5⋅6=2⋅5⋅6(7-3)=60⋅4=240.



Variációk
 

Ha adott n számú elemből úgy alkotunk csoportokat, hogy az egyes füzetekben csak egy bizonyos k számú elem forduljon elő, de ezek minden lehetséges kiválasztásban és sorrendben, akkor variációs füzeteket alkotunk, az n elem k-adosztályú variációit.
Pl. 1 2 3 elemeknek elsőosztályú variációi 1, 2, 3; másodosztályú variációi 12, 13, 21, 23, 31, 32; harmadosztályú variációi 123, 132, 213, 231, 312, 321, melyek nem mások, mint a három elem permutációi. Képezzük 1 2 3 4 elemek másod-, harmad- és negyedosztályú variációit. Az utóbbiak ismét nem egyebek, mint a 4 elem permutációi
122131411232133124121234213431244123132332421242143144131243214331424132142434431322313214211324231432144213134234324423134223413241423114224134143114232413341243121432433424321432243134214321
Ha a képzés menetét megfigyeljük, látjuk, hogy adott elemek bizonyos osztályú variációiból a közvetlen magasabb osztályúakat úgy képezhetjük, hogy az adott variációk mindegyikének végéhez a benne elő nem forduló összes többi elemeket hozzákapcsoljuk, tehát a 12-höz a 3-at és a 4-et, a 13-hoz a 2-t és a 4-et . . . stb.
Ismét világos, hogy így a magasabb osztályú variációk mindegyikét megkapjuk, ha az alacsonyabb osztályúak hiánytalanul fel voltak sorolva és mindegyiket csak egyszer.
Ennek alapján könnyű lesz a variációk számát is meghatározni. Jelöljük n elem k-ad osztályú variációinak számát Vnk-val. Haladjunk lépésről lépésre. Nézzük meg, hogy n elemből hány első, másod- . . . k-ad osztályú variációs füzet képezhető. n elemből nyilván n számú elsőosztályú variációs füzet képezhető, azaz Vn=n. Az első osztályú variációkból úgy képezhetünk másodosztályú variációs füzetet, hogy azokhoz vagyis az n elem mindegyikéhez sorra hozzáírjuk a többi (n-1) elem egy-egy elemét, tehát n elemből a n(n-1) másodosztályú variációs füzetet nyerünk; azaz Vn2=n(n-1). Ha a V számú füzet mindegyikének végére írjuk sorra a benne elő nem forduló (n-2) elem egy-egy elemét, akkor megkapjuk a harmadosztályú variációkat. Számuk tehát Vn3=n(n-1)(n-2). Ezt lépésenként folytatva kapjuk, hogy negyedosztályú variációk száma (ha k=4)
Vn4=(n-3)Vn3=n(n-1)(n-2)(n-3),Vn5=(n-4)Vn4=n(n-1)(n-2)(n-3)(n-4)


és általában
Vnk=n(n-1)(n-2)...(n-k+2)(n-k+1).
Speciálisan, ha elmegyünk az n-ed osztályú variációkig, akkor így azt nyerjük, hogy Vnn=n(n-1)(n-2)...[n-(n-1)]=n(n-1)(n-2)...3⋅2⋅1=n!=Pn, ami várható is, hiszen n elem n-ed osztályú variációi azonosak az elemek permutációival, tehát azok számát kellett megkapnunk.
Bizonyításunk így is végezhető: A Vnk számú k-ad osztályú variációs füzet mindegyikéhez hozzácsatolva a benne elő nem forduló n-k számú elem (n-k)! számú permutációs csoportját, akkor minden egyes variációs csoportból (n-k)! számú új ‐ n különböző elemet tartalmazó ‐ füzetet kapunk, vagyis Vkn számú csoportból Vnk(n-k)! csoportot. Ily módon azonban megkapjuk az n elem összes permutációit, mert hiszen minden n elemű permutációs csoport a fent adott módon keletkeztethető, és mindegyiket csak egyszer, tehát
Vkn(n-k)!=Pn,Vnk=Pn(n-k)!=n!(n-k)!=n(n-1)...(n-k+1)(n-k)(n-k-1)...3⋅2⋅1(n-k)(n-k-1)...3⋅2⋅1==n(n-1)...(n-k+1)



Most már megoldhatjuk a bevezetésben felvetett problémát: Hány 5 színű zászló készíthető 10 különböző színből ? Ott nyilván a 10 elemből alkotott 5-ödosztályú variációk számáról van szó. Tehát V105=10⋅9⋅8⋅7⋅6=30240.
Egy másik példa: Hány 5-tel osztható, csupa különböző számjegyből álló, 4 jegyű szám van ?
Itt nyilván a 10 számjegynek 4-edosztályú variációiról van szó. 5-tel azok a számok oszthatók, melyek 0, illetőleg 5-tel végződnek.
0-val annyi különböző jegyű 4-jegyű szám végződik, ahány 3-adosztályú csoport képezhető a többi 9 számjegyből, vagyis V93=9⋅8⋅7=504.
Az 5-tel végződők száma ugyanannyi, csak ki kell még vonni belőlük a 0-val kezdődő és 5-tel végződő számok számát, vagyis V82=8⋅7=56-ot.
Tehát a követelményeinknek megfelelő számok száma 2V93-V82=1008-56=952.
Hány számot kapunk akkor, ha nem tesszük fel, hogy a számjegyek mind különbözőek legyenek ? A feladat nyilván hasonlít a variációk kérdéséhez. Az utolsó jegy ismét csak 0, vagy 5 lehet, az előtte lévő 3 jegy pedig a 0, 1, 2, ..., 9 jegyekből álló bármilyen 3 elemű csoport lehet, de most egy jegy előfordulhat többször is. A feladatot kicsit bonyolítja az, hogy az első jegy nem lehet 0, az utolsó pedig csak 0, vagy 5 lehet. Azonban így is igen könnyű megoldani. Az első helyre 9 különböző jegyet írhatunk. Minden első jegy mellé 10-féleképpen írhatjuk a másodikat, tehát az első két jegyet 9⋅10-féleképpen választhatjuk. Mindegyik ilyen kétjegyű számot 10-féleképpen folytathatjuk a harmadik jeggyel, végül a kapott 9⋅10⋅10 háromjegyű szám mindegyikének a végére írhatunk 0-t vagy 5-öt, tehát ez esetben a kérdéses számok száma 9⋅10⋅10⋅2=1800.
Azt a ‐ variációhoz hasonló ‐ feladatot, amelyet fentebb említettünk ismétléses variációnak szokás nevezni. A feladat tehát ismét az, hogy adott n elemből minden lehető módon ki kell választani k számút. Két füzet akkor is különböző, ha csak a kiválasztott elemek sorrendjében különbözik, de most egy füzetben többször is ‐ akárhányszor is ‐ előfordulhat ugyanaz az elem. Az n elem k-adosztályú ismétléses variációinak számát Vni,k-val fogjuk jelölni. Ismétlés nélküli variációk nyilván nem lehetnek magasabb osztályúak, mint az elemek száma, ismétléses variációkat azonban képezhetünk akárhányad osztályúakat.
Figyeljük meg azt is, hogy az ismétléses variációk egészen más természetű problémát jelentenek, mint az ismétléses permutációk. Az utóbbiaknak inkább a következő feladat volna a megfelelője: Adva van n elem, melyek közt p1, p2, ..., pr számú egymás közt egyenlő elemekből álló csoportok vannak. Kérdés ezekből hány k-adosztályú variációs füzetet lehet készíteni. Ez a feladat azonban már lényegesen bonyolultabb az itt tárgyaltaknál. Ezzel nem fogunk foglalkozni.
Térjünk vissza az ismétléses variációk kérdéseihez, képezzük pl. az 1, 2, 3 elemek másodosztályú ismétléses variációit:
112131122232132333
A közvetlen magasabb osztályúak ezekből így képezhetők:
111121131211221231311321331112122132212222232312322333113123133213223233313323333

Vagyis az adott variációk mindegyikéhez sorban valamennyi adott elemet hozzácsatoljuk:
Keressük az ismétlés variációk számát. n elemből n elsőosztályú füzetet képezhetünk, ha most az n füzet mindegyikét az összes elemekkel megtoldjuk, n⋅n=n2 számú másodosztályú ismétléses variációs füzetet nyerünk, és ismét megkapunk minden füzetet pontosan egyszer, azaz Vni,2=n2. A harmadosztályú ismétléses variációs füzetek képzésénél az n2 számú füzet mindegyikét az n elem mindegyikével összekapcsoljuk, tehát n⋅n2=n3 füzetet nyerünk. Ezt ismételve eljuthatunk akárhányad osztályú variációkig és kapjuk általában, hogy
Vni,k=nk

Lássunk ismét néhány példát.
Hány 4-jegyű szám alkotható a 0, 2, 4, 6, 8 számjegyekből ? Nyilván az adott 5 elemből alkotható ismétléses 4-edosztályú variációkról van szó. Ezeknek száma V5i,4=54=625.
Ez volna a megoldás, ha 4-jegyű telefonszámokról volna szó. Ha nem telefonszámokról beszélünk, akkor a 0-val kezdődő csoportok számát le kell vonni. Utóbbiak száma V5i,3=53=125 (vagy más meggondolással: az összes csoportok számának ötödrésze 545=53=125). Tehát a szóbanforgó 4-jegyű számok száma V5i,4-V5i,3=625-125=500.
Hányféleképpen tölthető ki egy Toto-szelvény ?
A Toto-szelvény 2 oszlopból áll, mindegyik oszlopban 12 mérkőzés várt eredménye jelezhető az ,,1'', ,,2'', és ,,x'' jelekkel. Egy kitöltött oszlop tehát nem egyéb, mint a fenti 3 jelnek egy 12-edosztályú ismétléses variációja. Tehát egy oszlop V3i,12=312=(36)2=7292=531441-féleképpen tölthető ki. Mivel az első oszlop minden variációja a második oszlop minden variációjával párosítható, a keresett szám (V3i,12)2 vagy ha úgy tetszik V3i,24=5314412=282429536481. (A gyakorlatban a második oszlop nem lehet azonos az első oszloppal, tehát a nyert szám V3i,12-vel csökkentendő.)
 

Kombinációk
 

Ha adott elemekből úgy alkotunk csoportokat, hogy a csoportok mindegyikében csak bizonyos meghatározott számú elem forduljon elő és az elemek sorrendjére nem vagyunk tekintettel, akkor ezen csoportosítási eljárást kombinációnak nevezzük. Miután az elemek sorrendjét nem tekintjük, tehát pl. az 123, 132, 213, 231, 312, 321 füzetek azonosnak számítanak. Így rögzíthetjük, hogy az elemeket mindig természetes sorrendbe írjuk.
A másodosztályú kombinációkat pl. úgy képezzük, hogy minden elemet az összes nála magasabb rangúval összekapcsoljuk. Így, az 1, 2, 3, 4 elemekből kiválasztható összes párok 12, 13, 14, 23, 24, 34. A harmadosztályú kombinációkat úgy nyerjük, hogy az adott kombinációk mindegyikéhez sorra hozzávesszük a benne elő nem forduló magasabb elemeket, tehát 123, 124, 134, 234.
A kombinációk számát leggyorsabban úgy állapíthatjuk meg, ha figyelembe vesszük, hogy n elem k-ad osztályú variációi nem mások, mint n elem összes k-ad osztályú kombinációinak összes permutációi. Pl. 1, 2, 3, 4 elemek másodosztályú kombinációi, mint láttuk, 12, 13, 14, 23, 24, 34. Jelöljük ezeknek számát C42-vel. Az egyes füzetek permutálásával nyerjük a másodosztályú variációkat: 12, 21, 13, 31, 14, 41, 23, 32, 24, 42, 34, 43. Ezeknek számát jelöltük V42-vel. A másodosztályú kombinációs füzetek permutálásával minden egyes füzetből 2! új füzetet nyertünk s így a C42 számú füzetből 2!C42-t, ami viszont nem más, mint négy elem másodosztályú ismétlés nélküli variációinak száma. Tehát 2!C42=V42, ahonnan C43=V422!. Ugyanilyen meggondolással látható bármilyen n-re és k-ra, hogy Vnk megadja a Cnk számú kombinációk összes permutációinak számát. Egy-egy kombináció k elemének permutálásával k! új komplexiót nyerünk, így Cnk számú füzet mindegyikének permutálásával Cnk⋅k! új füzetet nyerünk, és ez annyi, mint ahány k-ad osztályú variáció képezhető n elemből. Tehát
Cnk⋅k=Vnk!,vagyisCnk=Vnkk!=n(n-1)...(n-k+1)1⋅2...k

A Cnk jelzés helyett az egyszerűbb (nk) (Olvasd ,,n alatta k'' vagy ,,n a k fölött'') szimbólumot szokás használni.
Tehát (nk)=n(n-1)...(n-k+1)1⋅2...k. Figyeljük meg, hogy a számlálóban ugyanannyi tényező van, mint a nevezőben, mégpedig n-től kiindulva csökkenő sorrendben.
 

Oldjuk meg a következő példákat:
 

Ismeretes, hogy a számtani haladványban szereplő 5 mennyiség: a, d, n, an és sn között két egymástól független összefüggést (egyenletet) állapítottunk meg, melyek alapján bármely 3 mennyiséget (a fenti 5 közül) megadva, a hiányzó kettő a két egyenletből kiszámítható. Hány ilyen alapfeladat van a számtani haladvánnyal kapcsolatban ? Annyi ilyen alapfeladat van, ahányféleképpen a 2 kiszámítandó mennyiség kiválasztható a szereplő 5 mennyiség közül. Tehát
C52=(52)=5⋅41⋅2=10.

Hányféleképpen választhatunk egy 24 tagú társaságból öttagú küldöttséget ? Mivel itt az egyes csoportokon belül a sorrend mellékes, azért kombinációval van dolgunk. Tehát
C245=24⋅23⋅22⋅21⋅201⋅2⋅3⋅4⋅5=4⋅23⋅22⋅21=42504.
féleképpen választhatunk. (Ha 5 különböző tisztségből álló tisztikar választásáról lett volna szó, akkor V245, lett volna a helyes felelet, ami 5!C245=5100480.)
Most már a bevezetésben felvetett kérdésünkre ‐ hogy mi x4-nek együtthatója az (x+1)10 kifejezésben, is válaszolhatunk és egyúttal az ott használt jelölésre is fény derült.
Az együttható a 10 elemből alkotott 4-edosztályú kombinációk száma
C104=(104)=10⋅9⋅8⋅71⋅2⋅3⋅4=10⋅3⋅7=210.

A kombinációkkal kapcsolatban is vessük fel az ismétléses variációknak megfelelő kérdést: hány k-elemű csoport választható ki n elemből, ha az elemek sorrendje nem számít, de mindegyik elem előfordulhat akárhányszor ? Ezt szokás ismétléses kombinációnak nevezni.
Képezzük az 1, 2, 3, 4 elemeknek sorra az elsőosztályú, másodosztályú és harmadosztályú ismétléses kombinációit. Az első osztályúak nyilván (ugyanúgy, mint ismétlés nélkül): 1, 2, 3, 4. A másodosztályú ismétlés kombinációkat úgy kapjuk, hogy minden egyes elemet először önmagával, azután sorra az összes nála magasabb rangú elemmel kapcsoljuk össze, tehát 11, 12, 13, 14, 22, 23, 24, 33, 34, 44. A közvetlen magasabb osztályú csoportokat úgy kapjuk, hogy minden egyes csoporthoz hozzáírjuk a csoport utolsó elemét, azután sorra egyenként az összes elemeket, melyek az utolsó elemnél magasabb rangúak. Tehát az 1, 2, 3, 4 elemeknek harmadosztályú ismétléséses kombinációi:
111,112,113,114,122,123,124,133,134,144222,223,224,233,234,244333,334,344,444.

Az ismétléses kombinációk számának meghatározása végett írjuk le az 1, 2, 3 elemeknek összes harmadosztályú ismétléses kombinációit:
111123112124113125122134123135133145222234223235233245333345

Ezekből alkossunk újabb csoportokat úgy, hogy az első helyen álló elemek rangszámához 0-t, a második helyen álló elemek rangszámához 1-et és a harmadik helyen álló elemek rangszámához 2-t adunk. (Lásd a jobb oldalon álló füzeteket). Az így nyert új füzetekben alacsonyabb rangú elem nem állhat magasabb rangú elem után, sőt még a rangszámok ismétlődése sem fordulhat elő, mert ez azt jelentené, hogy a baloldali ismétléses kombinációkban alacsonyabb rangú elem állt magasabb rangú elem után, ami a feltétel szerint lehetetlen. Ezek szerint tehát a jobb oldali újabb füzetek nem egyebek, mint az 1, 2, 3, 4, 5 elemeknek ismétlés nélküli 3-ad osztályú kombinációi. Nyilvánvaló az is, hogy e kombinációk egymás között mind különbözőek. Könnyű azt is belátni, hogy ilymódon megkaptuk az 1, 2, 3, 4, 5 elemeknek összes harmadosztályú ismétlés nélküli kombinációit, és ‐ az előbbiek szerint ‐ mindegyiket csak egyszer. Mert az utóbbiak bármelyikében az első helyen álló elem rangszámából 0-t, a második helyen álló elem rangszámából 1-et és a harmadik helyen álló elem rangszámából 2-t levonva, a nyert rangszámok sorrendjében csökkenés nem mutatkozhatik, legfeljebb csak ismétlődés, és így az 1, 2, 3 elemeknek egy ismétléses kombinációját kapjuk. Ebből következik, hogy a 3 elemből alkotott 3-ad osztályú ismétléses kombinációk száma, melyet C3i,3-mal fogunk jelölni, ugyanakkora, mint az 5 elemből ismétlés nélkül alkotott kombinációk száma, vagyis
C3i,3=C53.

Általában ugyanezzel a gondolatmenettel kimutatható, hogy ha az n elemből alkotott k-adosztályú ismétléses kombinációk mindegyikében az első helyen álló elemek rangszámát 0-val, a második helyen álló elemek rangszámát 1-gyel, a harmadik helyen álló elemek rangszámát 2-vel s. i. t. a k-adik helyen álló elemek rangszámát k-1-gyel növeljük, akkor megkapjuk az 1, 2, ...n, n+1, ...n+k-1 elemeknek összes k-ad osztályú ismétlés nélküli kombinációit mégpedig mindegyiket csak egyszer,
12k12...k1⌣1⌣...1⌣1⌣2⌣...k⌣11...212...k+1⋮⋮⋮⋮⋮⋮nn...nnn-1...n+k-1
vagyis
Cni,k=Cn+k-1k=(n+k-1k)==(n+k-1)(n+k-2)...(n+1)⋅n1⋅2...(k-1)⋅k



A Cni.k képlethez eljuthatunk a következő (BEKE MANÓ-tól származó) úton is: az 1, 2, 3, 4, 5 elemeknek bármelyik 4-edosztályú ismétléses kombinációs csoportját megadhatjuk azáltal, hogy megadjuk a benne előforduló elemeket, továbbá megadjuk a II., III. és IV. helyszámokból azokat, amely helyeken ismétlés előfordul. Pl. az első csoport 1 1 1 1 megadható az 1 II III IV jellemző csoporttal, ami azt jelenti, hogy a második helyre olyan elem kerül, amelyik már előfordult, de ez csak az 1-es lehet. Ugyanígy a harmadik és negyedik helyen ismétlődő elem is csak 1-es lehet. Az 1 2 2 5 csoportot az 1 2 5 III, a 3 3 3 4 csoportot 3 4 II III, a 3 3 4 4 füzetet a 3 4 II IV jellemzi. Félreértésre nem vezethet ez a jelölés, miután megegyeztünk abban, hogy az elemeket mindig emelkedő rangsorban írjuk egymás után. Így az első esetbe az 1 2-t kell egymásután írnunk, majd a harmadik helyre egy más szereplő elemet. Ez nem lehet az 1, mert azt a megegyezés szerint a második helyre írtuk volna, tehát a második helyen álló 2-t kell megismételnünk. Hasonlóan nem téveszthető össze a harmadik csoporttal jellemzett kombináció sem a második helyen állóval, mert előbbiben először a 3-ast kell leírni, azt a II-nek megfelelően megismételni, majd új elemet, a 4-et leírni; ezután a negyedik helyen ismétlődő elem már csak a magasabb rangú, a 4-es lehet. Ha nincs a csoportban ismétlés, akkor a ,,jellemző''-je az eredeti csoporttal azonos. A jellemző csoport is mindig 4 elemből áll, mert ha a csoport 4 különböző elemből áll, akkor nincs ismétlődés és akkor a jellemző csoportban sem szerepel helyszám, ha pedig 4-nél kevesebb elem szerepel a 4-ed osztályú ismétléses kombinációs csoportban, akkor annyi ismétlődésnek kell előfordulnia, amennyivel kevesebb elem szerepel a 4-nél és mivel minden ismétlést egy római helyszám jelez, azért a jellemző csoportban szintén mindig 4 az elemek száma. Az is nyilvánvaló, hogy a jellemző csoportban, az értelmezés szerint nem ismétlődhetik egy elem sem. Így minden jellemző csoport nem egyéb, mint az 1, 2, 3, 4, 5, II, III, IV elemeknek egy ismétlés nélküli 4-ed osztályú kombinációja.
Fordítva: az 1, 2, 3, 4, 5, II, III, IV elemekből alkotott bármely 4-ed osztályú ismétlés nélküli kombinációnak megfelel az 1, 2, 3, 4, 5 elemeknek egy ismétléses kombinációja, ami nyilvánvaló abból, hogy csak 3 római számunk van és így minden jellemző csoportban szerepel legalább egy arab szám is. Ezek közül a legkisebbet írjuk az első helyre. A továbbiakra ezután a jellemző csoport már világos utasítást ad. Pl. 1, 3, II, IV-nek megfelel 1 1 3 3, 4 5 II III-nak megfelel 4 4 4 5, 1 3 4 5-nek 1 3 4 5, 2 3 5 IV-nek 2 3 5 5 felel meg.
Így kimondható, hogy
C5i,k=C84=(84)=8⋅7⋅6⋅51⋅2⋅3⋅4=5⋅2⋅7=70

Általában az 1, 2, ..., n elemeknek bármely k-adosztályú ismétléses kombinációja jellemezhető az 1, 2, ...n, II, III, ...K elemeknek egy ismétlés nélküli k-adosztályú kombinációjával és fordítva, az utóbbi n+k-1 elemből alkotott bármely k-adosztályú ismétlés nélküli kombinációnak az 1, 2, ...n elemeknek egy k-adosztályú ismétléses kombinációja felel meg. A jellemző csoportot úgy készítjük el, hogy leírjuk a kombinációban szereplő különböző elemeket egymás után. Ezután római számmal jelezve felsoroljuk azokat a helyeket, amelyeken már előbb is szereplő elem áll. Megfordítva a jellemző csoporthoz úgy készítjük el az általa jellemzett ismétléses kombinációt, hogy növekvő rangsorban írjuk az elemeket egymás után, amíg egy római számmal jelzett helyhez nem érünk. Az ilyen helyre újra a megelőző helyen álló elemet írjuk. Ezen úton is azt nyertük, hogy
Cni,k=Cn+k-1k=(n+k-1k)==(n+k-1)(n+k-2)...(n+1)n1⋅2...(k-1)⋅k=n(n+1)...(n+k-1)1⋅2...k.


Figyeljük meg, hogy a számlálóban ismét ugyanannyi tényező van, mint a nevezőben, de most n-től kiindulva növekvő sorrendben.
Lássunk néhány példát:
4 dobókockával dobunk, melyeknek a 6 lapján a számok (vagy különböző számú pontok) vannak 1-től 6-ig. Hány különböző dobás tehető
 a) ha a kockák különböző színűek ?
 b) ha a kockák egyszínűek ?
a) Legyen a négy kocka fekete, piros, kék és zöld és dobás után állítsuk őket egymás mellé ebben a sorrendben. Ekkor a 3, 6, 1, 3 dobás nyilván különbözik a 6, 3, 3, 1 dobástól. Így az 1, 2, 3, 4, 5, 6 elemeknek 4-edosztályú ismétléses variációival van dolgunk.
V6i,4=64=1296.

b) Ez esetben a 4 kockát nem tudjuk megkülönböztetni s így nincs különbség pl. a 6, 4, 3, 4 dobás és 4, 6, 3, 4 dobás közt. Most tehát a 6 elemnek 4-edosztályú ismétléses kombinációiról van szó. Számuk
C6i,4=6⋅7⋅8⋅91⋅2⋅3⋅4=126.

Tekintsük még a következő példát: Ismeretes az Apollonius-féle érintési feladat, melyben 3 adott kört érintő köröket kell megszerkeszteni. Speciális esetek állanak elő, ha az adott körök között a nulla sugarú kört, vagyis a pontot, és a végtelen sugarú kört: az egyenest is megengedjük. A speciális esetekkel együtt hány ‐ ilyen értelemben általánosított ‐ Apollonius-féle feladat van ?
Nyilván annyi, ahány 3-adosztályú ismétléses kombináció képezhető a következő 3 elemből: pont (P), egyenes (e), kör (k):
C3i,3=3⋅4⋅51⋅2⋅3=10.

Cikkünk tartalmát röviden a következőkben foglalhatjuk össze:
1. Megismerkedtünk a különböző szempontok szerint alkotott csoportok képzési szabályaival. E képzési eljárásoknak főelve, hogy képessé tesz bennünket arra, hogy az összes csoportokat kivétel nélkül megkapjuk és minden csoportot csak egyetlenegyszer. Ebből az is következik, hogy minden csoportnak meghatározott rangszáma (sorszáma) van.
2. A tárgyalt esetekben képzési szabály alapján meg tudtuk állapítani esetről-esetre az összes csoportok számát megadó képletet.
Ha megadjuk az egy csoportban szereplő elemek számát és az elemek sorrendjére is tekintettel vagyunk, vagyis két csoportot, melyek ugyanazokat az elemeket tartalmazzák, de más-más sorrendben, különbözőnek tekintünk, akkor variációról vagy (speciális esetben) permutációról beszélünk.
Az n elemnek (ismétlés nélküli) k-adosztályú (k≤n) variációinak száma
Vnk=n!(n-k)!=n(n-1)...(n-k+1)
(k számú tényező n-től kiindulva csökkenő sorrendben).
Ha k=n, akkor permutációról beszélünk.
Vnn=Pn=n!=1⋅2...(n-1)⋅n.
Ha a permutálandó n elem között p1, p2 ...pr-számú azonos elem van (hol p1+p2+...+pr≤n), akkor a csoportok száma
Pnp1,p2,...pr=n!p1!p2!...pr!.

Az n elemből képezett ismétléses k-adosztályú variációk száma (hol k tetszőleges pozitív egészszám):
Vni,k=nk.

Ha az elemek sorrendjére nem vagyunk tekintettel, vagyis két füzetet azonosnak tekintünk, ha ugyanazon elemektől állnak, akkor kombinációról van szó. (A füzetek egy normál alakja az elemek természetes sorrendje.)
Az n elemből alkotott k-adosztályú kombinációk száma (k≤n):
Cnk=(nk)=n!k!(n-k)!=n⋅(n-1)...(n-k+1)1⋅2...k

Az n elemből alkotott k-adosztályú ismétléses kombinációk száma:
Cni,k=Cn+k-1k=(n+k-1k)==(n+k-1)(n+k-2)...(n+1)n1⋅2...(k-1)⋅k=n(n+1)...(n+k-1)1⋅2...k



Rá kell még mutatnunk, hogy a variációk nem egyebek, mint permutált kombinációk. E tény felhasználásával vezettük le a Cnk képletet, de a Cni,k képlet levezetésére ez a tény nem alkalmas.