Megoldás. Először próbáljuk kitalálni, merre érdemes keresgélni. Ha minden lépésben csak egy cserét engednénk, akkor, mint ismeretes, $n-1$ csere elég volna (és kevesebb nem mindig). A mi feladatunk megengedi, hogy egy lépésben $\frac{n}{2}$ cserét is végrehajtsunk. A kérdés az, hogy reménykedhetünk-e, hogy két ilyen lépés is elég.
A válaszhoz gondolatban készítsünk el egy irányított gráfot, amelyben minden tanulótól ahhoz a tanulóhoz indul él, akinek a mostani helyére kell állnia. Ha egy tanuló jó helyen áll, akkor egy irányított hurokél tartozik hozzá. Formálisabban: a csúcsok az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számok, ahol $n$ az osztály létszáma. Ha a névsorban $k$. helyen levő tanuló a nagyság szerinti sorban az $l$-edik, akkor a ,,$k$'' csúcsból az ,,$l$'' csúcsba mutat él. Így egy olyan irányított gráfot kapunk, amely irányított körökből áll (körnek tekintjük a hurokélt és azt is, ha két pont között mindkét irányban fut él). A körök pont- (és él-)diszjunktak. A feladat az, hogy minden ilyen kör mentén az irányítás mentén eggyel arrébb kerüljön minden tanuló.
Nézzük tehát először azt az esetet, ha a gráf egyetlen körből áll. Gondolatban ültessük a nyilak szerint egy kör alakú asztalhoz a tanulókat. (Ez persze nagyon megkavarja a tényleges sorrendjüket ‐ erre még visszatérünk ‐, de ezzel egyelőre ne törődjünk.) A következő feladathoz jutunk:

 

2. feladat. Egy osztály tanulói körben állnak. Az a feladat, hogy mindenki a tőle eggyel jobbra álló helyére kerüljön. Egy lépés most is ugyanaz, mint az előző feladatban, a tanulók száma $n$. Hány lépésben $(=$ hány sípszóval$)$ érhető el, ha egy lépés most is az, ami az előző feladatban.

 

Ha ezt a feladatot megoldottuk (a megoldást lásd alább), utána már hamar befejezhetjük a megoldást abban az esetben is, amikor az eredeti feladatban az irányított gráf több körből áll. Gondolatban minden körnek megfeleltetünk egy-egy ilyen szabályos sokszöget. Mindegyikben egyszerre végre tudjuk hajtani a két lépést, hiszen a körök pontdiszjunktak, tehát a benne szereplő tanulók egymástól függetlenül párosíthatók és mozgathatók. Tehát összességében is két lépésben célhoz juthatunk. Egy lépés nem mindig elég.
Adósak vagyunk még a 2. feladat megoldásával:
Feltehetjük, hogy egy szabályos $n$ szög csúcsaiban állnak a tanulók. A feladat: el kell forgatni a szabályos sokszöget $360/n$ fokkal. Ismeretes, hogy ez a sokszög két ,,szomszédos'' tükörtengelyére való tükrözéssel megvalósítható, amelyek tengelye $180/n$ fokos szöget zárnak be egymással. Egy tükrözésnél diszjunkt párok cserélnek helyet. (Ha $n$ páros, akkor az egyik tükrözésnél mindenkinek van párja, a másikban két szemközti csúcsban állónak nincs. Ha $n$ páratlan, akkor mindkét alkalommal egy-egy tanulónak nincs párja.)
Tehát két lépésben célhoz érhetünk. Egy lépés nyilván nem elég.

 

1.1. Az 1. feladat megoldásának elemzése

