2026 Kolokwium 1

Zadanie 1

Niech \(a_n\) oznacza liczbę \(n\)-permutacji \(a_1 a_2 \dots a_n\), które mają dwa lewostronne maksima lokalne, tzn. \(\left| \left\{ i \in \{1, 2, \dots, n-1\} \colon a_i < a_{i+1} \right\} \right| = 2 .\) Udowodnij, że \( a_n = 3^n - (n+1) 2^n + \binom{n+1}{2} \).

Zadanie 2

Dla \(n \ge 0\) niech \(d_n\) oznacza liczbę \(n\)-słów nad alfabetem \(\{A, B, C\}\), w których litery \(A\) i \(B\) nie sąsiadują ze sobą. Znajdź zwarty wzór na \(d_n\).

Zadanie 3

Dwukolorowym podziałem liczby \(n\) nazwiemy taki podział \(n\), którego każdy składnik jest czerwony albo niebieski, przy czym wszystkie składniki tego samego rozmiaru mają ten sam kolor (np. \(n = 3\) ma \(8\) dwukolorowych podziałów: \((1+1+1)N\), \((1+1+1)C\), \((2)C+(1)C\), \((2)C+(1)N\), \((2)N+1(C)\), \((2)N+(1)N\), \((3)C\), \((3)N\)).

Udowodnij, że liczba dwukolorowych podziałów \(n\) to \(\sum_{k=0}^{n} P_k Q_{n-k},\) gdzie \(P_n\) to liczba wszystkich podziałów \(n\), zaś \(Q_n\) to liczba podziałów \(n\) na składniki nieparzyste.