Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

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?

Útgáfudagur

30.9.2011

Spyrjandi

Davíð Freyr Björnsson

Höfundur

B.S. í stærðfræði

Tilvísun

Einar Bjarki Gunnarsson. „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)?“ Vísindavefurinn, 30. september 2011. Sótt 23. október 2017. http://visindavefur.is/svar.php?id=56654.

Einar Bjarki Gunnarsson. (2011, 30. september). 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)? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=56654

Einar Bjarki Gunnarsson. „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)?“ Vísindavefurinn. 30. sep. 2011. Vefsíða. 23. okt. 2017. <http://visindavefur.is/svar.php?id=56654>.

Chicago | APA | MLA

Sendu inn spurningu
eða

Vísindadagatalið

Arabískar tölur

Í bókinni Liber abaci frá 1202 kynnti ítalski stærðfræðingurinn Leónardó Fibonacci arabískar tölur og indó-arabískan sætisrithátt fyrir Evrópumönnum. Áður höfðu Evrópumenn notað rómverskan talnarithátt og reiknað á talnagrindum. Hin nýja talnaritun varð til þess að menn gátu reiknað á blaði, á sandi eða vaxtöflum.