Meg akarjuk vizsgálni részletesen, hogy mit is csináltunk az 1. feladat megoldásában. Ehhez előre bocsátunk egy didaktikai megjegyzést.
Bármennyire kézenfekvő az a gondolat, hogy a permutációt ciklusokra bontva szemléljük, mégsem könnyen érthető egy, a permutációk szerkezetével most ismerkedő tanulónak. Van benne egy absztrakciós lépés. Közelebbről: egy számsorozatot, az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számok egy adott sorrendbeli leírását nem ,,készen adottnak'' tekintjük, hanem egy mozgásnak, függvénynek. A csoportelméletben ez nagyon hasznos szemlélet. Itt a feladat szövege is sugallja ezt az absztraktabb szemléletet. De ettől még igaz marad, ami minden absztrakciós lépéssel kapcsolatban igaz: aki még nem jutott el hozzá, annak van benne valami megfoghatatlan, míg aki már elsajátította, az nehezen tud emlékezni arra a szituációra, amikor még nem értette. Ez egy olyan nehézség a matematika tanításánál, amit ha nem veszünk nagyon komolyan, akkor nem szabad csodálkoznunk, ha a matematikát valami akár elutasító (ez a gyakoribb), akár ködösen áhítatos borzongás veszi körül. Erre mindig újra figyelmeztetnünk kell magunkat, ha nem akarunk annak a kollégámnak a sorsára jutni, aki a többi tanárral úgy utáltatta meg magát és a matematikát, hogy egy irodalomból, történelemből igen jó diákot butának titulált, ,,még egy elsőfokú egyenletet sem tud rendezni'' felkiáltással. Hogy a mi esetünkben mi a nehézség, azt a legegyszerűbb eset részletes elemzésével is szemléltetjük. Az alábbiakban ehhez végigkövetjük a 2. feladat megoldását egy konkrét példán.
Legyen az egyszerűség kedvéért 8 tanuló az osztályban, és a névsor szerinti sorban álljanak a következő nagyság szerinti sorrendben:

$\begin{array}{c}{\displaystyle 43852716.}\end{array}$

Tehát az első helyen a negyedik legmagasabb áll, a második helyen a harmadik legmagasabb stb. Amikor gondolatban átrendeztük őket, akkor az ábrán látható első sorrendet kapjuk.

 

 

 

Az első lépésben az első ábrán látható párok cserélnek helyet: (1 4), (5 7), (2 6), (3 8). Így az ábrán látható második sorrendet kapjuk. A második lépésben az 1 és a 3 helyben marad (erre a tengelyre tükrözünk), helyet cserélnek a következő párok: (4 7), (6 5), (8 2). Most az ábrán látható utolsó sorrendet kapjuk. Mint látjuk, valóban eggyel elforgattuk a kört.
De mit jelent ez a feladatunk szempontjából? Tényleg azt kaptuk, amit akartunk? És ha igen, hogyan kell a tanárnak a párokat kijelölnie?
Arról könnyen meggyőződhetünk, hogy az első lépésben nem a legmagasabbat és a negyedik legmagasabbat kell felcserélnünk. Jobban meg kell értenünk, mi is történt.
Nézzük, mi történt valójában az első lépésben. Az eredeti sor így nézett ki: 4 3 8 5 2 7 1 6. Itt helyet cserélt az első és a negyedik helyen álló, az ötödik és hetedik helyen álló, a második és hatodik helyen álló, valamint a harmadik és nyolcadik helyen álló. A tényleges sor most tehát így alakult: 5 7 6 4 1 3 2 8.
Az első ábrán látható 4 1 7 6 8 3 2 5 (4) kör az eredetileg rendre a 4., 1., 7. stb. helyen állókat jelenti, tehát a nagyság szerinti sorrend szerint írva az 5 4 1 7 6 8 3 2 (5) körről van szó. Amikor azt mondtuk, hogy a második lépésben az 1 és a 3 helyben marad, akkor azt mondtuk, hogy az eredetileg ezeken a helyeken állók maradnak a helyükön, vagyis a 4. és 8. legmagasabb. És ez rendben is van: ők valóban a 4., illetve a 8. helyen állnak. A második lépésben lezajló (4 7) csere azt jelenti, hogy az eredetileg a 4. és 7. helyen álló helyet cserél, ami az 5. legmagasabb és a legmagasabb helycseréjét jelenti, ez megint csak jó, hiszen most az ötödik legmagasabb áll az első helyen és a legmagasabb az ötödik helyen. Ugyanúgy ellenőrizhető, hogy a további két csere után valóban a nagyság szerinti sorrendet kapjuk.
Ez a példa elég világosan mutatja, hogy csak látszólag egyszerű elvonatkoztatni a konkrét sorrendtől és áttérni egy gondolatbeli sorrendre. Valójában egy dinamikusabb nyelvre fordítottunk és ezzel tettünk egy absztrakciós lépést. Nem könnyű az eredeti nyelven követni, hogy valójában mi is történik. De vigyázzunk: nem akkor sajátítottunk el egy absztrakciós lépést, ha problémátlanul vissza tudjuk követni a konkrét esetben ‐ ez korántsem egyszerű általában ‐, hanem ha biztosnak érezzük magunkat, hogy a követés nehézségei ellenére is végig tudjuk követni a konkrét történést, ,,át tudjuk dolgozni''! Ha erről a követésről lemondunk, akkor az absztrakció a levegőben fog lebegni, nem fogjuk látni, hova vezet tovább. Ha viszont megijedünk, hogy nem megy kapásból, akkor nem fogjuk magunknak igazán elhinni, hogy képesek vagyunk felfogni az absztraháló lépést.
Ezután rátérhetünk az 1. feladat megoldásának az elemzésére.
A névsor szerint sorban álló tanulókat megsorszámoztuk, majd ebből a sorrendből akartunk egy másik sorrendhez, azaz permutációhoz eljutni. A permutációk felírásának szokásos módja az, hogy a felső sorba felírjuk az eredeti sorrendet (ezt néha el is hagyjuk), és alá az elérendőt. Legyen ez például a következő (az egyszerűség kedvéért 12 tagú osztályt választunk):

 

