Cím:	Hány olyan permutáció van, amely adott számú elemet rögzít?
Szerző(k):	Ádám András
Füzet:	2002/május, 265 - 268. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 1. Bevezetés   Amikor két és fél éves Péter unokámmal töltöttem az időt, gyakran támadt kedve azzal szórakozni, hogy cseréljük össze a lakás falaira akasztott három vagy négy órát. Ez a cserebere-játék természetesen akkor igazán érdekes, ha az órák egyike sem marad a megszokott helyén.   Mint tudjuk, egy $n$ elemű halmaz elemeit $n!=n\left(n-1\right)\left(n-2\right)\text{...}3\cdot 2$-féleképpen lehet sorba állítani (permutálni). A kérdés tehát az, hogyan oszlik meg az $n!$ permutáció aszerint, hogy mennyi ‐ egy rögzített ,,eredeti'' sorrendhez képest ‐ a helyben maradó elemek száma; jelöljük ezért $\psi \left(n\mathrm{,}k\right)$-val egy $n$ elemű halmaz azon permutációinak a számát, amelyeknél az eredeti helyükön álló elemek száma pontosan $k$.${}^{*}$ Ekkor nyilván $\begin{array}{c}{\displaystyle \sum _{k=0}^n\psi \left(n\mathrm{,}k\right)=n!\mathrm{.}}\end{array}$ (1) A későbbi eredményeket némileg megelőlegezve tekintsük át a $\psi \left(n\mathrm{,}k\right)$ értékeit $n\le 8$-ra: ${\displaystyle \begin{array}{|ccccccccccc|}\hline \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{<span style="font-weight: bold;">k</span>}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \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{<span style="font-weight: bold;">n</span>}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 2}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 1}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 3}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 2}}\hfill & \hfill {\displaystyle \text{3}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 4}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 9}}\hfill & \hfill {\displaystyle \text{8}}\hfill & \hfill {\displaystyle \text{6}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 5}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 44}}\hfill & \hfill {\displaystyle \text{45}}\hfill & \hfill {\displaystyle \text{20}}\hfill & \hfill {\displaystyle \text{10}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 6}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 265}}\hfill & \hfill {\displaystyle \text{264}}\hfill & \hfill {\displaystyle \text{135}}\hfill & \hfill {\displaystyle \text{40}}\hfill & \hfill {\displaystyle \text{15}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 7}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 1854}}\hfill & \hfill {\displaystyle \text{1855}}\hfill & \hfill {\displaystyle \text{924}}\hfill & \hfill {\displaystyle \text{315}}\hfill & \hfill {\displaystyle \text{70}}\hfill & \hfill {\displaystyle \text{21}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill & \hfill {\displaystyle }\hfill \\ \hfill {\displaystyle \text{ 8}}\hfill & \hfill {\displaystyle }\hfill & \hfill {\displaystyle \text{ 14833}}\hfill & \hfill {\displaystyle \text{14832}}\hfill & \hfill {\displaystyle \text{7420}}\hfill & \hfill {\displaystyle \text{2464}}\hfill & \hfill {\displaystyle \text{630}}\hfill & \hfill {\displaystyle \text{112}}\hfill & \hfill {\displaystyle \text{28}}\hfill & \hfill {\displaystyle \text{0}}\hfill & \hfill {\displaystyle \text{1}}\hfill \\ \hline\end{array}}$ Világos, hogy $\psi \left(n\mathrm{,}n\right)=1$ és $\psi \left(n\mathrm{,}n-1\right)=0$ (minden $n$-re). Az is látható, hogy a táblázat első $n-1$ sorának ismeretében az $n$-edik sor elemei a legelső kivételével könnyen meghatározhatók: ha ugyanis $1\le k\le n-1$, akkor $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$-féleképpen választható ki a helyén maradó $k$ elem, és minden ilyen választás esetén $\psi \left(n-k\mathrm{,0}\right)$ olyan permutáció van, amelynél a fennmaradó $n-k$ elem egyike sincs az eredeti helyén. Így $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,}k\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)\psi \left(n-k\mathrm{,0}\right)\mathrm{,}\text{ha}1\le k\le n-1.}\end{array}$ (2) Hátra van még a $\psi \left(n\mathrm{,0}\right)$ értékének kiszámítása. Ez megtehető például az (1) összefüggés felhasználásával: $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,0}\right)=n!-\sum _{k=1}^n\psi \left(n\mathrm{,}k\right)=n!-1-\sum _{k=1}^{n-2}\psi \left(n\mathrm{,}k\right)\mathrm{.}}\end{array}$ (3) A (2) és (3) formulák ismételt alkalmazásával (a nyilvánvaló $\psi \left(\mathrm{1,0}\right)=0$, $\psi \left(\mathrm{1,1}\right)=1$-ből kiindulva) minden $\psi \left(n\mathrm{,}k\right)$ kiszámítható. Mégsem lehetünk maradéktalanul elégedettek: a $\psi \left(n\mathrm{,0}\right)$ értékeknek ezen a ,,kerülő úton'' történő meghatározása meglehetősen átláthatatlanná teszi a folyamatot, és nem ad választ például arra a természetes módon felvetődő kérdésre, hogy a táblázatban megfigyelhető $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,1}\right)=\psi \left(n\mathrm{,0}\right)\pm 1}\end{array}$ összefüggés vajon minden $n$-re teljesül-e. A felmerült kételyekre választ kaphatunk, ha $\psi$ értékeit egy másfajta összefüggés segítségével határozzuk meg.   2. A $\psi \left(n\mathrm{,}k\right)$ kiszámítása szitálással   A szitaformula. Legyen $H$ véges halmaz, $G_1$, $G_2$, $\text{...}$ , $G_n$ pedig részhalmazok $H$-ban. Tetszőleges $X_i$ halmazok elemszámát $|X_i|$-vel, metszetüket $X_i\cap X_j\cap \text{...}\cap X_t$-vel, egyesítésüket $X_i\cup X_j\cup \text{...}\cup X_t$-vel, két halmaz különbségét pedig $X_i\setminus X_j$-vel jelöljük. A felsorolt $G_i$ részhalmazokra legyen $N_{\left\{i\mathrm{,}j\mathrm{,}\text{...}\mathrm{,}t\right\}}=|G_i\cap G_j\cap \text{...}\cap G_t|$. A szitaformula szerint ekkor $\begin{array}{c}{\displaystyle |H\setminus \left(G_1\cup G_2\cup \text{...}\cup G_n\right)|=\sum _{L\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}}^{}{\left(-1\right)}^{|L|}{N}_L\mathrm{.}}\end{array}$ (4) A jelölések és halmazok metszetének értelmezése szerint az üres halmazt $\varnothing$-val jelölve $N_{\varnothing }=|H|$, hiszen ilyenkor a metszetbe tartozás semmilyen követelményt nem jelent, így annak a $H$ minden eleme eleget tesz. A (4) formula igazolásához először is jegyezzük meg, hogy a bal oldalon a $H$ azon elemeinek a száma áll, amelyek egyik $G_i$ részhalmazban sincsenek benne. A formula jobb oldala pedig a $G_i\cap G_j\cap \text{...}\cap G_t$ metszetek elemszámának a ${\left(-1\right)}^{|\left\{i\mathrm{,}j\mathrm{,}\text{...}\mathrm{,}t\right\}|}$-vel súlyozott összege, ahol $\left\{i\mathrm{,}j\mathrm{,}\text{...}\mathrm{,}t\right\}\subseteq \left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$. Legyen $x$ a $H$ egy tetszőleges eleme. Ha $x$ a $G_i$ részhalmazok egyikének sem eleme, akkor ő a bal oldalon található halmaz elemszámához 1-gyel járul hozzá; ha pedig benne van legalább egy $G_j$-ben, akkor a különbséghalmaz elemszámához 0-val járul hozzá. Vizsgáljuk meg ugyanezt a jobb oldalon szereplő metszethalmazok szempontjából is. Amennyiben $x$ egyik $G_i$-nek sem eleme, akkor a metszetek közül egyedül az ,,üresben'' van benne, ezért a ‐ súlyozott ‐ hozzájárulása ${\left(-1\right)}^0\cdot 1=1$. Tekintsük ezután azt az esetet, amikor $x$ eleme a $G_{i_1}\mathrm{,}{G}_{i_2}\mathrm{,}\text{...}\mathrm{,}{G}_{i_k}$ halmazoknak, a többinek pedig nem ($n\ge k\ge 1$). Ekkor $x$ pontosan azokban a metszetekben van benne, amelyek $G_s\cap G_t\text{...}\cap G_b$ alakúak, ahol $S=\left\{s\mathrm{,}t\mathrm{,}\text{...}\mathrm{,}b\right\}\subseteq \left\{i_1\mathrm{,}{i}_2\mathrm{,}\text{...}\mathrm{,}{i}_k\right\}$. Így az $x$ ,,súlyozott'' járuléka (4) jobb oldalához: $\begin{array}{c}{\displaystyle \sum _{S:S\subseteq \left\{i_1\mathrm{,}{i}_2\mathrm{,}\text{...}\mathrm{,}{i}_k\right\}}^{}{\left(-1\right)}^{|S|}=\sum _{\ell =0}^k{\left(-1\right)}^{\ell }\left(\genfrac{}{}{0ex}{}{k}{\ell }\right)={\left(1-1\right)}^k=0.}\end{array}$ (Az utolsó előtti lépésben a binomiális tételt alkalmaztuk ${\left(1-1\right)}^k$ kiszámítására). Ezzel a (4)-et be is láttuk.   Egy újabb előállítás $\psi$-re. Alkalmazzuk a szitaformulát a $\psi \left(n\mathrm{,}k\right)$ értékek meghatározására. Ennek érdekében jelölje $H$ az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számok összes permutációinak a halmazát; tekintsük e számok növekvő sorrendjét az eredeti sorrendjüknek. Legyen továbbá $G_k$ azoknak a permutációknak a halmaza, amelyeknél a $k$ az eredeti helyén szerepel ($1\le k\le n$). Ekkor $\psi \left(n\mathrm{,0}\right)$ éppen a $H\setminus \left(G_1\cup G_2\cup \text{...}\cup G_n\right)$ elemeinek a száma. Hány eleme van egy $G_{v_1}\cap G_{v_2}\cap \text{...}\cap G_{v_t}$ metszetnek? Ez éppen azoknak a permutációknak a száma, amelyeknél $v_1\mathrm{,}{v}_2\mathrm{,}\text{...}\mathrm{,}{v}_t$ az eredeti helyén áll, ezért a fennmaradó $n-t$ elem permutációit kell csak megszámlálnunk, az eredmény természetesen $\left(n-t\right)!$. Ezért, a szitaformula alapján $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,0}\right)=\sum _{t=0}^n\sum _{\left\{v_1\mathrm{,}\text{...}\mathrm{,}{v}_t\right\}}^{}{\left(-1\right)}^t\left(n-t\right)!=\sum _{t=0}^n{\left(-1\right)}^t\left(\genfrac{}{}{0ex}{}{n}{t}\right)\left(n-t\right)!=n!\sum _{t=0}^n{\left(-1\right)}^t\frac{1}{t!}\mathrm{.}}\end{array}$ A kapott eredményt $n$ helyett $\left(n-k\right)$-ra felírva, (2) szerint a kívánt előállítás: $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,}k\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(n-k\right)!\sum _{t=0}^{n-k}{\left(-1\right)}^t\frac{1}{t!}=\frac{n!}{k!}\sum _{t=0}^{n-k}{\left(-1\right)}^t\frac{1}{t!}\mathrm{.}}\end{array}$ (5) Az (5) formulának több érdekes következménye is van. Vizsgáljuk először $\psi \left(n\mathrm{,0}\right)$ és $\psi \left(n-\mathrm{1,0}\right)$ kapcsolatát: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle \psi \left(n\mathrm{,0}\right)-n\psi \left(n-\mathrm{1,0}\right)}& {\displaystyle =n!\sum _{t=0}^n{\left(-1\right)}^t\frac{1}{t!}-n\left(n-1\right)!\sum _{t=0}^{n-1}{\left(-1\right)}^t\frac{1}{t!}=}\hfill \\ \hfill {\displaystyle }\\ \hfill {\displaystyle }& {\displaystyle =n!\frac{{\left(-1\right)}^n}{n!}={\left(-1\right)}^n\mathrm{,}}\hfill \end{array}}}\end{array}$ azaz a következő egyszerű rekurzió adódik $\psi \left(n\mathrm{,0}\right)$ értékeire: $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,0}\right)=n\cdot \psi \left(n-\mathrm{1,0}\right)+{\left(-1\right)}^n\mathrm{.}}\end{array}$ (6) Vessük ezt össze a (2) speciális eseteként adódó $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,1}\right)=n\psi \left(n-\mathrm{1,0}\right)}\end{array}$ (7) egyenlőséggel: $\begin{array}{c}{\displaystyle \psi \left(n\mathrm{,0}\right)=n\psi \left(n-\mathrm{1,0}\right)+{\left(-1\right)}^n=\psi \left(n\mathrm{,1}\right)+{\left(-1\right)}^n\mathrm{,}}\end{array}$ (8) tehát a táblázatból korábban megsejtett összefüggés valóban általános érvényű.   Befejezésül vizsgáljuk meg a $\begin{array}{c}{\displaystyle \sigma \left(n\right)=\psi \left(n\mathrm{,0}\right)+\psi \left(n\mathrm{,1}\right)+\psi \left(n\mathrm{,}n\right)}\end{array}$ viselkedését; ez azoknak a permutációknak a száma (és ezek teszik ki a túlnyomó többséget!), amelyeknél legfeljebb egy elem áll az eredeti helyén, vagy mindegyik. Megmutatjuk, hogy $\begin{array}{c}{\displaystyle \sigma \left(n\right)=\{{\displaystyle \begin{array}{cc}{\displaystyle n\cdot \sigma \left(n-1\right)\mathrm{,}}\hfill & {\displaystyle \text{ ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math> páratlan;}}\hfill \\ {\displaystyle }\hfill \\ {\displaystyle n\cdot \sigma \left(n-1\right)-2\left(n-1\right)=\left(n-\frac{2}{\sigma \left(n-2\right)}\right)\sigma \left(n-1\right)\mathrm{,}}\hfill & {\displaystyle \text{ ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math> páros.}}\hfill \end{array}}}\end{array}$ (9) Tegyük föl először, hogy $n$ páratlan. Ekkor (8) és (7) alapján $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle \frac{\sigma \left(n\right)}{\sigma \left(n-1\right)}}& {\displaystyle =\frac{\psi \left(n\mathrm{,0}\right)+\psi \left(n\mathrm{,1}\right)+1}{\psi \left(n-\mathrm{1,0}\right)+\psi \left(n-\mathrm{1,1}\right)+1}=\frac{\psi \left(n\mathrm{,1}\right)-1+\psi \left(n\mathrm{,1}\right)+1}{\psi \left(n-\mathrm{1,0}\right)+\psi \left(n-\mathrm{1,0}\right)-1+1}=}\hfill \\ \hfill {\displaystyle }\\ \hfill {\displaystyle }& {\displaystyle =\frac{\psi \left(n\mathrm{,1}\right)}{\psi \left(n-\mathrm{1,0}\right)}=n\mathrm{.}}\hfill \end{array}}}\end{array}$ Ha pedig $n$ páros, akkor (6) és (7) szerint $\begin{array}{c}{\displaystyle \sigma \left(n\right)=\psi \left(n\mathrm{,0}\right)+\psi \left(n\mathrm{,1}\right)+1=n\psi \left(n-\mathrm{1,0}\right)+1+n\psi \left(n-\mathrm{1,0}\right)+\mathrm{1,}}\end{array}$ ami viszont (8) alapján $\begin{array}{c}{\displaystyle n\left(\psi \left(n-\mathrm{1,1}\right)-1\right)+1+n\psi \left(n-\mathrm{1,0}\right)+1=n\sigma \left(n-1\right)-2\left(n-1\right)\mathrm{.}}\end{array}$ Mivel most $n-1$ páratlan, azért, mint már beláttuk, $\begin{array}{c}{\displaystyle \frac{\sigma \left(n-1\right)}{\sigma \left(n-2\right)}=n-1.}\end{array}$ ${}^{*}$Az $n=6$, $k=2$ esetet illusztrálja a belső borító.