5600235762

8 Współczynniki dwumianowe 19

Ostatecznie 7r = (0,2,6,5,1,3) (4) (7,8).

Twierdzenie 7.4. Rozkład permutacji na cykle jest jednoznaczny z dokładnością do kolejności.

Typ permutacji 7T € S_n to wektor (ci, C2,..., c^), gdzie c* jest liczbą cykli długości i w rozkładzie n. Zazwyczaj typ permutacji zapisujemy jako

[l^Cl2^C2...n^Cn],

przy czym często pomijamy te wartości, dla których Cj = 0.

Permutacja z przykładu 7.3 ma jeden cykl długości 1, jeden cykl długości 2 oraz jeden cykl długości 6, a więc jej typ to [l¹^¹^¹].

7.2 Transpozycje

Transpozycja to permutacja zbioru n-elementowego X (dla n < 2) typu [l^n-22¹]. Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów ze zbioru X.

Przykład 7.5. Dla permutacji 7r € S7 takiej, że:

n	0	1	2	3	4	5	6
7r(n)	0	1	5	3	4	2	6

mamy 7r = (0)(1)(2,5)(3)(4)(6) = (2,5), a więc 7r ma typ [1⁵2¹], co oznacza, że 7r jest transpozycją.

Twierdzenie 7.6. Dowolny cykl z S_n jest złożeniem n — 1 transpozycji.

Ponieważ, na mocy 7.4 dowolna permutacja jest rozkładalna na cykle, zatem z powyższego twierdzenia wynika, że każda permutacja jest złożeniem transpozycji. W szczególności każda permutacja typu [l^Cl2^C2... n^Cn], ma rozkład na co najwyżej C2 + 2C3 + ■ • • + (n — 1)^ transpozycji.

Permutacja jest parzysta, gdy jest złożeniem parzystej liczby transpozycji, natomiast permutacja jest nieparzysta, gdy jest złożeniem nieparzystej liczby transpozycji. Znak permutacji 7r to

sign(ir) = (-l)^r,

gdzie r jest liczbą transpozycji, na które można rozłożyć 7r.

8 Współczynniki dwumianowe

Wiemy już, że zbiór n-elementowy X ma dokładnie 2ⁿ podzbiorów, tyle ile jest funkcji charakterystycznych podzbiorów. Teraz zajmiemy się pytaniem ile taki zbiór ma podzbiorów o dokładnie k elementach. Rodzinę wszystkich fc-elementowych podzbiorów zbioru X będziemy oznaczać przez Vi_c(X).

Współczynnik dwumianowy (£) to ilość fc-elementowych podzbiorów zbioru n-elementowego, czyli