Problem polega na rozłożeniu liczby na sumę jej składników, przy czym każdy jest większy od kolejnego, a następnie zliczenie liczby takich kombinacji. Przykładowo,mamy liczbę "12"
Jej rozkład będzie więc taki:
12 czyli zawsze jeden jednoczłonowy,
11+1, 10+2, ... , 7+5 (6+6 nie może być, bo 6<6, 5+7 też nie, bo 5<7 itd.)
1+2+9, 2+3+7, 3+4+5,
1+2+3+6
w sumie... 9
Wypisałem sobie tak dla kolejnych 15 liczb, ale (poza dwuczłonowymi) nie znalazłem żadnej zależności.
Wpadłem też na pomysł, żeby policzyć wszystkie takie możliwości rozkładu liczby na sumy innych, a następnie odrzucenie ciągów nierosnących. Potem wystarczałoby jedynie ich zliczenie. Niestety zadanie mnie przerosło, więc bardzo proszę o pomoc.
1 =1
1
2 =2
1
3 =3, 1+2
2
4 =4, 1+3
2
5 =5, 1+4,2+3
3
6 =6, 1+5,2+4, 1+2+3
4
7 =7, 1+6,2+5,3+4, 1+2+4
5
8 =8, 1+7,2+6,3+5, 1+2+5,
5
9 =9, 1+8,2+7,3+6,4+5, 1+2+6,2+3+4
7
10=10, 9+1,8+2,7+3,6+4, 1+2+7,2+3+5, 1+2+3+4 8
11=11, 10+1,9+2,8+3,7+4,6+5 1+2+8,2+3+6, 1+2+3+5 9
12=12, 11+1,10+2,9+3,8+4,7+5 1+2+9,2+3+7,3+4+5 1+2+3+6 10
13=13, 12+1,11+2,10+3,9+4,8+5,7+6 1+2+10,2+3+8,3+4+6 1+2+3+7 11
14=14, 13+1,12+2,11+3,10+4,9+5,8+6 1+2+11,2+3+9,3+4+7 1+2+3+8,2+3+4+5 12
15=15, 14+1,13+2,12+3,11+4,10+5,9+6,8+7 1+2+12,2+3+10,3+4+8,4+5+6 1+2+3+9,2+3+4+6 1+2+3+4+5
15
Rozkład liczby na sumy czynników liczb.
-
abc666
Rozkład liczby na sumy czynników liczb.
Pogubiłeś trochę rozkładów
12 ma 15 rozkładów
Po takim rozpisaniu widać już zależność. Niech \(\displaystyle{ r(k,m)}\) oznacza liczbę rozkładów liczby \(\displaystyle{ k}\), które spełniają warunki zadania, oraz w których największa liczba jest mniejsza niż \(\displaystyle{ m}\). Wtedy można zapisać zależność rekurencyjną. Niech \(\displaystyle{ s(n)}\) oznacza liczbę rozkładów liczby \(\displaystyle{ n}\), czyli to czego szukamy. Wtedy
\(\displaystyle{ s(n)=\sum_{i=0}^{n}r(i,n-i)}\)
tzn. np.
\(\displaystyle{ s(7)=r(0,7)+r(1,6)+r(2,5)+r(3,4)+r(4,3)+r(5,2)+r(6,1)+r(7,0)}\)
\(\displaystyle{ s(7)=\underbrace{r(0,7)}_{7}+\underbrace{r(1,6)}_{6+1}+\underbrace{r(2,5)}_{5+2}+\underbrace{r(3,4)}_{4+3,\ 4+2+1}}\)
Reszta składników jest równa zero.
Teraz musimy znaleźć zależność na \(\displaystyle{ r(k,m)}\). Bo \(\displaystyle{ s(n)=r(n,n+1)}\). Zauważamy, że \(\displaystyle{ r(0,m)=1, r(k,m)=0\text{ dla }k<0, r(k,m)=0\text{ dla }m\le 1}\) oraz, że \(\displaystyle{ r(k,m)=r(k,m-1)+r(k-m+1,m-1)}\)
Jak można zobaczyć na rozwiązanie raczej i tak nie ma znanej postaci zwartej.
Ukryta treść:
Ukryta treść:
\(\displaystyle{ s(n)=\sum_{i=0}^{n}r(i,n-i)}\)
tzn. np.
\(\displaystyle{ s(7)=r(0,7)+r(1,6)+r(2,5)+r(3,4)+r(4,3)+r(5,2)+r(6,1)+r(7,0)}\)
\(\displaystyle{ s(7)=\underbrace{r(0,7)}_{7}+\underbrace{r(1,6)}_{6+1}+\underbrace{r(2,5)}_{5+2}+\underbrace{r(3,4)}_{4+3,\ 4+2+1}}\)
Reszta składników jest równa zero.
Teraz musimy znaleźć zależność na \(\displaystyle{ r(k,m)}\). Bo \(\displaystyle{ s(n)=r(n,n+1)}\). Zauważamy, że \(\displaystyle{ r(0,m)=1, r(k,m)=0\text{ dla }k<0, r(k,m)=0\text{ dla }m\le 1}\) oraz, że \(\displaystyle{ r(k,m)=r(k,m-1)+r(k-m+1,m-1)}\)
Jak można zobaczyć na
Kod: Zaznacz cały
https://oeis.org/A000009