Page 133 - vol2

15. Permutációegyenletek megoldása

Az elemi kombinatorikában n elem egy permutációján az n darab
elem egy meghatározott sorrendjét (sorbarendezését) értjük. Legyen az n
darab elem a következő rendezett A halmaz eleme: A={a1, a2, …, an}.
Matematikailag legtermészetesebben úgy definiálható ekkor az A egy
permutációja, hogy az egy f:{1,2,…,n}→A kölcsönösen egyértelmű
függvény (minden számhoz 1-től n-ig az A egy és csak egy elemét
rendeljük, azaz „sorba rendezzük”). Azonban a felsőbb matematikában
mégsem így, hanem a halmazok önmagára való bijektív leképezéseként
definiálják a permutációkat (utóbbi definíció nem-megszámlálható
halmazokra is értelmes fogalmat ad). Egy permutációt úgy adhatunk
meg, hogy zárójelben (általában vesszővel) felsoroljuk az elemeit, vagy
például n=5 esetén az f(1)=a5, f(2)=a2, f(3)=a1, f(4)=a3,
f(5)=a4 permutációt a következő rövidebb alakokban adhatjuk meg:

 1 2 3 4 5 
 
 a 1 a 2 a 3 a 4 a 5 

Még rövidebb, ha a második sorban csak az elemek indexeit írjuk ki
(mintha azonosítanánk A-t az {1,2,…,n} halmazzal):

 1 2 3 4 5
 
 5 2 1 3 4 

A legrövidebben pedig, ha az elemeknek a séma felső sorában szereplő
„természetes sorrendjét” is elhagyjuk, és csak a képelemeket írjuk ki:
(5, 2, 1, 3, 4). Akadnak szerzők, akik ez utóbbit a permutáció „Descartes-
féle alakjának” nevezik. Az így bevezetett permutációkkal végezhető
művelet a tankönyvekben is megtalálható permutációk szorzása. Ez a
művelet általában nem kommutatív, de asszociatív, van semleges elem az
azonos permutáció és minden permutációnak van inverz permutációja.
Az n-ed rendű permutációk halmazát Sn-el jelöljük. Az érvényben levő
tankönyvekben, továbbá értelmezik és vizsgálják a permutációk
transzpozícióit (elemcseréit) és inverzióit. Egy adott  permutációnak

133