Tietystä n-alkioisesta joukosta S muodostuvien k-kombinaatioiden lukumäärää merkitään alkeiskombinatoriikan teksteissä usein C ( n , k ) {\displaystyle C(n,k)}
, tai muunnelmalla, kuten C k n {\displaystyle 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}}
tai jopa C n k {\displaystyle C_{n}^{k}}}
(jälkimmäinen muoto oli standardi ranskalaisissa, romanialaisissa, venäläisissä, kiinalaisissa ja puolalaisissa teksteissä). Sama luku esiintyy kuitenkin monissa muissa matemaattisissa yhteyksissä, joissa sitä merkitään ( n k ) {\displaystyle {\tbinom {n}{k}}}}
(usein luettuna ”n valitsee k”); erityisesti se esiintyy kertoimena binomikaavassa, mistä johtuu sen nimi binomikerroin. Voidaan määritellä ( n k ) {\displaystyle {\tbinom{n}{k}}}
kaikille luonnollisille luvuille k kerralla relaatiolla ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}}X^{k}},}
josta nähdään, että
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}=1,}
ja edelleen,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
kun k > n.
Voidaksemme nähdä, että nämä kertoimet laskevat k-kombinaatioita S:stä, voidaan ensin tarkastella n:n erillisen muuttujan kokoelmaa Xs, joka on merkitty S:n elementeillä s, ja laajentaa tulo kaikkien S:n elementtien yli:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
sillä on 2n erillistä termiä, jotka vastaavat kaikkia S:n osajoukkoja, joista kukin osajoukko antaa vastaavien muuttujien Xs:n tulon. Asetetaan nyt kaikki Xs yhtä suureksi kuin merkitsemätön muuttuja X, niin että tuotteesta tulee (1 + X)n, ja kutakin S:n k-kombinaatiota vastaava termi tulee Xk, niin että kyseisen potenssin kerroin tuloksessa on yhtä suuri kuin tällaisten k-kombinaatioiden lukumäärä.
Binomikertoimet voidaan laskea eksplisiittisesti eri tavoin. Saadakseen kaikki ne laajennuksille (1 + X)n asti voidaan käyttää (jo annettujen perustapausten lisäksi) rekursiosuhdetta
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
for 0 < k < n, joka seuraa (1 + X)n = (1 + X)n – 1(1 + X); tämä johtaa Pascalin kolmion rakentamiseen.
Yksittäisen binomikertoimen määrittämiseksi on käytännöllisempää käyttää kaavaa
( 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!}}}
.
Ajanottaja antaa n:n k-permutaatioiden lukumäärän, ts, S:n k:sta eri elementistä koostuvista sekvensseistä, kun taas nimittäjä antaa niiden tällaisten k-permutaatioiden lukumäärän, jotka antavat saman k-yhdistelmän, kun järjestystä ei oteta huomioon.
Kun k on suurempi kuin n/2, yllä oleva kaava sisältää osoittajalle ja nimittäjälle yhteisiä tekijöitä, ja niiden kumoaminen antaa suhteen
( n k ) = ( n n – k ) , {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}},}
for 0 ≤ k ≤ n. Tämä ilmaisee symmetriaa, joka on ilmeinen binomikaavasta, ja se voidaan ymmärtää myös k-kombinaatioiden kannalta ottamalla tällaisen kombinaation komplementti, joka on (n – k)-kombinaatio.
Loppujen lopuksi on olemassa kaava, joka osoittaa tätä symmetriaa suoraan, ja jolla on se etu, että se on helppo muistaa:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}
joissa n! tarkoittaa n:n faktoriaalia. Se saadaan edellisestä kaavasta kertomalla nimittäjä ja osoittaja (n – k)!, joten se on varmasti laskennallisesti vähemmän tehokas kuin tuo kaava.
Viimeinen kaava voidaan ymmärtää suoraan tarkastelemalla kaikkien S:n alkioiden n! permutaatiota. Jokainen tällainen permutaatio antaa k-kombinaation valitsemalla sen ensimmäiset k elementtiä. Kaksoisvalintoja on paljon: mikä tahansa ensimmäisten k alkion keskenään ja viimeisten (n – k) alkioiden keskenään yhdistetty permutaatio tuottaa saman yhdistelmän; tämä selittää kaavassa olevan jaon.
Yllä olevista kaavoista seuraa Pascalin kolmion vierekkäisten lukujen välisiä suhteita kaikkiin kolmeen suuntaan:
( n k ) = { ( n k – 1 ) n – k + 1 k jos k > 0 ( n – 1 k ) n n – k jos k < n ( n – 1 k – 1 ) n k jos n , k > 0 {\displaystyle {\binom {n}{k}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{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}}}
.
Yhdessä perustapausten ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}}
, näiden avulla voidaan peräkkäin laskea vastaavasti kaikki yhdistelmien lukumäärät samasta joukosta (Pascalin kolmion rivi), k-kombinaatiot kasvavan kokoisista joukoista ja yhdistelmät, joiden komplementti on kiinteän kokoinen n – k.
Esimerkki kombinaatioiden laskemisestaEdit
Konkreettisena esimerkkinä voidaan laskea tavallisesta viidenkymmenenkahden kortin pakasta mahdollisten viiden kortin käsien lukumäärä seuraavasti:
( 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.}
Vaihtoehtoisesti voidaan käyttää kaavaa faktoriaaleina ja kumota osoittajan tekijät nimittäjän tekijöiden osilla, minkä jälkeen tarvitaan vain jäljelle jäävien tekijöiden kertominen:
( 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}}}
Toinen vaihtoehtoinen, ensimmäistä vastaava laskutoimitus perustuu kirjoitukseen
( 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}}},}
jolloin saadaan
( 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}}
.
Kun se arvioidaan seuraavassa järjestyksessä: 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, tämä voidaan laskea käyttämällä vain kokonaislukuaritmetiikkaa. Syynä on se, että jokaisen jaon yhteydessä syntyvä välitulos on itsessään binomikerroin, joten jäännöslukuja ei koskaan synny.
Symmetrisen kaavan käyttäminen faktoriaaleina ilman yksinkertaistusten suorittamista antaa melko laajan laskutoimituksen:
( 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-kombinaatioiden luetteleminenEdit
Voidaan luetella tietyn n-alkioisen joukon S kaikki k-kombinaatiot jossakin kiinteässä järjestyksessä, jolloin saadaan bijektio intervallista ( n k ) {\displaystyle {\tbinom {n}{k}}}}
kokonaislukujen välille näiden k-yhdistelmien joukon kanssa. Jos oletetaan, että S on itsessään järjestetty, esimerkiksi S = { 1, 2, …, n }, sen k-yhdistelmien järjestämiseen on kaksi luonnollista mahdollisuutta: vertaamalla niiden pienimpiä alkioita ensin (kuten yllä olevissa kuvissa) tai vertaamalla niiden suurimpia alkioita ensin. Jälkimmäisen vaihtoehdon etuna on, että uuden suurimman alkion lisääminen S:ään ei muuta luettelon alkuosaa, vaan lisää vain suuremman joukon uudet k-yhdistelmät edellisten jälkeen. Toistamalla tätä prosessia voidaan luetteloa laajentaa loputtomiin yhä suurempien joukkojen k-yhdistelmillä. Jos lisäksi kokonaislukujen intervallien katsotaan alkavan 0:sta, k-yhdistelmä tietyssä luettelon paikassa i voidaan helposti laskea i:stä, ja näin saatu bijektio tunnetaan nimellä kombinatorinen lukujärjestelmä (combinatorial number system). Se tunnetaan laskennallisessa matematiikassa myös nimillä ”rank”/”ranking” ja ”unranking”.
On monia tapoja luetella k yhdistelmää. Yksi tapa on käydä läpi kaikki binääriluvut, jotka ovat pienempiä kuin 2n. Valitaan ne luvut, joissa on k nollasta poikkeavaa bittiä, vaikka tämä on hyvin tehotonta pienelläkin n:llä (esim. n = 20 edellyttäisi noin miljoonan luvun tarkastelua, kun taas k = 10:n tapauksessa k:n sallittujen k-kombinaatioiden enimmäismäärä on noin 186 tuhatta). Näiden 1 bittien sijainnit tällaisessa luvussa ovat joukkojen { 1, …, n } erityinen k-kombinaatio. Toinen yksinkertainen ja nopeampi tapa on seurata valittujen elementtien k indeksinumeroa, alkaen {0 .. k-1} (nollapohjainen) tai {1 .. k} (yksikköpohjainen) ensimmäisenä sallittuna k-yhdistelmänä ja siirrytään sitten toistuvasti seuraavaan sallittuun k-yhdistelmään lisäämällä viimeistä indeksilukua, jos se on pienempi kuin n-1 (nollapohjainen) tai n (yksikköpohjainen), tai viimeistä indeksilukua x, joka on pienempi kuin sitä seuraava indeksiluku miinus yksi, jos tällainen indeksi on olemassa, ja nollaamalla x:n jälkeiset indeksiluvut muotoon {x + 1, x + 2, …}.
.