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.