${\displaystyle \begin{array}{|cccccccccccc|}\hline \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{8}}\hfill & \hfill {\displaystyle \text{9}}\hfill & \hfill {\displaystyle \text{10}}\hfill & \hfill {\displaystyle \text{11}}\hfill & \hfill {\displaystyle \text{12 }}\hfill \\ \hfill {\displaystyle \text{4}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{8}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{10}}\hfill & \hfill {\displaystyle \text{7}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle \text{5}}\hfill & \hfill {\displaystyle \text{11}}\hfill & \hfill {\displaystyle \text{2}}\hfill & \hfill {\displaystyle \text{9}}\hfill & \hfill {\displaystyle \text{12 }}\hfill \\ \hline\end{array}}$

 

Mi ehelyett elkészítettük a következő, irányított körök diszjunkt uniójából álló gráfot:

 

 

 

 

 

Ezeket a köröket nevezzük a permutáció ciklusainak. Most kódolhatjuk ezt a permutációt úgy is, hogy egymás után leírjuk az egyes ciklusokat és zárójellel választjuk őket el egymástól. A fenti esetben: (1 4 6 7) (2 3 8 5 10) (9 11) (12).
Ez a permutáció ciklus-szerkezete.
Nyilvánvaló, hogy ebből a felírásból is ,,visszafejthetjük'' a permutáció eredeti felírását. Tetszőleges ilyen ciklus-szerkezetet felírhatunk, csak arra kell vigyáznunk, hogy minden elem pontosan egy ciklusban szerepeljen, és akkor egyértelműen ,,visszafejthető'' lesz. (Megjegyezzük, hogy ha ismert a halmaz, amelyen a permutáció hat, akkor az egyelemű ciklusokat szokás nem kiírni.)
Ugyanannak a permutációnak a ciklus-szerkezetét azonban többféleképpen is felírhatjuk. Két okból is. Egyrészt a ciklusok sorrendje (egyelőre legalábbis) tetszőleges, másrészt az egyes ciklusokat bármely tagjuktól kezdve is felírhatjuk. Az első helyett írhatnánk pl. (6 7 1 4)-et, a második helyett pl. (3 8 5 10 2)-t, a harmadik helyett (11 9)-et is. Tehát a fenti permutációt így is írhatjuk: (11 9) (6 7 1 4) (3 8 5 10 2), és még sokféleképpen.
Ennek a ciklikus felírási módnak a csoportelméletben is sok haszna van (lásd erről pl. Hegedüs Pál feladatsorát¹). Mi most a véletlen permutációk felé vesszük az irányt, amelyek szintén jobban megfoghatók innen nézve.
Természetesen, ha tanítani támad kedvünk a ciklikus szerkezetet, akkor érdemes gyakoroltatni konkrét permutációk felírását. És érdemes azt is kipróbálni, hogy két permutáció szorzatát hogyan kaphatjuk meg ezzel a felírással gyorsan és mechanikusan. De erre itt nincs szükségünk.

 

2. Véletlen permutációk
2.1. A permutációk újrakódolása

A következő feladat szintén a permutáció ciklusairól szól, de most már véletlen permutációról van szó.

 

3. feladat. Az osztály most moziba megy. Egy sorba szól a jegyük, egymás mellé. Mindenki el is megy a moziba, de egyesével, véletlen sorrendben érkeznek. Ahogy megjönnek, mindenki leül az első üres székre, függetlenül attól, hogy hova szól a jegye. (Az elsőnek érkező az első helyre stb.) Amikor már mindenki leült, az utolsó helyen ülőnek eszébe jut, hogy ő mégis ott szeretne ülni, ahova a jegye szól. Megnézi, hova szól, és ha épp ott ül, akkor nem tesz semmit. Ha nem oda szól, akkor felállítja azt, aki a helyén ül és helyet foglal. Akit felállított, az most már maga is oda akar ülni, ahova a jegye szól. Két eset van: vagy épp az üres helyre szól a jegye, akkor leül oda, vagy foglalt a helye, akkor felállítja az ott ülőt, és leül a helyére. Ez folytatódik, amíg ahhoz nem érnek, akinek a jegye a még üres helyre szól. Ő is leül a helyére és kezdődhet az előadás. Mennyi a valószínűsége, hogy az első helyen ülőnek nem kell felállnia?

 

