Permutation og Kombination

At Tælle Arrangementer og Valg fra en Gruppe

En permutation (nPr) tæller, hvor mange måder man kan arrangere r elementer ud af n på, hvor rækkefølgen betyder noget, mens en kombination (nCr) tæller, hvor mange måder man kan vælge r elementer ud af n på, hvor rækkefølgen ikke betyder noget. Indtast et samlet antal elementer (n) og hvor mange du vælger (r), og denne beregner finder begge relaterede svar på én gang.

Formlerne

• Permutationer: $P(\vA{n}, \vB{r}) = \frac{\vA{n}!}{(\vA{n} - \vB{r})!}$ — svarende til produktet af $\vB{r}$ faldende tal, der starter ved $\vA{n}$: $\vA{n} \times (\vA{n}-1) \times \cdots \times (\vA{n}-\vB{r}+1)$.
• Kombinationer: $C(\vA{n}, \vB{r}) = \frac{P(\vA{n}, \vB{r})}{\vB{r}!}$ — det samme antal permutationer, divideret med de $\vB{r}!$ måder de samme $\vB{r}$ elementer selv kunne omarrangeres på (da rækkefølgen ikke betyder noget for en kombination).

Eksempel

At vælge 3 elementer fra en gruppe på 10, hvor rækkefølgen betyder noget (permutationer):

$$P(10,3) = 10 \times 9 \times 8 = 720$$

Det samme valg, hvor rækkefølgen IKKE betyder noget (kombinationer):

$$C(10,3) = 720 \div 3! = 720 \div 6 = 120$$

Et Virkelighedstjek

Chancerne for at matche alle 6 tal i en 6-af-49-lottotrækning er 1 til C(49,6) — præcis 13.983.816 — da rækkefølgen tallene trækkes i, ikke ændrer, om du har vundet.

Vigtige Faktorer At Overveje

• Om rækkefølgen betyder noget, er det enkeltstående spørgsmål, der afgør, hvilken formel der gælder. At arrangere medaljevindere på en podie (1., 2., 3. plads betyder noget) er et permutationsproblem, mens at vælge hvilke 3 personer der udgør et udvalg (ingen rangordning involveret) er et kombinationsproblem — at identificere denne skelnen korrekt er den mest almindelige fejlkilde, når man anvender disse formler.
• Kombinationer producerer altid et lige stort eller mindre antal end permutationer for de samme n og r. Da en kombination grupperer hver mulig rækkefølge af de samme r elementer sammen til ét tal, er C(n,r) altid P(n,r) divideret med r! — de to værdier matcher kun præcist, når r er 0 eller 1, da der kun er én måde at arrangere 0 eller 1 elementer på uanset rækkefølge.
• Både permutations- og kombinationstal vokser ekstremt hurtigt, efterhånden som n og r stiger. Denne eksplosive vækst (kaldet kombinatorisk eksplosion) er præcis grunden til, at lotto-lignende odds bliver så astronomisk små med blot en beskeden stigning i, hvor mange tal der trækkes fra — at gå fra en 6-af-49-lotto til en 6-af-59-lotto, for eksempel, forværrer oddsene mærkbart på trods af, at puljen kun vokser med 10 tal.
• Disse formler antager, at hvert element er distinkt, og at ingen kan vælges mere end én gang. Et scenarie, der tillader gentagne valg (som en 4-cifret PIN-kode, hvor cifre kan gentages), bruger en helt anden tællformel — bekræft altid, om gentagelse er tilladt, før du anvender de standardiserede nPr/nCr-formler her.

Almindelige Fejl

• At bruge permutationstallet, når rækkefølgen reelt ikke betyder noget, eller omvendt. Dette er den mest almindelige fejl — spørg altid først, om ombytning af to valgte elementer ville tælle som et andet resultat, før du vælger en formel, i stedet for at gætte ud fra, hvordan problemet er formuleret.
• At glemme, at kombinationer aldrig er større end permutationer for de samme n og r. Hvis et kombinationstal viser sig at være større end det tilsvarende permutationstal for de samme input, er noget indtastet forkert — kombinationer dividerer permutationstallet ned, de forstørrer det aldrig.
• At anvende disse formler på en situation, der tillader gentagne valg. Begge formler antager, at hvert element højst kan vælges én gang — et problem, der tillader gentagelser (som at generere en 4-cifret PIN-kode), kræver en helt anden tællemetode, ikke nPr eller nCr.

Godt At Vide

• Vil du rent faktisk beregne oddsene for et specifikt udfald, ikke bare tælle mulighederne? Sandsynlighed Beregner omdanner et kombinations- eller permutationstal til en faktisk sandsynlighed.
• Arbejder du med et helt datasæt i stedet for bare at tælle arrangementer? Statistik Beregner beregner gennemsnit, standardafvigelse og andre sammenfattende tal fra en liste af tal.
• Skal du forenkle et forhold eller finde en fælles nævner som en del af et relateret kombinatorikproblem? Største Fælles Divisor og Mindste Fælles Multiplum Beregner finder den største fælles divisor og mindste fælles multiplum for et sæt tal.