Podział liczby \( n \) na \( k \) składników to przedstawienie \( n \) w postaci sumy
\( a_0+\ldots+a_{k-1}=n, \)
gdzie \( a_0 \leq a_1 \leq \ldots \leq a_{k-1}\leq 1 \).
Liczbę podziałów \( n \) na \( k \) składników oznaczamy przez \( P(n,k) \).
Przykład
Lista podziałów \( 7 \) na \( 4 \) składniki:
\( 1+1+1+4,\qquad 1+1+2+3,\qquad 1+2+2+2. \)
Obserwacja 6.23
Dla \( n,k\in\mathbb{N}-{\{ {0} \} } \)
Dowód
Uzasadnimy jedynie ostatni punkt. Dla dowodu ograniczenia górnego liczby \( P(n,k) \) zauważmy, że interesujące nas podziały liczby \( n \) są rozwiązaniami równania \( n=x_0+\ldots+x_{k-1} \), a tych, jak już wiemy, jest dokładnie \( {n-1\choose k-1} \).
Z drugiej strony dowolny podział liczby \( n \) generuje co najwyżej \( k! \) rozwiązań równania \( n=x_0+\ldots+x_{k-1} \) (generuje dokładnie \( k! \), jeśli składniki podziału są parami różne) i wszystkie rozwiązania mogą zostać w ten sposób osiągnięte. To oczywiście daje ograniczenie dolne.
Ograniczenie górne dla \( P(n,k) \) można poprawić:
Obserwacja 6.24
\( P(n,k) \leq \frac{1}{k!}{n+{k\choose2}-1\choose k-1}. \)
Dowód
Dla podziału \( n=a_0+\ldots+a_{k-1} \) definiujemy
\( b_i=a_i+(k-1-i),\qquad\mbox{ dla }{0}\leq{i}\leq{k-1}. \)
Zauważmy, że wszystkie liczby \( b_i \) są różne oraz
\( b_0+\ldots+b_{k-1}=n+\frac{k(k-1)}{2}. \)
A zatem podziały liczby \( n \) na \( k \) składników stoją w bijektywnej odpowiedniości z podziałami liczby \( n+{k\choose 2} \) na \( k \) parami różnych składników. Każdy podział \( n+{k\choose2} \) na \( k \) parami różnych składników generuje dokładnie \( k! \) rozwiązań równania
\( x_0+\ldots+x_{k-1}=n+{k\choose 2}, \)
gdzie \( x_i>0 \). Wiemy zaś, że to ostatnie równanie posiada co najwyżej \( {n+{k\choose2}-1\choose k-1} \) rozwiązań. A zatem ciągów \( \langle b_i \rangle \), a tym samym podziałów \( n \) na \( k \) składników, jest co najwyżej \( \frac{1}{k!}{n+{k\choose2}-1\choose k-1} \).
Ostatnia obserwacja pozwala na opisanie granicznego zachowania liczb \( P(n,k) \) przy ustalonym \( k \).
Wniosek 6.25
Dla dowolnego \( k \)
\( \displaystyle \lim_{n\to\infty}\frac{P(n,k)}{n^{k-1}}=\frac{1}{k!(k-1)!}. \)
Dość skutecznym narzędziem do badania podziałów liczb naturalnych są tzw. diagramy Ferrersa.
Diagram Ferrersa dla podziału \( n=a_0+\ldots+a_{k-1} \) składa się z \( k \) wierszy o odpowiednio \( a_{i-1} \) elementach.
\( 2+5+6+6+9=28. \)
\( 1+3+3+3=10. \)
Użyteczność diagramów Ferrersa ilustrują dowody kilku nastepnych obserwacji.
Obserwacja 6.26
Liczba \( P(n,k) \) jest równa liczbie podziałów liczby \( n \) (na dowolną liczbę składników) o największym składniku równym \( k \).
Dowód
Odwracając o \( 90 \) stopni diagram podziału liczby \( n \) na \( k \) składników otrzymamy diagram podziału liczby \( n \), którego największy składnik równy jest \( k \). Oczywiście jest to odwzorowanie bijektywne, gdyż odwracając z powrotem o \( 90 \) stopni otrzymamy ten wyjściowy diagram.
Obserwacja 6.27
Liczba \( P(n+k,k) \) jest równa liczbie podziałów \( n \) na co najwyżej \( k \) składników.
Dowód
Wycinając ostatnią kolumnę w diagramie podziału liczby \( n+k \) na \( k \) składników otrzymamy podział liczby \( n \) na co najwyżej \( k \) składników. Łatwo zauważyc, że jest to odwzorowanie bijektywne.