Przypomnijmy, że przez \( P(n,k) \) oznaczyliśmy liczbę podziałów liczby \( n \) na dokładnie \( k \) składników. Wtedy \( \displaystyle p_n = \sum_{k=1}^n P(n,k) \) oznacza liczbę wszystkich możliwych podziałów liczby \( n \) na sumę.
Przykład
Policzmy wszystkie sposoby przedstawienia liczby \( 6 \) za pomocą sumy dodatnich liczb naturalnych.
\( 6=a_0+a_1+\ldots+a_{k-1}, \)
gdzie \( k \) oraz \( \displaystyle a_0\leq a_1 \leq \ldots \leq a_{k-1} \) są dodatnimi liczbami naturalnymi. Oto one
\( \begin{array} {rclp{2cm}rcl} 6 & = & 1+1+1+1+1+1 & & 6 & = & 2+2+2 \\ 6 & = & 1+1+1+1+2 & & 6 & = & 1+5 \\ 6 & = & 1+1+1+3 & & 6 & = & 2+4 \\ 6 & = & 1+1+2+2 & & 6 & = & 3+3 \\ 6 & = & 1+1+4 & & 6 & = & 6 \\ 6 & = & 1+2+3 & & & & \end{array} \)
tzn. \( p_6 =11 \).
Funkcja tworząca podziału liczby na sumy to szereg
\( {P}(x)=p_0+p_1x+p_2x^2+p_3x^3+\ldots \)
Ponadto funkcja tworząca podziału liczby na sumy złożone wyłącznie z liczb \( k_1, k_2, \ldots, k_m \) oznaczać będziemy przez
\( {P_{k_1,k_2,\ldots, k_m}}(x)=p'_0+p'_1x+p'_2x^2+p'_3x^3+\ldots, \)
gdzie \( p'_n \) to liczba podziałów liczby \( n \) na sumę \( n=a_0+a_1+\ldots+a_{k-1}, \) gdzie \( k\in\mathbb{N}-{\{ {0} \}\ } \) oraz \( a_0,a_1, \ldots, a_{k-1}\in{\{ {k_1, k_2, \ldots, k_m} \}\ } \).
Przykład
Pierwszy przykład w wykładzie o funkcjach tworzących dotyczył możliwości rozmiany kwoty za pomocą jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Rozważaliśmy więc tam funkcję tworzącą \( {P_{1,5,10,25,50}}(x) \).
Obserwacja 8.7
\( {P_k}(x)=1+x^k+x^{2k}+x^{3k}+\ldots=\frac{1}{1-x^k}. \)
Dowód
Niech \( p_{k,n} \) będzie liczbą rozkładów liczby \( n \) na sumę złożoną wyłącznie ze składników równych \( k \). Oczywiście jeśli \( k \) dzieli \( n \), to istnieje dokładnie jedna suma \( n=k+k+\dots+k \). Jeśli natomiast \( n \) nie jest podzielne przez \( k \), to taki rozkład nie istnieje, tak więc
\( p_{k,n}=\lbrace\begin{array} {ll} 1, & \textrm{jeśli}\ n=ak\ \textrm{dla}\ a=0,1,2,\ldots \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} . \)
Otrzymujemy w ten sposób
\( \begin{align*} {P_k}(x) & =p_{k,0}+p_{k,1}x+p_{k,2}x^2+\ldots \\ & =1+x^k+x^{2k}+x^{3k}+\ldots, \end{align*} \)
która to funkcja zwija się do
\( {P_k}(x)\ =\ \frac{1}{1-x^k}. \)
Obserwacja 8.8
\( {P_{k_1,k_2,\ldots, k_m}}(x)\ =\ {P_{k_1}}(x)\cdot {P_{k_2}}(x)\cdot\ldots\cdot {P_{k_m}}(x) =\ \frac{1}{1-x^{k_1}}\cdot\frac{1}{1-x^{k_2}}\cdot\ldots\cdot\frac{1}{1-x^{k_m}}. \)
Dowód
Załóżmy, że splot
\( (1+x^{k_1}+x^{2k_1}+\ldots)\cdot (1+x^{k_2}+x^{2k_2}+\ldots)\cdot\ \cdot(1+x^{k_m}+x^{2k_m}+\ldots) \)
jest przedstawiony jako szereg \( p'_0+p'_1x+p'_2x^2+p'_3x^3+\ldots \). Wtedy oczywiście \( p'_nx^n \) jest sumą wszystkich jednomianów postaci \( x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}} \), dla których \( x^n=x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}} \). Współczynnik \( p'_n \) więc jest liczbą wszystkich ciągów \( s,j_1,\ldots,j_s,l_1,\ldots,l_s \) takich, że
\( \begin{align*} n & =j_1k_{l_1}+j_2k_{l_ 2}+\ldots+j_sk_{l_s} \\ & =(k_{l_1}+\ldots+k_{l_1})+(k_{l_2}+\ldots+k_{l_2})+\ldots+(k_{l_s}+\ldots+k_{l_s}), \end{align*} \)
tzn. \( p'_n \) jest liczbą rozkładów liczby \( n \) na sumy o składnikach ze zbioru \( {\{ {k_1, k_2,\ldots,k_n} \}\ } \), a zatem \( p'_n \) jest \( n \)-tym współczynnikiem funkcji tworzącej \( {P_{k_1,k_2,\ldots, k_m}}(x) \).
Przykład
Niech \( {P_{1,2,3,4}}(x)=p''_0+p''_1x+p''_2x^2+\ldots \). Współczynnik \( p''_6 \) to liczba iloczynów postaci \( x^{j_1k_{l_1}}\cdot x^{j_2k_{l_2}}\cdot\ldots\cdot x^{j_sk_{l_s}} \) równych \( x^6 \), a zarazem liczba podziałów liczby \( 6 \) na sumy złożone ze składników \( 1,2,3 \) oraz \( 4 \). Każdemu iloczynowi odpowiada jeden podział. Na przykład \( x^{1\cdot4}\cdot x^{2\cdot1} \), gdzie \( x^{1\cdot4} \) pochodzi z \( {P_1}(x) \) oraz \( x^{2\cdot1} \) pochodzi z \( {P_2}(x) \), odpowiada sumie \( 6=1+1+1+1+2 \). Poniżej zaznaczono w funkcji tworzącej \( {P_{1,2,3,4}}(x) \) jednomiany \( \mathbf{x^{(1+1+1+1)}} \) oraz \( \mathbf{x^2} \)
\( \begin{array} {l} {P_{1,2,3,4}}(x)\ =\ 1+x+2x^2+3x^3+4x^4+6x^5+7x^6+\ldots \\ = \ (1 +x^1 +x^{(1+1)} +x^{(1+1+1)} +\mathbf{{x^{(1+1+1+1)}}} +x^{(1+1+1+1+1)} +x^{(1+1+1+1+1+1)} +\ldots) \\ = \cdot(1 +\mathbf{{x^2}} +x^{(2+2)} +x^{(2+2+2)} +x^{(2+2+2+2)} +x^{(2+2+2+2+2)} +\ldots) \\ = \cdot(1 +x^3 +x^{(3+3)} +x^{(3+3+3)} +x^{(3+3+3+3)} +x^{(3+3+3+3+3)} +\ldots) \\ = \cdot(1 +x^4 +x^{(4+4)} +x^{(4+4+4)} +x^{(4+4+4+4)} +x^{(4+4+4+4+4)} +\ldots) \end{array} \)
Odpowiadają one zaznaczonemu rozkładowi na liście wszystkich rozkładów liczby \( 6 \):
\( \begin{array} {lp{2cm}l} 6\ =\ 1+1+1+1+1+1, & & 6\ =\ 1+2+3, \\ \mathbf{\underline{6\ =\ 1+1+1+1+2}}, & & 6\ =\ 2+2+2, \\ 6\ =\ 1+1+1+3, & & 6\ =\ 3+3. \\ 6\ =\ 1+1+2+2, & & \end{array} \)
Przykład
W funkcji tworzącej
\( {P_{1,5,10,25,50}}(x)=p'''_0+p'''_1x+p'''_2x^2+\ldots. \)
współczynnik \( p'''_n \) jest liczbą podziałów liczby \( n \) na sumy postaci
\( n=1+\ldots+1+5+\ldots+5+10+\ldots+10+25+\ldots+25+50+\ldots+50, \)
czyli liczbą sposobów na jakie można rozmienić \( n \) centów przy użyciu jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Otrzymaliśmy więc rozwiązanie przykładu o rozmienianiu monet. Funkcja tworząca jest w poznanej już postaci równej
\( {P_{1,5,10,25,50}}(x)=\frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{25}}\cdot\frac{1}{1-x^{50}}. \)
Widzieliśmy już, że ogólnie
\( {P_{k_1k_2\ldots k_m}}(x)\ =\ \frac{1}{1-x^{k_1}}\cdot\frac{1}{1-x^{k_2}}\cdot\ldots\cdot\frac{1}{1-x^{k_m}}. \)
Twierdzenie 8.9[L. Euler]
Funkcja tworząca podziału liczby na sumy jest przedstawialna jako
\( \displaystyle {P}(x)=\prod_{k=1}^{\infty}\frac{1}{1-x^k} =\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\ldots\cdot\frac{1}{1-x^n}\cdot\ldots \)
Dowód
Niech \( {P_{(m)}}(x)= {P_{1,2,\ldots,m}}(x) \) rozwija się w szereg \( \displaystyle \sum_{n=0}^\infty p_{(m)n}x^n \), a formalny nieskończony splot
\( \displaystyle \prod_{k=1}^{\infty} {P_k}(x) = \prod_{k=1}^{\infty}\frac{1}{1-x^k} = \prod_{k=1}^{\infty}(1+x^k+x^{2k}+x^{3k}+\ldots) \)
zwija się do szeregu formalnego
\( {F}(x)=f_0+f_1x+f_2x^2+f_3x^3+\ldots \)
Oczywiście przy liczeniu \( f_n \) z czynników \( (1+x^k+x^{2k}+x^{3k}+\ldots) \), gdzie \( k>n \), jedynie jednomian \( 1 \) odgrywa rolę, gdyż jednomiany \( x^{lk} \) z \( l\geq1 \) dają zbyt duże potęgi. A zatem \( f_n=p_{(n)n} \). Ponieważ żaden składnik w rozkładzie \( n=a_0+a_1+\ldots+a_s \) nie może przekraczać \( n \), mamy \( p_n=p_{(n)n} \), skąd natychmiast \( f_n=p_n \), co kończy dowód.