Ugrás a tartalomhoz

Matematika III. 1., Kombinatorika

Prof. Dr. Závoti József (2010)

Nyugat-magyarországi Egyetem

1.5 A kombinatorika alkalmazásai

1.5 A kombinatorika alkalmazásai

1.5.1 Binomiális tétel

Tétel:

Binomális tétel:

Kéttagú kifejezés (binom) bármely nemnegatív egész kitevőjű hatványa polinommá alakítható:

-ahol , és .

A polinom jellemzői:

  1. A polinom tagból áll.

  2. Minden tagban az alakú kifejezés kitevőinek összege n.

  1. A bk kitevője megegyezik kifejezés alul szereplő értékével.

Bizonyítás:

Tekintsük az alábbi n tényezős szorzatot:

Ha mindegyik tényezőből az a –kat szorozzuk össze, kapjuk:

an

Ha tényezőből az a-kat, és 1 tényezőből b-t választjuk, n féleképp tehetjük ezt meg, kapjuk:

Ha tényezőből az a-kat, és 2 tényezőből b-ket választjuk, féleképp tehetjük ezt meg, kapjuk:

.

Teljes indukcióval adódik a tétel állítása.

Speciális esetek:

A középiskolai tananyagból jól ismert speciális esetek:

Példa 1:

1.5.2 Pascal-háromszög

Írjuk fel a binomiális együtthatókat az alábbi formában:

A Pascal-háromszög tulajdonságainak jellemzésére szolgál az alábbi tétel:

Tétel:

A Pascal-háromszög tulajdonságainak jellemzésére szolgál az alábbi tétel:

Legyen n nemnegatív egész szám, és legyen szintén egész. Ekkor fennállnak a következő összefüggések:

  1. -szimmetria tulajdonság

  2. -összegzés

  3. -kettőhatvány

Bizonyítás:

  1. =

  2. Helyettesítsünk a binomiális tételbe -et!

  3. Helyettesítsünk a binomiális tételbe -et!

Tétel:

Ha m, n és k nemnegatív egész számok, akkor

Bizonyítás:

Egy urnába helyezzünk m db fekete, és n darab fehér golyót! Húzzunk ki k darab golyót!

Hányféleképp tehetjük meg?Lehetőségek: mind a k darab golyót a fehérek közül húzzuk, egy golyót a feketék , k-1 darab golyót e fehérek közül húzunk, stb

1.5.3 Generátorfüggvény

Definíció:

Legyen adott egy végtelen sorozat.

Tegyük fel, hogy az

hatványsor nem csak a 0 helyen konvergens.

Ekkor az függvényt az adott sorozat generátorfüggvényének nevezzük.

Példa 1:

Legyen

írjuk fel a MacLaurin sort !

Megoldás:

Tétel:

Az binomiális együtthatók generátorfüggvénye:

Bizonyítás:

A binomiális tételben végezzük el a következő helyettesítéseket .