262080418

MATEMATYKA DYSKRETNA 2010 4. Wykład 4 - 24.III.2010

4.1.    Metody zliczania c.dc.d.

4.1.1.    Liczby Stirlinga pierwszego rodzaju. Przypomnieliśmy co to jest permutacja, jak zapisujemy permutacje w przypadku zbioru skończonego (wyglądało na to, że nie wszyscy wiedzieli!), co to jest cykl permutacji (permutacja cykliczna) i jak rozkładamy permutację na iloczyn (złożenie) cykli.

c(n, k) - liczba permutacji zbioru n-elementowego, które mają k cykli.

Twierdzenie 10. Niech k,n € N, 0 < k < n.

(1)    c(n, k) = c(n — 1, k — 1) + (n — l)c(n — 1 ,k).

(2)    c(n, n) = 1

(3)    c(n, 0) = c(0, k) = 0.

Dow. ...

Oznaczmy

[x]_n = x(x — 1) •... • (x — n -f 2)(x — n + 1)

[x]_n = ^s(ⁿ> k)x^k k=0

Współczynniki s(n, k) nazwyamy liczbami Stirlinga I-go rodzaju.

Twierdzenie 11. Niech fc,nGN,0<Kn. Wówczas

(1)    s(n,k) = s(n — 1, k— 1) — (n — l)s(n — 1 ,k).

(2)    s(n,n) = 1.

(3)    s(n, 0) = s(0, k) = 0

Dow. ...

Twierdzenie 12. Niech n, k G N, k < n.

c(n,k) = (—l)^n+fcs(n, k)

Dow. ...

4.1.2. Liczba permutacji danego typu.

Definicja 1. Permutację a e S_n nazywamy typu l^¹2^² .. .n^Xn jeżeli ma cykli długości i (w rozkładzie kanonicznym na cykle rozłączne), dla i = 1,... ,n.

Uwaga. Oczywiście, jeśli permutacja o jest typu l^Al2^A2... n^Xn, wówczas zachodzi:

lAi 2A2 H“ • • • -j- n\_n = n

Twierdzenie 13 (Cauchy’ego). Jeśli lAi + 2A2 -I- • • • + nX_n = n, wówczas liczba permutacji typu    ... n^Xn jest równa

n\

h(X_u .... A„) = JA,2^    A, !A₂!.. .A„!

Dow. ...