1. megoldás. Ki tudjuk számolni. Az ellentét eseményt számoljuk ki, azt tehát, hogy hány olyan permutáció van, amelyben az első helyen ülőnek fel kell állnia. Az a kérdés, hogy hány olyan permutáció van, amelyben az utolsó helyen ülő és az első helyen ülő tanulók ugyanabban a ciklusban vannak. Ha ez a ciklus $k$ embert mozgat meg, akkor még $k-2$ embert kell kiválasztanunk, ezt $\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)$-féleképpen tehetjük meg. Utána őket még $\left(k-1\right)!$-féleképpen lehet sorba tenni. (Az utolsó helyen ülő jegye a másik $k-1$ helyének bármelyikére szólhat, a ciklusban következőé még $k-2$ hely bármelyikére stb.). A maradó $n-k$ ember pedig akárhogy permutálható egymás között, ez $\left(n-k\right)!$-féleképpen lehetséges. Összeszorzásukkal $\left(n-2\right)!\left(k-1\right)$ adódik. Ezt kell minden lehetséges $k$-ra, tehát $k=\mathrm{2,}\text{...}\mathrm{,}n$-re összeadnunk. Az összeg

$\begin{array}{c}{\displaystyle \left(n-2\right)!\frac{n\left(n-1\right)}{2}=\frac{n!}{2}\mathrm{,}}\end{array}$

és ez a permutációknak pontosan a fele. Tehát $1/2$ valószínűsége van annak is, hogy az első helyen ülő tanulónak is fel kell állnia.

 

2. megoldás. Cseréljük meg az első és az utolsó tanuló jegyét. Ezzel párosítjuk a permutációkat. Ha az egyik permutációban az első és utolsó tanuló egy ciklusban volt, akkor a csere után külön ciklusba kerülnek és fordítva ‐ erről a nyilak berajzolásával könnyen meggyőződhetünk. Vagyis minden párból pontosan az egyikben kell felállnia az első tanulónak is. A keresett valószínűség tehát $1/2$.
A második megoldás talán a legegyszerűbb. Az itt használt gondolatnak fontos szerepe van a permutációk elméletében, lásd például a már említett, a ciklusokról szóló feladatsort. A véletlen permutációkhoz azonban érdemes még egy megoldást megismernünk. Ehhez az egész permutációt fel kell írnunk ciklus-szerkezettel. Szükségünk van a következő ötletre (én Lovász László könyvében olvastam először):

 

4. feladat. Láttuk, hogy a permutációk ciklikus felírása nem egyértelmű. Egy permutáció sokféleképp is felírható. Az egyes ciklusokon belül is bármelyik elemtől elindulhatunk, de a ciklusokat is tetszőleges sorrendben írhatjuk egymás után. Most szeretnénk egyértelműsíteni a ciklikus felírást ‐ éspedig úgy, hogy el is hagyhatjuk a zárójeleket. Lehetséges ez?

 

Megoldás. Feltesszük, hogy az első $n$ pozitív szám permutációjáról van szó. A ,,csel'' a következő. Először a ciklusokat rakjuk sorba, mégpedig úgy, hogy a bennük szereplő legkisebb számok növekvő sorrendet adjanak. Az első ciklus tehát az lesz, amelyben szerepel az 1, a második az lesz, amelyikben az első ciklusban nem szereplő számok közül a legkisebb áll stb. A fenti (a 2. feladat megoldása utáni) példánkban ez így volt: (1 4 6 7) (2 3 8 5 10) (9 11) (12). Most még a ciklus sorrendjét kell úgy felírni, hogy egyben kódoljuk azt is, hol van a vége. A megoldás a következő: minden ciklusban a legkisebb elemet írjuk utoljára. Így az első ciklus végét az 1 szám jelöli, a második ciklus végét az 1 előtt nem szereplő legkisebb szám megjelenése jelöli stb. A fenti példánk tehát így alakul: 4 6 7 1 3 8 5 10 2 11 9 12. Megjegyezzük, hogy ha a legnagyobb szám áll a legutolsó helyen, akkor az biztosan egyelemű ciklust alkot. Világos, hogy így az első $n$szám minden permutációját újra kódoltuk, egy-egyértelműen ‐ egy-egy $n$ hosszú permutációval.
A megoldásban szereplő felírási módot a következőkben ,,házi használatra'' a permutáció újrakódolásának fogjuk nevezni.

 

