Stakroynd uttan Afturlegging v. Raðfylgju

Filmur

Innleiðing

Støðan er næstan tann sama sum á seinastu síðu: vit hava \(n\) lutir og skulu velja \(r\) av teimum, ein í senn, og raðfylgjan hevur týdning.

Ein einasti munur er, at nú leggja vit ikki lutin aftur. Ein lutur, sum er valdur, er úti úr myndini og kann ikki veljast aftur. Vit siga, at stakroyndin er uttan afturlegging.

Frymilin

Vit hugsa okkum valini eitt og eitt, eins og á undanfarnu síðuni:

• Fyrsta valið: \(n\) møguleikar.
• Annað valið: ein lutur er tikin burtur, so nú eru \(n - 1\) møguleikar.
• Triðja valið: \(n - 2\) møguleikar.
• … og so framvegis. Í \(r\)-tu val eru \(n - r + 1\) møguleikar eftir.

Faldireglan gevur tá

\[n \cdot (n-1) \cdot (n-2) \cdots (n-r+1)\]

Hetta er eitt produkt (falding) við \(r\) liðum, har hvør liður er “eitt minni” enn tann undanfarni.

Fakultet

Fyri at skriva hetta styttri innføra vit fakultet. Fyri eitt heilt tal \(n \geq 1\) er

\[n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1\]

Til dømis er \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\). Harafturat verður sett \(0! = 1\).

Faldingin omanfyri er byrjanin á \(n!\) - men hon steðgar, tá ið vit hava tikið \(r\) liðir. Tey liðini, sum mangla, eru júst \((n-r)!\). Tí kunnu vit skriva

\[n \cdot (n-1) \cdots (n-r+1) = \frac{n!}{(n-r)!}\]

Hetta sæst best við at hyggja at, hvat hendir í brotinum: í teljaranum stendur alt produktið niður til 1, og í nevnaranum stendur tann parturin av henni, sum vit ikki skulu hava við. Hann verður styttur burtur.

Permutatiónir

Talið av møguleikum fyri at velja \(r\) lutir av \(n\) lutum, tá ið raðfylgjan hevur týdning og lutirnir ikki verða lagdir aftur, verður kallað talið av permutatiónum:

\[P(n, r) = \frac{n!}{(n-r)!}\]

Ansa eftir! Hetta \(P\) hevur einki at gera við líkindafunktiónina \(P\) frá fyrra partinum av evninum. Tað er sami bókstavur í tveimum ymiskum týdningum, og tað sæst av, hvat stendur inni í klombrunum: \(P(A)\) er sannlíkindið fyri eina hending, \(P(n, r)\) er eitt tal av møguleikum.

Legg til merkis, at nú má \(r \leq n\). Vit kunnu ikki velja fimm lutir av trimum, tá ið hvør lutur bert kann veljast eina ferð.

Dømi: kapping

Átta luttakarar eru í einari kapping. Hvussu nógvir møguleikar eru fyri, hvør vinnur gull, silvur og bronsu?

Her er \(n = 8\) og \(r = 3\). Raðfylgjan hevur eyðsæð týdning - tað er ikki tað sama at vinna gull sum at vinna bronsu - og ein luttakari kann bert fáa eina medalju.

Vit rokna beinleiðis:

\[8 \cdot 7 \cdot 6 = 336\]

Ella vit nýta frymilin:

\[P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = \frac{40\,320}{120} = 336\]

Báðir hættirnir geva 336 møguleikar.

Samanbering við seinastu síðu

Var stakroyndin við afturlegging, hevði svarið verið \(8^3 = 512\). Tað er størri, og orsøkin er greið: tá vóru eisini møguleikar sum “sami luttakari vinnur bæði gull og silvur” taldir við. Í hesum føri er hetta ikki loyvt, og tí verður talið minni.

Stutt sagt

\[\text{Stakroyndir uttan afturlegging, raðfylgja hevur týdning:} \qquad P(n, r) = \frac{n!}{(n-r)!}\]

Á næstu síðu spyrja vit tann seinasta spurningin: hvat hendir, um raðfylgjan ikki hevur týdning?