Podziały liczby

Podziały liczby


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. \)

  • \( P(7,4)=3 \).

Obserwacja 6.23

Dla \( n,k\in\mathbb{N}-{\{ {0} \} } \)

  • \( P(n,1)=1 \),
  • \( P(n,2)=\lfloor \frac{n}{2}\rfloor \),
  • \( P(n,n)=1 \),
  • \( P(n,k)=0 \), dla \( n < k \)
  • \( \frac{1}{k!}{n-1\choose k-1}\leq P(n,k)\leq{n-1\choose k-1} \).

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.