Szukam rozwiązania do zadania:
Niech \(\displaystyle{ a_{n}(k)}\) oznacza liczbę \(\displaystyle{ n}\)-permutacji z powtórzeniami ze zbioru \(\displaystyle{ {1,...,k}}\), w których \(\displaystyle{ k}\) występuje nieparzystą liczbę razy. Znajdź zwarty wzór na \(\displaystyle{ a_{n}(k)}\) dla \(\displaystyle{ k>1}\).
Zauważyłem, że można opisać warunki zadania układem równań rekurencyjnych (przez rozłączne przypadki obecności lub nieobecności \(\displaystyle{ k}\) na ostatnim miejscu permutacji):
\(\displaystyle{ a_{n}(k) = b_{n-1}(k) + (k-1)a_{n-1}(k) \newline
b_{n}(k) = a_{n-1}(k) + (k-1)b_{n-1}(k)\newline
a_{1}(k) = 1\newline
b_{1}(k) = k-1}\)
Gdzie \(\displaystyle{ b_{n}(k)}\) to ciąg analogiczny do \(\displaystyle{ a_{n}(k)}\) z tą różnicą, że ilość wystąpień \(\displaystyle{ k}\) jest parzysta. Jednak nie potrafię dalej ruszyć z rozwiązaniem tego równania, ani nie wiem, czy moje rozumowanie jest dobre. Proszę o pomoc.
--EDIT--
Odpocząłem i od razu zobaczyłem rozwiązanie Z funkcji tworzących wychodzi, że \(\displaystyle{ a_{n}(k) = \frac{1}{2}(k^{n}-(k-2)^{n})}\), co potwierdza wolfram. Tylko czy ktoś mógłby potwierdzić poprawność mojego rozumowania?