Kombinatorik

Kombinatorik kallas den del av aritmetiken, som sysslar med att undersöka, på hur många sätt ett givet antal element kan ordnas och sammanställas i grupper.
Man skiljer på permutationer, kombinationer och variationer (delpermutationer).

Alla element ingår i sammanställningen Permutationer
En del av elementen ingår i sammanställningen Olika ordningsföljd räknas för samma sammanstälningar
Kombinationer av k st valda bland n st utan hänsyn till ordning		 Kombinationer
Olika ordningsföljd räknas för olika sammanställningar
Permutationer av k st valda bland n st med hänsyn till ordning. 		Variationer
delpermutationer

Fakultet (faktorial)

benämning på produkten n!=1·2·3·…·n av de första positiva heltalen.

T.ex. är 5!=1·2·3·4·5=120.

Definition:

n! = n·(n - 1)!

Om man nämligen väljer n = 1 blir ju uttrycket 1! = 1·0! och för att det ska stämma måste 0! vara 1.
Betecknas även med Π (n)

Gamma-funktion utvidgar fakultetsbegreppet till alla positiva reella tal:

Γ(n) = (n - 1)! om n är positivt helt tal.

Permutationer

En permutation är en sammanställning av n element. Varje element förekommer en och endast en gång i permutationen.

A. Permutationer utan upprepning. Alla element är olika.
   Antalet permutationer är då n!   (n-fakultet)

Pn = n!

Ex.   De tre elementen a, b och c permuteras.
Antalet permutationer är: P3 = 3! = 1·2·3 = 6
abc bac cab
acb bca cba

B. Permutationer med upprepning. Alla n element är inte olika.
Det är t.ex. två grupper, den första med k1 lika element, den andra med k2 lika element.
Antalet permutationer blir då:

Ex.   Elementen A, A, A, B och B permuteras.
Antalet permutationer är:
 
AAABB AABAB ABAAB BAAAB AABBA ABABA ABBAA ABBAA BABAA BBAAA

Kombinationer

En kombination är en sammanställning av endast k av n olika element (k < n). Olika ordningsföljder har inte någon betydelse. Så t.ex. är ab och ba samma kombination

A. Kombinationer utan upprepning. Varje element får förekomma endast en gång
Antalet kombinationer är (binomialformeln):

Betecknas även: C(n,k); Cn,k; nCk (nCr).

Binomialkoefficienten (utläses "n över k" eller "n välj k") är koefficienten av xn i utvecklingen av (1 + x)n och kan enligt binomialsatsen beräknas som

Ex.   Antal kombinationer med 5 element till en mängd med 8 element:
 

B. Kombinationer med upprepning. Ett element får förekomma flera gånger i kombinationen.
Antalet kombinationer är:

Ex. Två av de fyra elementen a, b, c, och d kombineras.
Antalet kombinationer är:  
Kombinationerna är: aa ab ac ad bb bc bd cc cd dd

Variationer (delpermutationer)

En variation är en sammanställning av bara k av n olika element (k < n).
Olika ordningsföljder räknas som olika sammanställningar är samma som
Antalet permutationer av p olika objekt valda bland n givna

A. Variation utan upprepning. Om ett element får endast användes en gång är antalet variationer:

Betecknas även: P(n,k), nPk (nPr)

Ex. De tre elementen 1,2 och 3 varieras.
Antalet variationer är:  
12  13  21  23  31  32

B. Variation med upprepning. Samma element får användas flera gånger.
Antalet variationer är:

Ex. Två av de tre bokstäverna A, B och C varieras.
Antalet variationer är:
AA AB AC BA BB BC CA CB CC

Binomialsatsen

Newtons binomialteorem.
Utvecklingen
där n är ett positivt heltal.

Koefficienterna kallas binomialkoefficienter och .
Om n inte är ett positivt heltal gäller i stället den oändliga serieutvecklingen:

Binomialkoefficienterna kan ställas upp i den s.k. Pascals triangel, som bygger på det viktiga sambandet


så att t.ex.