Hvað er tvíliðustuðullinn C(n,k) og hvers vegna er fjöldi tvíundastrengja af lengd n með k ása einmitt C(n,k)?

Nafn þitt

Netfang þitt

Netfang móttakanda

Ruslpóstvörn =

Svar

Hvað er tvíliðustuðullinn C(n,k) og hvers vegna er fjöldi tvíundastrengja af lengd n með k ása einmitt C(n,k)?
Formlega er tvíliðustuðullinn $C(n,k)$ skilgreindur sem fjöldi $k$ staka hlutmengja í $n$ staka mengi. Óformlega þýðir þetta að $C(n,k)$ er fjöldi möguleika á að velja $k$ hluti úr safni af $n$ hlutum, þar sem ekki skiptir máli í hvaða röð þessir $k$ hlutir eru valdir. Ef til dæmis velja á $5$ einstaklinga úr $10$ manna hópi, og ekki skiptir máli í hvaða röð þeir eru valdir, táknar $C(10,5)$ fjölda möguleika á að framkvæma þetta val. Í stærðfræði er algengt að nota táknið ${n \choose k}$ í stað $C(n,k)$ fyrir tvíliðustuðul og verður það gert það sem eftir er svarsins.

Til er almenn formúla sem segir okkur hvernig reikna megi gildi tvíliðustuðulsins ${n \choose k}$ í öllum tilvikum. Hún er svona:

\[{n \choose k} = \frac{n!}{k! \cdot (n-k)!}.\]

Hér táknar $n!$ margfeldi allra jákvæðra heiltalna frá $1$ og upp í $n$, það er

\[n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n.\]

Á sama hátt er

\[k! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot k\]

og

\[(n-k)! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-k).\]

Nánar má lesa um þessar stærðir í svari Einars Arnar Þorvaldssonar og Þorsteins Vilhjálmssonar við spurningunni Fyrir hvað stendur upphrópunarmerkið, '!', í líkindareikningi?

Næst skulum við skoða hvernig fyrrnefnd formúla fyrir ${n \choose k}$ er fengin. Hugsum okkur þá að við höfum safn af $n$ hlutum og að við ætlum að velja $k$ hluti úr því. Fyrst um sinn skulum við jafnframt gera ráð fyrir að við veljum þessa $k$ hluti í ákveðinni röð.

Þegar við veljum fyrsta hlutinn getum við gert það á $n$ vegu, því þá eru $n$ hlutir í safninu og við getum valið hvern þeirra sem er. Þegar við veljum annan hlutinn höfum við þegar valið einn hlut úr safninu, svo $n-1$ hlutir standa eftir. Við getum valið hvern sem er af þeim, svo annan hlutinn getum við valið á $n-1$ vegu. Þriðja hlutinn getum við á sama hátt valið á $n-2$ vegu, fjórða hlutinn á $n-3$ vegu, og svo koll af kolli. Síðasta hlutinn, sem er $k$-ti hluturinn, getum við loks valið á $n-(k-1)$ vegu, því þá höfum við þegar valið $k-1$ hluti úr safninu og þess vegna standa $n-(k-1)$ hlutir eftir.

Fjöldi möguleika á að velja $k$ hluti úr safni af $n$ hlutum, þar sem valið fer fram í ákveðinni röð, er þess vegna

\[n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-(k-1)).\]

Rifjum nú upp að ${n \choose k}$ táknar fjölda leiða til að velja $k$ hluti úr safni af $n$ hlutum, þar sem ekki skiptir máli í hvaða röð hlutirnir eru valdir. Tökum síðan eftir því að alls má raða $k$ hlutum á $k!$ vegu, eins og útskýrt er í fyrrnefndu svari Einars og Þorsteins. Í talningunni að ofan kemur sérhvert val á $k$ hlutum þess vegna $k!$ sinnum fyrir; einu sinni fyrir sérhverja mögulega uppröðun á þessum hlutum.

Til að fá ${n \choose k}$ þarf þess vegna að deila formúlunni að ofan með $k!$. Þannig fæst:

\[{n \choose k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-(k-1))}{k!}.\]

Loks getum við margfaldað bæði teljara og nefnara brotsins í hægri hlið þessarar jöfnu með stærðinni

\[(n-k)! = (n-k)\cdot(n-(k+1))\cdot\ldots\cdot1.\]

Þegar þetta er gert fáum við margfeldi af öllum jákvæðum heiltölum frá $n$ niður í $1$ í teljaranum, sem við vitum að er $n!$, og í nefnaranum fáum við $k! \cdot (n-k)!$. Þannig fæst:

\[{n \choose k} = \frac{n!}{k! \cdot (n-k)!}.\]

Eins og kom fram fremst í svarinu er ${10 \choose 5}$ heildarfjöldi möguleika á að velja $5$ einstaklinga úr $10$ manna hópi, þar sem röðin skiptir ekki máli. Nú getum við notað formúluna að ofan til að reikna þessa tölu út:

\[{10 \choose 5} = \frac{10!}{5! \cdot (10-5)!} = \frac{10!}{5! \cdot 5!} = 252.\]

Þetta sýnir að alls er hægt að velja $5$ einstaklinga úr $10$ manna hópi, þar sem röðin skiptir ekki máli, á $252$ vegu.

Sem annað dæmi getum við athugað að fjöldi möguleika á að fá fimm spil á hendi í póker er ${52 \choose 5}$, því spilastokkur hefur alls $52$ spil og ekki skiptir máli í hvaða röð við fáum spilin fimm. Með því að nota formúluna að ofan er hægt að reikna þessa tölu út:

\[{52 \choose 5} = \frac{52!}{5! \cdot (52-5)!} = \frac{52!}{5! \cdot 47!} = 2.598.960. \]

Þess vegna er alls hægt að fá fimm spil á hendi í póker á 2.598.960 vegu.

Svörum loks þeim þætti spurningarinnar sem snýr að tvíundastrengjum. Segja má að tvíundastrengur sé runa af tölustöfunum $0$ og $1$, og tvíundastrengur af lengd $n$ er tvíundastrengur sem hefur alls $n$ tölustafi. Til dæmis er $101001$ tvíundastrengur af lengd $6$ og $010011110$ er tvíundastrengur af lengd $9$.

Segjum að við ætlum að búa til tvíundastreng af lengd $n$ sem hefur $k$ ása. Við getum þá hugsað okkur að við höfum $n$ auð sæti og að í sérhvert sæti setjum við annaðhvort tölustafinn $0$ eða tölustafinn $1$. Þá er nóg að velja í hvaða sæti $1$ á að fara, því $0$ fer sjálfkrafa í hin sætin.

Þar sem við erum að búa til tvíundastreng með $k$ ása getum við alls valið sætin sem $1$ á að fara í á ${n \choose k}$ vegu, því við erum að velja $k$ sæti af $n$ mögulegum og engu máli skiptir í hvaða röð við veljum þau. Þess vegna getum við búið til tvíundastreng af lengd $n$ með $k$ ása á ${n \choose k}$ vegu, sem þýðir að fjöldi slíkra tvíundastrengja er ${n \choose k}$.

Upphaflega spurningin var sem hér segir:

Fjöldi tvíundastrengja af lengd n sem innihalda k ása er C(n,k), sem er fjöldi k staka hlutmengja í n staka mengi. Hver er ástæðan fyrir þessu?

...