Ugrás a tartalomhoz

Matematika III. 1., Kombinatorika

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

Nyugat-magyarországi Egyetem

1.2 Permutáció

1.2 Permutáció

1.2.1 Ismétlés nélküli permutáció

Definíció:

Adott n elem. Az elemek egy meghatározott sorrendjét az adott n elem egy ismétlés nélküli permutációjának nevezzük.

Példa 1:

Írjuk fel az a, b, c elemek összes permutációját!

Megoldás: abc, bac, cab, acb,bca, cba

Definíció + eljárás:

Lexikografikus sorrend:

Létezik egy természetes sorrend, az elemek nagyság szerint nem csökkenő sorrendje.

  1. Megkeresni az utolsó számot, amely mögött még van nála nagyobb szám!

  2. E szám előtti számokat leírni!

  3. E szám helyére beírni a nálánál nagyobb elemek legkisebbikét!

  4. A megmaradt elemeket természetes sorrendben leírni!

Példa 2:

Adjuk meg az 1,2,3,4 számok összes permutációját lexikografikus sorrendben!

Megoldás:

1234

2134

3124

4123

1243

2143

3142

4132

1324

2314

3214

4213

1342

2341

3241

4231

1423

2413

3412

4312

1432

2431

3421

4321

Tétel:

Az n különböző elem permutációinak száma: , ahol , és .

Definíció:

Hasznos a Stirling-formula, amellyel n! a következőképp becsülhető:

Bizonyítás:

Az első helyen az 1,2,...,n elemek mindegyike állhat, utána a maradék n-1 elem összes lehetséges sorrendje következik. És így tovább, az utolsó elemig. Az összefüggéseket visszafelé felírva adódik az állítás.

Példa 3:

5 távolugró sportoló életkora: 19, 20, 21, 23 és 26 év.

Egy versenyen az életkoruk alapján hányféle sorrend fordulhat elő?

Megoldás:

Példa 4:

Hány tíz jegyű szám van, amelyben minden számjegy egyszer fordul elő?

Megoldás:

Az összes lehetséges sorrend 10! Ha a 0 az első helyen szerepel, maradék 9 szám összes lehetséges sorrendje: 9! Így a valóban különböző tízjegyű számok száma:

10! - 9! = 9! (10-1) = 9 · 9!

Egy másik megoldás:

9

9

8

7

6

5

4

3

2

1

Példa 5:

Hányféleképpen ültethető le 4 férfi és 5 nő egy padra, ha felváltva ülnek.

x

y

x

y

x

y

x

y

x

Megoldás:

4! ·5! = 24 · 120 = 2880.

1.2.2 Ismétléses permutáció

Definíció:

Adott n elem, amelyek között k1 db egyenlő, másik k2 db egyenlő, ... másik ks db egyenlő, ahol

Az adott n elem egy meghatározott sorrendjét ezen elemek egy ismétléses permutációjának nevezzük.

Jele:

Példa 1:

Származtassuk az a, b, b elemek ismétléses permutációját az ismétlés nélküli permutációból!

Tétel:

Adott n, s és esetén az ismétléses permutációk száma:

Bizonyítás:

Tekintsük az n elem egy tetszőleges permutációját!

azonos elemhez különböző indexet rendelhetünk,

azonos elemhez különböző indexet rendelhetünk,

...

azonos elemhez különböző indexet rendelhetünk.

Ekkor fenn áll az alábbi összefüggés:

Példa 2:

Az előbbi szemléltető példa ismétléses permutációinak száma:

Példa 3:

Ha 5 magasugró sportoló közül kettő 19 éves, egy 20 éves és kettő 21 éves van, akkor

Példa 4:

A totó 13 mérkőzése közül 7 hazai győzelem (1), 3 döntetlen és 3 vendéggyőzelem született.

Hány szelvényt kellett volna kitölteni a biztos 13-as találathoz?

Megoldás: