Elemi kombinatorikai szövegekben gyakran C ( n , k ) {\displaystyle C(n,k)} jelölik az adott n elemű S halmaz k kombinációinak számát.
, vagy egy variációval, például C k n {\displaystyle C_{k}^{n}}}
, n C k {\displaystyle {}_{n}C_{k}}}
, n C k {\displaystyle {}^{n}C_{k}}}
, C n , k {\displaystyle C_{n,k}}
vagy akár C n k {\displaystyle C_{n}^{k}}}
(ez utóbbi forma volt szabványos a francia, román, orosz, kínai és lengyel szövegekben). Ugyanez a szám azonban számos más matematikai szövegkörnyezetben is előfordul, ahol ( n k ) {\displaystyle {\tbinom {n}{k}}}}
(gyakran úgy olvassák, hogy “n választ k-t”); nevezetesen a binomiális képletben együtthatóként fordul elő, innen a binomiális együttható elnevezés. Meghatározhatjuk ( n k ) {\displaystyle {\tbinom {n}{k}}}}
minden k természetes számra egyszerre a ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k összefüggéssel, {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}}X^{k}},}
amiből világos, hogy
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}=1,}
és továbbá,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
k > n esetén.
Hogy lássuk, hogy ezek az együtthatók k-kombinációkat számítanak S-ből, először is tekinthetjük az S s elemeivel jelölt n különböző Xs változók gyűjteményét, és a szorzatot kiterjeszthetjük S összes elemére:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
az S összes részhalmazának megfelelő 2n különböző tagból áll, mindegyik részhalmaz a megfelelő Xs változók szorzatát adja. Most az összes Xs-t az X jelöletlen változóval egyenlővé téve, így a szorzat (1 + X)n lesz, az S-ből minden k kombinációhoz tartozó kifejezés Xk lesz, így az eredményben az adott hatvány együtthatója megegyezik az ilyen k kombinációk számával.
A binomiális együtthatókat többféleképpen lehet explicit módon kiszámítani. Ahhoz, hogy a (1 + X)n-ig terjedő bővítésekre az összeset megkapjuk, használhatjuk (a már megadott alapeseteken kívül) a rekurziós összefüggést
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}},}
ra 0 < k < n, ami az (1 + X)n = (1 + X)n – 1(1 + X) egyenletből következik; ez vezet a Pascal-háromszög megkonstruálásához.
Az egyedi binomiális együttható meghatározásához célszerűbb a következő képletet használni
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}}
.
A számláló az n k-permutációinak számát adja meg, azaz, az S k különböző elemeinek sorozata, míg a nevező azoknak a k-permutációknak a számát adja meg, amelyek a sorrend figyelmen kívül hagyásával ugyanazt a k-kombinációt adják.
Ha k meghaladja az n/2-t, a fenti képlet a számlálóban és a nevezőben közös tényezőket tartalmaz, és ezek kiiktatásával az összefüggés
( n k ) = ( n n – k ) , {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}
for 0 ≤ k ≤ n. Ez egy olyan szimmetriát fejez ki, amely a binomiális képletből nyilvánvaló, és a k-kombinációk szempontjából is érthető, ha egy ilyen kombináció komplementjét vesszük, amely egy (n – k)-kombináció.
Végül van egy képlet, amely közvetlenül mutatja ezt a szimmetriát, és amelynek az az érdeme, hogy könnyen megjegyezhető:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}
ahol n! az n faktoriálisát jelöli. Az előző képletből úgy kapjuk, hogy a nevezőt és a számlálót megszorozzuk (n – k)!, így számítási szempontból biztosan kevésbé hatékony, mint az a képlet.
Az utolsó képlet közvetlenül is értelmezhető, ha figyelembe vesszük S összes elemének n! permutációját. Minden ilyen permutáció az első k elemének kiválasztásával k-kombinációt ad. Sok duplikált kiválasztás van: az első k elemeknek egymás között és az utolsó (n – k) elemeknek egymás között bármely kombinált permutációja ugyanazt a kombinációt eredményezi; ez magyarázza a képletben szereplő osztást.
A fenti képletekből következnek a Pascal-háromszögben mindhárom irányban szomszédos számok közötti összefüggések:
( n k ) = { ( n k – 1 ) n – k + 1 k ha k > 0 ( n – 1 k ) n n – k ha k < n ( n – 1 k – 1 ) n k ha n , k > 0 {\displaystyle {\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}{k}}&\quad {\text{if }}k>0\\\{\\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\{\binom {n-1}{k-1}}{\frac {n}{k}}}&\quad {\text{if }}n,k>0\end{cases}}}
.
Az alapesetekkel együtt ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}}
, ezek lehetővé teszik az azonos halmazból (a Pascal-háromszög egy sorából) származó kombinációk, a növekvő méretű halmazok k-kombinációinak, illetve a fix n – k méretű komplementummal rendelkező kombinációk egymás utáni kiszámítását.
Példa a kombinációk megszámlálásáraSzerkesztés
Konkrét példaként kiszámíthatjuk az ötvenkét szabványos kártyapakliból lehetséges ötlapos kezek számát a következőképpen:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311,875,200 120 = 2,598,960. {\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Alternatívaként használhatjuk a faktoriális képletet, és a számlálóban lévő tényezőket a nevezőben lévő tényezők részeivel szemben törölhetjük, ami után már csak a megmaradó tényezők szorzására van szükség:
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\\\&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\\&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}}\\\&={\frac {(26\times {\cancel {2})\times (17\times {\cancel {3})\times (10\times {\cancel {{\\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\\&={26\times 17\times 10\times 49\times 12}\\\&=2{,}598{,}960.\end{alignedat}}}
Egy másik, az elsővel egyenértékű alternatív számítás az alábbi felíráson alapul:
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}}},}
amelyből
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960}}
.
A következő sorrendben kiértékelve: 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, ez csak egész számtani számítással számítható ki. Ennek az az oka, hogy minden egyes osztásnál a keletkező közbenső eredmény maga is binomiális együttható, így maradékok soha nem keletkeznek.
A szimmetrikus képletet a faktoriálisok tekintetében egyszerűsítések elvégzése nélkül használva meglehetősen terjedelmes számítást kapunk:
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}}}
K-kombinációk felsorolásaSzerkesztés
Egy adott n elemű S halmaz összes k-kombinációját felsorolhatjuk valamilyen rögzített sorrendben, ami egy ( n k ) {\displaystyle {\tbinom {n}{k}}}} intervallumból bijekciót hoz létre.
egész számok és e k-kombinációk halmaza között. Feltételezve, hogy S maga is rendezett, például S = { 1, 2, …, n }, két természetes lehetőség van a k-kombinációk rendezésére: először a legkisebb elemeik összehasonlítása (mint a fenti ábrákon) vagy először a legnagyobb elemeik összehasonlítása. Az utóbbi lehetőségnek megvan az az előnye, hogy egy új legnagyobb elem hozzáadása S-hez nem változtatja meg a felsorolás kezdeti részét, hanem csak a nagyobb halmaz új k-kombinációit adja a korábbiak után. Ezt a folyamatot megismételve a felsorolás a végtelenségig bővíthető egyre nagyobb halmazok k-kombinációival. Ha ráadásul az egész számok intervallumait úgy vesszük, hogy 0-ról indulnak, akkor a felsorolás egy adott i helyén lévő k-kombináció könnyen kiszámítható i-ből, és az így kapott bijekciót kombinatorikus számrendszernek nevezzük. A számítási matematikában “rangsor”/”rangsorolás” és “rangsorolástalanítás” néven is ismert.
A k kombinációk felsorolásának számos módja van. Az egyik mód az, hogy felkeressük az összes 2n-nél kisebb bináris számot. Válasszuk ki azokat a számokat, amelyeknek k nem nulla bitje van, bár ez még kis n esetén is nagyon kevéssé hatékony (pl. n = 20 esetén körülbelül egymillió számot kellene meglátogatni, míg k = 10 esetén a megengedett k kombinációk maximális száma körülbelül 186 ezer). Ezeknek az 1 biteknek a helyzete egy ilyen számban a { 1, …, n } halmaz egy adott k-kombinációja. Egy másik egyszerű, gyorsabb módszer a kiválasztott elemek k indexszámának nyomon követése, kezdve a {0 .. k-1} (nulla alapú) vagy {1 … k} (egy-alapú) mint az első megengedett k-kombinációval, majd ismételten a következő megengedett k-kombinációra lépünk az utolsó indexszám növelésével, ha az kisebb, mint n-1 (nulla-alapú) vagy n (egy-alapú), vagy az utolsó x indexszámmal, amely kisebb, mint az azt követő indexszám mínusz egy, ha létezik ilyen index, és az x utáni indexszámok visszaállításával {x+1, x+2, …}.
.