2021 Egzamin poprawkowy
Zadanie 1
Permutację \(\langle \pi_1, \pi_2, \ldots, \pi_n \rangle\) zbioru \( \{1, \ldots, n\}\) nazywamy ciekawą, jeśli dla dokładnie jednego \(i \in \{1, \ldots, n\}\) zachodzi \(\pi_i > i\). Znajdź zwarty wzór na liczbę ciekawych \(n\)-permutacji.
Wskazówka: rozważ zbiór punktów stałych ciekawej permutacji.
Zadanie 2
Dla ustalonej liczby naturalnej \(n\) ciąg \(\langle a_i \rangle_{i=0}^{3n}\) jest określony zależnością: \[ \sum_{i=0}^{3n} a_i x^i = (1+x+x^2+x^3)^n \]
Uprość wyrażenie \(\sum_{i=0}^{k} (-1)^i a_{k-i} \binom{n}{i}\).
Zadanie 3
Ustalmy zbiory skończone \(S_1, \ldots, S_m\) i zdefiniujmy graf \(G = (V, E)\):
\( V = S_1 \times S_2 \times \ldots \times S_m \),
\( E = \{\{u,v\} \subseteq V \mid u\) i \(v\) różnią się na każdej współrzędnej\(\}\).
Wyznacz \(\chi(G)\).Zadanie 4
Znajdź (bez wspomagania komputerowego) najmniejsze \(n\) takie, że \(3^n - 2^n\)
jest wielokrotnością liczby \(175\).