Zadanie 1

Znajdź wzór na liczbę n-permutacji o danej sygnaturze.

Zadanie 2

Permutacja f jest inwolucją gdy $f\circ f = id$. Pokaż, że
(a) permutacja jest inwolucją w.t.w. gdy ma sygnaturę $1^{\alpha_1}2^{\alpha_2}$;
(b) każda permutacja jest złożeniem dwóch inwolucji.

Zadanie 3

Dane są liczby naturalne $n\ge k>0$. Jakie jest prawdopodobieństwo, że w losowej n-permutacji jedynka należy do cyklu o długości k?

Zadanie 4

Pokaż, że losowa n-permutacja z prawdopodobieństwem $H_{n-1}/n$ składa się dokładnie z dwóch cykli.

Zadanie 5

Mamy n skarbonek i n kluczy, przy czym każdy klucz pasuje do dokładnie jednej skarbonki. Wrzucamy losowo po jednym kluczu do każdej skarbonki, po czym rozbijamy k skarbonek, $1\leq k\leq n$. Oblicz prawdopodobieństwo tego, że dzięki temu będzie można otworzyć wszystkie pozostałe skarbonki.

Zadanie 6

Pokaż tożsamość
$$x^n = \sum_k \left\{{n}\atop{k}\right\}\, x^{\underline{k}}$$
przez interpretację kombinatoryczna.

Zadanie 7

Pokaż następujące wzory:
$$\left\{{n}\atop{k}\right\} = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [1\le i_1\le i_2 \le \ldots \le i_{n-k}\le k]\ ,$$
$$\left[{n}\atop{k}\right] = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [0< i_1 < i_2 < \ldots < i_{n-k} < n]$$