KOMBINATORIKA. Készítette: Bordi István Tóth Árpád Gimnázium Debrecen,

KOMBINATORIKA

1

Tóth Árpád Gimnázium

Készítette: Bordi István Tóth Árpád Gimnázium Debrecen, [email protected]

DEBRECEN

Matematika-Kombi001

2005.03.18.

A KOMBINATORIKA TÁRGYA Kérdések: 1. n elemet hányféleképpen lehet egymás mellé tenni (permutáció). 2. n elemből hányféleképpen lehet kiválasztani k elemet úgy, hogy a sorrend nem számít (kombináció). 3. n elemből hányféleképpen lehet kiválasztani k elemet úgy, hogy a sorrend számít (variáció). 2 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Példák: a) Hányféleképpen tölthető ki egy lottószelvény? b) Hány értelmes vagy értelmetlen szó képezhető a MATEMATIKA szó betűiből? c) Hányféleképpen lehet négy játékos között kiosztani az 52 lapos francia kártyát? d) Hány háromjegyű szám képezhető az 1, 2, 3, 5 számjegyekből? e) Hányféle módon ülhet le 6 személy egy padra egymás mellé, és hányféleképpen helyezkedhet el egy kerek asztal körül? 3 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

1. PERMUTÁCIÓK 1.1. ISMÉTLÉS NÉLKÜLI ESET  DEFINÍCIÓ: n különböző elem egy sorrendjét az n elem egy permutációjának nevezzük.

4 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Példa: Legyen: a, b, c. Permutációk pl.: b c a, c a b, a c b, stb. Mennyi a permutációk száma? Vegyük az {1,2,3} halmazt. A lehetséges permutációk 3 2 1 2 3 1 3 1 2

2 3

Tóth Árpád Gimnázium

DEBRECEN

3 1 2 1 Matematika-Kombi001

5 2005.03.18.

T: n számú elem összes permutációinak száma Pn. Pn = n(n - 1)(n - 2)...3•2•1 = n! n!= n(n - 1)(n - 2) ...2•1 Megjegyzés. 1. n! = n(n-1)! ezért a fenti képlet így is írható: Pn = nPn-1 (rekurzív képlet). 2. Definíció szerint 0! = 1, és 1!=1. Példa. Írjuk le 4 elem lehetséges permutációit. abcd bacd cabd dabc abdc badc cadb dacb acbd bcad cbad dbac acdb bcda cbda dbca adbc bdac cdab dcab adcb bdca cdba dcba 6 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

MEGJEGYZÉS

1. Az n növekedésével az n! nagyon erősen növekszik. Például 10!=3 628 800 2. Az n! közelítésére a Stirling formulát használhatjuk:

n! 2 e n n

n

1 2

7 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

1.2. ISMÉTLÉSES ESET

DEFINÍCIÓ: Ismétléses permutáció n, nem feltétlen különböző elem egy sorrendjét az n elem ismétléses permutációjának nevezzük.

8 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

T: n elem ismétléses permutációinak száma: Pn

k1 , k 2 ,..., k r



n! k1!k 2 !...k r !

(k1  k 2  ...  k r  n).

Példa. Az 1, 1, 2, 3 elemek esetén: 4! 4  3  2 1 P4; 2    4  3  12. 2! 2 1

Példa. A MATEMATIKA szó betűiből alkotott összes ismétléses permutációk száma: 10!  151200. 3!2!2! 9 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

2. VARIÁCIÓK

2.1. ISMÉTLÉS NÉLKÜLI ESET DEFINÍCIÓ: Az n különböző elem közül kiválasztott k különböző elem (n k) egy sorrendjét az n elem k-ad osztályú ismétlés nélküli variációjának nevezzük.

10 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

2.1. ISMÉTLÉS NÉLKÜLI ESET T: Az ismétlés nélküli variációk száma Vnk , n! Vn   nn  1...n  k  1 (n  k )! k

1 2 3

k-1 k

(n-1)-féleképpen n-féleképpen 11 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Példa: Hány háromjegyű szám képezhető az 1,2,3,4,5 számjegyekből, ha ugyanaz a számjegy minden számban csak egyszer fordul elő? Megoldás: 5! 5  4  3  2! V5;3    60. 2! 2!

Példa: Egy 30 fős csoportból hányféleképpen állíthatunk össze elnökből, alelnökből, titkárból és pénztárosból álló vezetőséget? Megoldás: V 30 ; 4 = 30 • 29 • 28 • 27 = 657720. 12 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

PÉLDA

Egy 30 fős csoportból hányféleképpen állíthatunk össze elnökből, alelnökből, titkárból és pénztárosból álló vezetőséget? Megoldás: V 30 ; 4 = 30 • 29 • 28 • 27 = 657720.

13 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

DEFINÍCIÓ: Az n különböző elemből kiválasztott k, nem feltétlen különböző elem egy sorrendjét az n elem k-ad osztályú ismétléses variációjának nevezzük. T: Az n elem k-ad osztályú ismétléses variációinak a száma: k ,i k

Vn  n .

14 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Példa: Írjuk fel az 1, 2, 3, 4 elemek másodosztályú ismétléses variációit! Megoldás: 11 21 31 41 12 22 32 42 13 23 33 43 14 24 34 44 Példa: Hány totószelvényt kell kitöltenünk (különböző módon) ahhoz, hogy biztosan legyen köztük 13 találatos? Megoldás: Ismétléses variációról van szó tehát V3i;13  313  1594323 15 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

3. KOMBINÁCIÓK 3.1. ISMÉTLÉS NÉLKÜLI ESET DEFINÍCIÓ: Az n különböző elemből kiválasztott k elemet az n elem k-ad osztályú ismétlés nélküli kombinációjának nevezzük. T: Az ismétlés nélküli kombinációk száma: n n! n(n  1)  (n  k  1) Cn;k      k!  k  k !n  k ! n  Megjegyzés:    1 0 Példa: Hányféleképpen lehet kitölteni egy lottószel16 vényt? Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Megoldás:  90  90  89  88  87  86  43949268   1 2  3  4  5 5  3.2. ISMÉTLÉSES ESET DEFINÍCIÓ: Az n különböző elem közül kiválasztott k, nem feltétlen különböző elemet az n elem k-ad osztályú ismétléses kombinációjának nevezzük. T: Az n elem k-ad osztályú ismétléses kombinációi száma: C   n kk  1 i n;k





Példa: 7 elemből hány olyan hármas csoport nyerhető, ahol az elemek sorrendjére nem kell tekintettel lenni, és ugyanazt az elemet egy csoportban akár 3-szor is fel lehet tüntetni? 17

Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Megoldás: i 7 ;3

C

 7  3  1  9        84. 3  3

Példa: 4 pénzérmét dobunk fel egyszerre. Hányféle eset lehetséges a fej, írás kombinációkra? Megoldás:  2  4  1  5        5  4   4

18 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

4. A BINOMIÁLIS TÉTEL ÉS A PASCAL-HÁROMSZÖG  n  n  n  n1  n  n2 2 a  b    a   a b   a b  ...  0 1  2 n  n  n1  n   n  nk k  ab   b    a b k 0  k   n  1 n n

n

n   binomiális együttható; Binomiális tétel k   Ezekből az alábbi Pascal háromszöget kapjuk. 19 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

0   0  1   1      0   1  2  2  2        0  1   2   3   3  3   3          0  1   2   3 

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

20 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

Tulajdonságok: 1. Szélső elemek:

n  n       1 0 n  n  n     k  n  k 

2. Szimmetria: 3. Összeg tulajdonság:

 n   n   n  1      k   k  1  k  1

4. Az n-edik sor elemeinek összege: n n n n (1  1)      2 k 0  k  21 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.

22 Tóth Árpád Gimnázium

DEBRECEN

Matematika-Kombi001

2005.03.18.