Permutációk paritása, ciklusok és a szita-formula

Emlékeztető — szemléltetés és kétsoros jelölés

Az \(\{1, 2, \dots, n\}\) elemek ismétlés nélküli permutációinak halmazát \(S_n\)-nel jelöljük (\(|S_n| = n!\)). Egy \(\pi \in S_n\) permutáció megadható kétsoros alakban:

\[ \pi = \begin{pmatrix} 1 & 2 & \dots & n \\ i_1 & i_2 & \dots & i_n \end{pmatrix} \]

ahol az oszlopok sorrendje tetszőlegesen felcserélhető.

Definíció — inverzió és paritás

A \(\pi = (i_1, i_2, \dots, i_n) \in S_n\) permutációban az \((i_k, i_l)\) pár inverzióban áll, ha \(k < l\), de \(i_k > i_l\). Az inverziók számát \(I(\pi)\)-vel jelöljük. A \(\pi\) permutáció páros, ha \(I(\pi)\) páros, és páratlan, ha \(I(\pi)\) páratlan.

Tétel — elemcsere hatása a paritásra

Ha egy \(S_n\)-beli permutációban két elemet felcserélünk (transzpozíció), akkor a permutáció paritása megváltozik.

Bizonyítás

Tegyük fel, hogy az \(i_k\) és \(i_l\) elemeket cseréljük fel, melyek között \(s\) darab elem áll.

• Az \(i_k\) előtt és az \(i_l\) után álló elemekkel való inverziós viszonyok nem változnak.
• A köztes \(s\) darab elemmel való inverziós viszonyok kétszer váltanak (egyszer az \(i_k\)-val, egyszer az \(i_l\)-lel), így ezek hatása páros (\(2s\)).
• Az \(i_k\) és \(i_l\) egymáshoz képesti viszonya pontosan 1-gyel változik.

Az inverziók számának változása: \(2s + 1\), ami páratlan szám. Így a permutáció paritása megváltozik.

Tétel — páros és páratlan permutációk száma

Ha \(n \ge 2\), akkor az \(S_n\)-beli páros permutációk száma megegyezik a páratlan permutációk számával, azaz mindkettőből \(\frac{n!}{2}\) darab van.

Bizonyítás

Képezzünk egy \(f\) leképezést a páros permutációkból a páratlan permutációkba úgy, hogy minden páros permutáció első két elemét felcseréljük. Ez a leképezés bijektív, így a két halmaz elemszáma megegyezik.

Definíció — permutációk szorzása

Legyen \(\pi = (i_1, i_2, \dots, i_n) \in S_n\) és \(\rho = (j_1, j_2, \dots, j_n) \in S_n\).

A \(\pi\) és \(\rho\) permutációk szorzata a leképezések egymás utáni elvégzése (összetétele), ahol a műveletet balról jobbra hajtjuk végre:

\[ \pi \cdot \rho = (j_{i_1}, j_{i_2}, \dots, j_{i_n}) \in S_n \]

azaz ha \(\pi\) a \(k\)-t az \(i_k\)-ba viszi, és \(\rho\) az \(i_k\)-t a \(j_{i_k}\)-ba viszi, akkor \(\pi \cdot \rho\) a \(k\)-t a \(j_{i_k}\)-ba viszi.

Tétel — a szimmetrikus csoport tulajdonságai

Az \((S_n, \cdot)\) struktúra csoportot alkot, melyet \(n\)-edfokú szimmetrikus csoportnak nevezünk:

1. Asszociativitás: \(\forall \pi, \rho, \sigma \in S_n : (\pi \cdot \rho) \cdot \sigma = \pi \cdot (\rho \cdot \sigma)\).
2. Egységelem: létezik \(\varepsilon = (1, 2, \dots, n) \in S_n\) identikus permutáció, melyre \(\forall \pi \in S_n : \pi \cdot \varepsilon = \varepsilon \cdot \pi = \pi\).
3. Inverz elem: \(\forall \pi \in S_n\)-hez létezik egyértelműen \(\pi^{-1} \in S_n\), melyre \(\pi \cdot \pi^{-1} = \pi^{-1} \cdot \pi = \varepsilon\).

Tétel — paritás szabályai szorzásra és inverzre

• Azonos paritású \(S_n\)-beli permutációk szorzata páros.
• Különböző paritású \(S_n\)-beli permutációk szorzata páratlan.
• Bármely \(\pi \in S_n\) esetén \(I(\pi^{-1}) = I(\pi)\), azaz \(\pi\) és \(\pi^{-1}\) paritása megegyezik.

Emlékeztető — ciklikus eltolás fogalma

Egy \(l\) hosszúságú ciklus egy olyan speciális permutáció, amely az \((i_1, i_2, \dots, i_l)\) elemeket körkörösen eltolja (\(i_1 \to i_2 \to \dots \to i_l \to i_1\)), míg az összes többi elemet helyben hagyja.

Definíció — ciklus és idegen ciklusok

