Antag att du har n typer av objekt, och du vill välja en samling av r av dem. Vi kanske vill ha dessa artiklar i en viss ordning. Vi kallar dessa uppsättningar av artiklar permutationer. Om beställningen spelar ingen roll kallar vi samlingskombinationer. För både kombinationer och permutationer kan du överväga det fall där du väljer en del av n-typen mer än en gång, som kallas "med repetition", eller det fall där du bara väljer en typ enstaka, som kallas "ingen repetition" '. Målet är att kunna räkna antalet kombinationer eller permutationer som är möjliga i en given situation.

Beställningar och faktorialer

Faktorfunktionen används ofta vid beräkning av kombinationer och permutationer. N! betyder N × (N-1) × ... × 2 × 1. Till exempel 5! = 5 × 4 × 3 × 2 × 1 = 120. Antalet sätt att beställa en uppsättning objekt är en factorial. Ta de tre bokstäverna a, b och c. Du har tre val för första bokstaven, två för den andra och en för den tredje. Med andra ord totalt 3 × 2 × 1 = 6 beställningar. I allmänhet finns det n! sätt att beställa n föremål.

Permutationer med upprepning

Antag att du har tre rum du ska måla, och var och en kommer att målas en av fem färger: röd (r), grön ( g), blå (b), gul (y) eller apelsin (o). Du kan välja varje färg så många gånger du vill. Du har fem färger att välja mellan för första rummet, fem för andra och fem för tredje. Detta ger totalt 5 × 5 × 5 = 125 möjligheter. I allmänhet är antalet sätt att välja en grupp av r-artiklar i en viss ordning från n repeterbara val n /r.

Tillåten utan upprepning

Antag nu att varje rum kommer att vara en annan färg. Du kan välja mellan fem färger för första rummet, fyra för andra och bara tre för tredje. Detta ger 5 × 4 × 3 = 60, vilket bara råkar vara 5! /2 !. I allmänhet är antalet oberoende sätt att välja r-poster i en viss ordning från n icke-återställbara val n! /(N-r)!

Kombinationer utan repetition

Därefter glömmer du vilket rum är vilken färg Välj bara tre oberoende färger för färgschemat. Beställningen spelar ingen roll här, så (röd, grön, blå) är densamma som (röd, blå, grön). För val av tre färger finns 3! sätt du kan beställa dem. Så du minskar antalet permutationer med 3! för att få 5! /(2! × 3!) = 10. I allmänhet kan du välja en grupp av r-poster i vilken ordning som helst från ett urval av n nonrepeatable val i n! /[(n-r)! × r! ] sätt.

Kombinationer med upprepning

Slutligen måste du skapa ett färgschema där du kan använda vilken färg som helst så många gånger du vill. En smart bokföringskod hjälper denna räkningsuppgift. Använd tre Xs för att representera rummen. Din lista med färger representeras av 'rgbyo'. Blanda X-erna i din färglista och associera varje X med den första färgen till vänster om den. Till exempel betyder rgXXbyXo att det första rummet är grönt, det andra är grönt och det tredje är gult. En X måste ha minst en färg till vänster, så det finns fem tillgängliga slitsar för den första X. Eftersom listan nu innehåller en X finns det sex tillgängliga slitsar för den andra X och sju tillgängliga slots för den tredje X. I allt finns det 5 × 6 × 7 = 7! /4! sätt att skriva koden. Rummets ordning är dock godtycklig, så det finns egentligen bara 7! /(4! × 3!) Unika arrangemang. I allmänhet kan du välja r-poster i valfri ordning från n repeterbara val i (n + r-1)! /[(N-1)! × r!] Sätt.