Zbiór zadań, (zadania różne)
Zadanie 330
Na ile sposobów można przedstawić liczbę $30$ jako uporządkowaną sumę liczb całkowitych, gdzie składniki muszą być większe lub równe od $2$?
Rozwiązanie
Niech $a_n$ oznacza liczbę sposobów przedstawienia liczby $n$ spełniających warunki zadania.
Zauważmy, że $a_{n+2}=a_n+a_{n-1}+\ldots + a_2 + 1$
$a_2 = 1$, $(2)$
$a_3 = 1$, $(3)$
$a_4 = a_2+1 = 2$, $(2+2, 4)$
$a_5 = a_3+a_2+1 = 3$, $(2+3, 3+2, 5)$
$a_6 = a_4+a_3+a_2+1 = 5$, $(2+2+2, 2+4, 3+3, 4+2, 6)$
$a_7 = a_5+a_4+a_3+a_2+1 = 8$, $(2+2+3, 2+3+2, 3+2+2, 2+5, 3+4, 4+3, 5+2, 7)$
...
Ciąg $a_n = F_{n-2}$, jest ciągiem Fibonacciego, gdzie $F_0=F_1=1$
$a_{n+2} = a_n+a_{n-1} + \ldots + a_2 + 1 = F_{n-2}+F_{n-3}+\ldots+F_1+F_0+1 = F_n-F_{n-1}+F_{n-1}-F_{n-2} + \ldots+F_2-F_1+1=F_n-F_1+1 = F_n$
Dla $n=30$, $a_{30}=F_{28}=514229$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>