• Egy \(\pi \in S_n\) permutáció \(l\) hosszúságú ciklus, ha létezik \(l\) (\(2 \le l \le n\)) és \(i_1, \dots, i_l \in \{1, \dots, n\}\) úgy, hogy \(\pi(i_1)=i_2, \pi(i_2)=i_3, \dots, \pi(i_l)=i_1\), és a többi \(n-l\) elemet \(\pi\) fixen hagyja. Jelölése: \((i_1 \, i_2 \, \dots \, i_l)\).
• Két \(S_n\)-beli ciklust idegen ciklusoknak nevezünk, ha nincs közös mozgatott elemük.

Tétel — ciklusok tulajdonságai

1. Ha \(\pi \in S_n\) egy \(l\) hosszú ciklus, akkor \(\pi^l = \varepsilon\).
2. Ha \(\pi, \rho \in S_n\) idegen ciklusok, akkor felcserélhetők: \(\pi \cdot \rho = \rho \cdot \pi\).
3. Ha \(\pi \in S_n\) egy \(l\) hosszú ciklus, akkor \(\pi\) és \(l\) különböző paritású (azaz páros \(l\) esetén a ciklus páratlan, páratlan \(l\) esetén a ciklus páros).
4. Egy \(l\) hosszú ciklus inverze is \(l\) hosszú ciklus: \((i_1 \, i_2 \, \dots \, i_{l-1} \, i_l)^{-1} = (i_l \, i_{l-1} \, \dots \, i_2 \, i_1)\).

Tétel — ciklusfelbontási tétel

Minden \(\pi \in S_n\) (\(\pi \neq \varepsilon\)) permutáció felírható páronként idegen ciklusok szorzataként, és ez a felírás a tényezők sorrendjétől eltekintve egyértelmű.

Tétel — szita-formula (tartalmazás és kizárás elve)

Legyen \(X \neq \emptyset\) véges halmaz és \(Y_1, \dots, Y_m \subseteq X\). Ekkor:

\[ \left| X \setminus \bigcup_{i=1}^{m} Y_i \right| = |X| + \sum_{\emptyset \neq J \subseteq \{1, \dots, m\}} (-1)^{|J|} \left| \bigcap_{j \in J} Y_j \right| \]

Részletesen kiírva:

\[ \left| X \setminus \bigcup_{i=1}^{m} Y_i \right| = |X| - \sum_{i=1}^m |Y_i| + \sum_{1 \le i < j \le m} |Y_i \cap Y_j| - \dots + (-1)^m |Y_1 \cap \dots \cap Y_m| \]

Bizonyítás

Azonosítsuk, hányszor számoljuk meg \(X\) egy tetszőleges \(y\) elemét a jobb oldalon:

• Ha \(y \notin \bigcup Y_i\), akkor a bal oldalon 1-szer számoljuk. A jobb oldalon csak \(|X|\)-ben szerepel (1-szer), a metszetekben nem. Így \(1 = 1\).
• Ha \(y \in \bigcup Y_i\), akkor \(y\) pontosan \(s\) darab \(Y_i\) halmaznak eleme (\(s \ge 1\)). A bal oldalon 0-szor számoljuk. A jobb oldalon a hozzájárulása: \[ 1 - \binom{s}{1} + \binom{s}{2} - \binom{s}{3} + \dots + (-1)^s \binom{s}{s} = (1-1)^s = 0 \]

Tehát az egyenlőség minden elemre teljesül.

Tétel — Euler-féle φ-függvény képlete

Legyen \(n \in \mathbb{N}, n > 1\) prímhatvány-felbontása \(n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}\). Ekkor az \(n\)-nél nem nagyobb, \(n\)-hez relatív prím pozitív egész számok száma:

\[ \varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right) \]

Tétel — szürjektív leképezések száma

Legyen \(k, n \in \mathbb{N}\), \(|A| = k\) és \(|B| = n\). Az \(A \to B\) szürjektív (ráképező) függvények száma:

\[ \sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^k \]

Tétel

Legyen \(n \in \mathbb{N}\). Az \(S_n\)-beli fixpontmentes permutációk (derangement-ek) száma:

\[ \sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)! \]

Bizonyítás

Legyen \(X = S_n\), és \(Y_i = \{ \pi \in S_n \mid i \text{ fixpontja } \pi\text{-nek} \}\) (\(i=1, \dots, n\)). Ekkor \(|X| = n!\).

\[ |Y_i| = (n-1)! \]

(mivel 1 elem fixpont, a többi \(n-1\) elem tetszőlegesen permutálandó). Általában \(j\) db \(Y_i\) halmaz metszetének elemszáma:

\[ = (n-j)! \]

(\(j\) db elem fixpont, a többi \(n-j\) elem permutálandó). A szita-formula szerint:

\[ \left| X \setminus \bigcup_{i=1}^{n} Y_i \right| = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \dots + (-1)^n \binom{n}{n}(n-n)! \]

ahol a bal oldal a fixpontmentes permutációk halmazának létszáma (azon permutációk száma, melyeknek nincs fixpontja).