Kombinatorika. A valószínűség kiszámításának kombinatorikus modellje

Kombinatorikai alapfogalmak

Az elemeket sorrendbe állítjuk Az elemek közül k darabot, kiválasztunk

(permutáció)

Az elemek mind Az elemek között A kiválasztott elemek A kiválasztott elemek

Különbözőek: k₁ db azonos, k₂ db sorrendje nem lényeges: sorrendje lényeges:

Ismétlés nélküli azonos, az előzőtől Kombináció Variáció

Permutáció Különböző…

P_n=n! Ismétléses permutáció Egy elemet Egy elemet Egy elemet Egy elem

P_n^k₁^,k₂^…k_r=n!/k₁!*k₂!*…k_r! egyszer többször is csak egyszer többször

k₁+k₂+…+k_r=n választhatok kiválaszt- választhatunk: is kivál-

ki: ismétlés hatunk: ismétlés nélküli asztható:

nélküli kombináció Ismétléses variáció ismétléses

C_n^k=(n /alatt/ k) kombináció V_n^k=n!/(n-k)! vari-

C_n^k,i=(n+k-1 /alatt/ k) áció

V_n^k,i=n^k

n!=1*2*3*…*n

A binomiális tétel

A kéttagú összeg (binom) bármely n є N kitevőjű hatványa az alábbi módon írható fel:

(a+b)ⁿ=(n /alatt/ 0)aⁿ+(n /alatt/ 1)a^n-1b+…+(n /alatt/ n-1)ab^n-1+(n /alatt/ n)bⁿ

ahol az (n /alatt/ k) binomiális együtthatókat a következő módon értelmezzük:

(n /alatt/ k)= n!/k!(n-k)!

∑ⁿ_k=0(n /alatt/ k)a^n-kb^k

Definíció: Ha az adott n különböző elemet (n є N⁺) minden lehetséges módon elrendezünk, akkor a kombinatorika nyelvén azt mondjuk, hogy az illető elemeket permutáljuk, s ismétlés nélküli permutációról beszélünk. A permutációk számát a P_n szimbólummal jelöljük.

Tétel: n (n єN⁺) különböző elem permutációinak száma P_n=N!

Bizonyítás: teljes indukcióval

1. Nézzük meg, hogy n=1 esetén igaz-e az állítás, vagyis az, hogy P₁=1! Egy elemet csak egyféleképpen lehet leírni, így P₁=1=1! Tehát az állítás n=1 esetén igaz.

2. Tegyük fel, hogy n=k esetén (k є Z⁺) is igaz az állítás, vagyis k különböző elem permutációinak száma P_k=k!

3. Következik-e ebből n=k+1 esetére is az állítás, azaz P_k+1=(k+1)!?

A k+1 elemből vegyünk ki egy tetszőleges elemet és helyezzük el az első helyre. Ekkor a maradék k elemet k! módon tudjuk sorba rakni utána. Ha az első helyre mindig más-más elemet választunk ki, akkor a lehetséges esetek száma k+1 és mindegyik esetben az első elem után k! módon tudjuk sorrendbe rakni a többi k elemet. Így tehát k+1 elem összes permutációinak száma

P_k+1=(k+1)k!=(k+1)k(k-1)(k-2)*…*3*2*1=(k+1)!

Eszerint abból, hogy valamely k є Z⁺ számára igaz a vizsgált tétel, következik, hogy ez igaz a k+1 számra is. A teljes indukciós gondolatmenetnek tehát az, hogy P_n=n!, minden pozitív egész szám esetén igaz.