Matematika érettségi

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: k1 db azonos, k2 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ő…

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

Pnk1,k2…kr=n!/k1!*k2!*…kr! egyszer többször is csak egyszer többször

k1+k2+…+kr=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

Cnk=(n /alatt/ k) kombináció Vnk=n!/(n-k)! vari-

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

Vnk,i=nk

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=(n /alatt/ 0)an+(n /alatt/ 1)an-1b+…+(n /alatt/ n-1)abn-1+(n /alatt/ n)bn

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

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

nk=0(n /alatt/ k)an-kbk

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 Pn szimbólummal jelöljük.

Tétel: n (n єN+) különböző elem permutációinak száma Pn=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 P1=1! Egy elemet csak egyféleképpen lehet leírni, így P1=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 Pk=k!

  3. Következik-e ebből n=k+1 esetére is az állítás, azaz Pk+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

Pk+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 Pn=n!, minden pozitív egész szám esetén igaz.

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük