Matematika III. 1., Kombinatorika
Prof. Dr. Závoti József (2010)
Nyugat-magyarországi Egyetem
1.4 Kombináció

1.4 Kombináció

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

Definíció:

Adott n különböző elem. Ha n elem közül elemet úgy választunk ki, hogy mindegyik csak egyszer kerül sorra, és a kiválasztás sorrendje nem számít, akkor az n elem egy k-ad osztályú ismétlés nélküli kombinációját kapjuk.

Jele:

Példa 1:

Írjuk fel az a, b, c, d elemek 2-od osztályú ismétlés nélküli kombinációit

Megoldás:

ab

bc

cd

ac

db

ad

Tétel:

Az n különböző elem k-ad osztályú ismétlés nélküli kombinációinak száma:

Bizonyítás:

Az n elem k-ad osztályú ismétlés nélküli kombinációinak száma megegyezik a k darab kiválasztott és az n-k ki nem választott elem ismétléses permutációinak számával:

Definíció:

Az kifejezést binomiális együtthatónak nevezzük.

Megegyezés alapján:

A binomiális együttható fogalma általánosítható tetszőleges valós számra:

Legyen

Következmény:

Ha , akkor .

Példa 2:

1, 2, 3, 4, 5 elemek 3-ad osztályú kombinációi:

+ + + - -

+ + - + -

+ + - - +

+ - + + -

+ - + - +

+ - - + +

- + + + -

- + + - +

- + - + +

- - + + +

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

Példa 3:

A lottóhúzásnál 90 számból öt számot választanak ki visszatevés nélkül, és a sorrend nem számít, ezért ismétlés nélküli kombinációról van szó.

1.4.2 Ismétléses kombináció

Definíció:

Adott n különböző elem. Ha n elem közül k elemet úgy választunk ki, hogy egy elem többször is sorra kerülhet, és a kiválasztás sorrendje nem számít, akkor az n elem egy k-ad osztályú ismétléses kombinációját kapjuk.

Jele:

Példa 1:

Írjuk fel az a, b, c, d elemek 2-od osztályú ismétléses kombinációit!

aa

ab

ac

ad

bb

bc

bd

cc

cd

dd

Tétel:

Az n különböző elem k-ad osztályú ismétléses kombinációinak a száma:

Bizonyítás:

Az n elem k-ad osztályú ismétléses kombinációinak száma megegyezik n+k-1 elemből k kiválasztott elem és n-1 ki nem választott elem ismétléses permutációinak számával:

Példa 2:

Írjuk fel az 1, 2, 3 számok 4-ed osztályú kombinációit!

Megoldás:

1 2 3 4 5 6

+ + + + - -

+ + + - + -

+ + + - - +

+ + - + + -

+ + - + - +

+ + - - + +

+ - + + + -

+ - + + - +

+ - + - + +

+ - - + + +

- + + + + -

- + + + - +

- + + - + +

- + - + + +

- - + + + +

1 1 1 1

1 1 1 2

1 1 1 3

1 1 2 2

1 1 2 3

1 1 3 3

1 2 2 2

1 2 2 3

1 2 3 3

1 3 3 3

2 2 2 2

2 2 2 3

2 2 3 3

2 3 3 3

3 3 3 3