2020 Kolokwium 1
Zadanie 1
Niech \(p_{n,k}\) oznacza liczbę \(n\)-permutacji mających dokładnie \(k\)
punktów stałych i niech \(r\) będzie ustaloną liczbą naturalną. Uprość sumę:
\[
\sum_k \binom{k}{r} p_{n,k}
\]
Zadanie 2
Niech \(a_n\) oznacza liczbę sposobów pomalowania płotu składającego się z
\(n>0\) sztachet przy pomocy farb w trzech kolorach tak, żeby każdy maksymalny
jednokolorowy spójny fragment płotu składał się z nieparzystej liczby sztachet
(np. \(a_1 = 3 \), \(a_2 = 6\), \(a_3 = 15\)). Znajdź funkcję tworzącą i zwarty
wzór na \(a_n\).
Zadanie 3
Udowodnij, że liczba podziałów \(n\) na składniki dające resztę \(1\) lub \(5\) z dzielenia przez \(6\), jest równa liczbie podziałów \(n\) na różne składniki niepodzielne przez \(3\).
Rozwiązanie
Zdefiniujmy:
-
\(F(x)\) – funkcja tworząca podziału \(n\) na składniki dające resztę \(1\) lub \(-1\) modulo \(6\);
-
\(G(x)\) – funkcja tworząca podziału \(n\) na różne składniki dające resztę \(1\) lub \(-1\) modulo \(3\).
-
\(F(x) = \prod_{k=1}^{\infty} [k \equiv \pm 1 \bmod 6] (1 + x^k + x^{2k} + x^{3k} + \ldots) = \prod_{k=0}^{\infty} \frac{1}{(1 - x^{6k+1})(1 - x^{6k+5})}\)
-
\(G(x) = \prod_{k=1}^{\infty} [k \equiv \pm 1 \bmod 3] (1 + x^k) = \prod_{k=0}^{\infty} (1 + x^{3k+1})(1 + x^{3k+2})\)