Niech \(\displaystyle{ P(n)}\) będzie zbiorem uporządkowanych podziałów liczby \(\displaystyle{ n}\), czyli ciągów \(\displaystyle{ a = <a_{1}, a_{2}, ...>}\) dodatnich liczb całkowitych takich, że \(\displaystyle{ a_{1} + a_{2} + ... = n}\), i niech \(\displaystyle{ f(a) = a_{1} * a_{2} * ...}\) będzie iloczynem składników takiego podziału.
Udowodnij, że \(\displaystyle{ \sum_{a \in P(n)}^{} f(a) = F_{2n}}\) , gdzie \(\displaystyle{ F_{n}}\) oznacza n-tą liczbę Fibonacciego.
WSKAZÓWKA: Niech \(\displaystyle{ a'}\) oznacza podział powstający z \(\displaystyle{ a}\) przez zastąpienie ostatniego składnika jedynką. Rozważ \(\displaystyle{ \sum_{a \in P(n)}^{} f(a')}\).
Jakieś pomysły?
Podział liczby
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Podział liczby
To zadanie nr 2 z egzaminu z MD dla informatyki na MIMUW w 2016 r.,
rozwiązanie tutaj:
rozwiązanie tutaj:
Kod: Zaznacz cały
http://wakacjezmd.github.io/2016/egzamin/1/