Kombinatorika

Kombináció

Kulcsszavak: kombináció, ismétléses, ismétlés nélküli

Ismétlés nélküli kombináció

n különböző elem közül k elemet kell kiválasztani (k ≤ n). Egy elem csak egyszer választható, a sorrend nem számít.

A különböző kiválasztások száma:

C n k = n · ( n 1 ) · ( n 2 ) · . . . ( n k + 1 ) k ! = n ! k ! · ( n k ) ! = ( n k )

Példa:

5 elemből {a,b,c,d,e} kettőt választva: C 5 2 = 5 ! 2 ! · ( 3 ) ! = ( 5 3 ) = 10

(a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), (d,e)

Ismétléses kombináció

n különböző elem közül k elemet kell kiválasztani. Egy elem töbször is kiválasztható, a sorrend nem számít.

A különböző kiválasztások száma:

C ¯ n k = ( n + k 1 k )

Példa:

4 elemből {a,b,c,d} ki kell választani kettőt, úgy hogy az elemek ismétlődhetnek:

Az összes lehtséges eset száma tehát: C ¯ 4 2 = ( 4 + 2 1 2 ) = ( 5 2 ) = 10

(a,a), (a,b), (a,c), (a,d), (b,b), (b,c), (b,d), (c,c), (c,d), (d,d)