5. feladat*.${}^2$ (Gyakorló feladat.)² Melyik permutációkon nem változtat a fenti újrakódolás?

 

Az újrakódolás segítségével már könnyen megadhatjuk az ígért

 

1. megoldást a 3. feladathoz. A feladat azt kérdezi, hogy mennyi a valószínűsége annak, hogy az 1 és az $n$ egy ciklusban szerepel. Ez pontosan akkor következik be, ha az újrakódolás során az $n$ az 1-es előtt áll. Ez pedig nyilván az esetek felében teljesül, hiszen a kódokat párosíthatjuk úgy, hogy felcseréljük 1 és $n$ helyét.
Végül egy megjegyzés a 3. feladathoz: Egyik megoldásban sem játszik szerepet, hogy épp az utolsó helyen ülő áll fel és épp az első helyen ülőről szól a kérdés. Bárhogy jelölünk ki két tanulót, mindig $1/2$ annak a valószínűsége, hogy ők egy ciklusban lesznek (tehát ha az egyik feláll, akkor a másiknak is fel kell állnia). Mi a valószínűsége annak, hogy a 3. feladatban mindenkinek fel kell állnia?

 

6. feladat. $a)$ Mi a valószínűsége annak, hogy a $3$. feladatban mindenkinek fel kell állnia?
$b)$ Mi a valószínűsége annak, hogy pontosan $k$ embernek kell felállnia?

 

1. megoldás. $a)$ Ha mindenkinek fel kell állnia, az azt jelenti, hogy az egész permutáció egyetlen ciklus, tehát mind az $n$ tanulót megmozgatja. Az elsőnek felálló tanuló jegye most $n-1$ másik helyre szólhat, a következőé a maradó $n-2$ helyre stb., ez összesen $\left(n-1\right)!$ lehetőség, a permutációk $1/n$-ed része. Ez a keresett valószínűség. (A megoldás egy mondatban: $n$ elem ciklikus permutációinak száma $\left(n-1\right)!$, vagyis a permutációk $n$-ed része.) Ugyanígy kiszámolható az is, hogy $1/n$ a valószínűsége annak, hogy pontosan $k$ tanulónak kell felállnia, azaz, hogy az adott tanuló egy $k$ elemű ciklusban van benne. A számolást az olvasóra bízzuk, helyette egy másik megoldást mutatunk.

 

2. megoldás. A 3. feladat 3. megoldásánál alkalmazott újrakódolás is egyszerű választ tesz lehetővé mindkét kérdésre, és megvan az az előnye, hogy számolni sem kell.
$a)$ Pontosan akkor kell mindenkinek felállnia, ha a permutáció újrakódolásában az 1-es áll az utolsó helyen. Minthogy az újrakódolás után az $1$-es bármelyik helyen ugyanolyan valószínűséggel áll (hiszen minden permutáció pontosan egyszer szerepel az újrakódolásnál is), ezért $1/n$ valószínűséggel áll az utolsó helyen. Így ennyi a valószínűsége annak is, hogy mindenkinek fel kell állnia.
$b)$ Az 1-es a $k$-adik helyen is ugyanezzel a valószínűséggel áll, így csak annyit kell meggondolnunk, hogy ugyanaz marad a válasz, ha nem az utolsó helyen ülő tanuló áll fel először, hanem az első helyen ülő.
Ebben az esetben viszont már az a kérdés, hogy milyen valószínűséggel szerepel az 1 egy pontosan $k$ elemű ciklusban. Amire a válasz az, hogy ahányszor pontosan a $k$-adik helyen áll az újrakódolásban. És ez minden $k$-ra egyforma, tehát $1/n$.
A megoldásban kapott eredmény permutációkra átfogalmazva így szól:

 

Tétel. Legyen $n$ és $k$ tetszőleges pozitív egész szám, $k\le n$. Tekintsük $n$ elem egy véletlen permutációját. Annak a valószínűsége, hogy ebben egy adott elem pontosan $k$ hosszú ciklusban szerepel, $k$ értékétől függetlenül $1/n$.

 

${\displaystyle \begin{array}{c}\hfill {\displaystyle \text{<span style="font-weight: bold;">Surányi László</span>}}\hfill \end{array}}$

²A *-gal jelölt feladatok megoldása a cikk következő részével megjelenő függelékben található.