Funkcje tworzące

Drukuj

Poziom studiów

Funkcja tworząca jest narzędziem w kombinatoryce i teorii szeregów służącym do kodowania ciągów liczb w postaci formalnych szeregów potęgowych. Za pomocą tego narzędzia można zliczać obiekty kombinatoryczne oraz rozwiązywać rekurencje.

Definicja

Funkcja tworząca (generująca) \(G(x)\) dla ciągu \((a_n)=(a_0, a_1, a_2,...)\) to formalny szereg potęgowy: \[G(x) = \sum_{n=0}^{\infty }a_nx^n \]

Określenie szeregu \(\sum_{n=0}^{\infty }a_nx^n\) jako formalny oznacza, że traktujemy go jako obiekt czysto algebraiczny, w którym nie rozważamy zbieżności ani wartości funkcji. Traktujemy ten nieskończony wielomian jako czysto formalną sumę.

Zauważmy również, że w powyższej definicji numerujemy wyrazy ciągu od \(0\), czyli pierwszy wyraz ciągu to \(a_0\).

Dla ciągu: \((6, 4, 2, 0, 0, 0,...)\), który ma niezerowe tylko pierwsze trzy wyrazy, funkcja tworząca to: \[G(x) = \sum_{n=0}^{\infty }a_nx^n=6x^0+4x^1+2x^2+0x^3+...\] Kolejne wyrazy sumy zerują się, czyli ostatecznie funkcja tworząca to: \[G(x) = 6+4x+2x^2\]

Dla ciągu \(a_n=(1,1,1,\dots)\), w którym każdy wyraz wynosi \(1\), funkcja tworząca to:

\( G(x) = \sum_{n=0}^{\infty} a_n\,x^n \) \( = \sum_{n=0}^{\infty} 1\cdot x^n \) \( = 1 + x + x^2 + x^3 + \cdots \)

Korzystając ze wzoru na sumę szeregu geometrycznego \(1, x, x^2, x^3,...\) o pierwszym wyrazie równym \(1\) oraz ilorazie \(q=x\) otrzymujemy: \[1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}\] Zatem ostatecznie funkcja tworząca to: \[G(x)=\frac{1}{1 - x}\]

Dla ciągu \(a_n = n+1\), czyli \(a_n=(1,2,3,4,\dots)\), funkcja tworząca to:

\(G(x) = \sum_{n=0}^{\infty} a_nx^n\) \(= \sum_{n=0}^{\infty} (n+1)x^n\) \(= 1 + 2x + 3x^2 + 4x^3 + \cdots\)

Spróbujemy wyznaczyć skończony wzór na \(G(x)\).

W tym celu wykorzystamy równanie wyprowadzone w poprzednim przykładzie: \[\sum_{n=0}^{\infty} x^n = \frac{1}{1 - x}\] Zróżniczkujmy je stronami (bo dzięki temu otrzymamy wyrażenie zbliżone do \(\bigl((n+1)x^n\bigl)\)): \[\begin{split} \frac{d}{dx}\left(\sum_{n=0}^{\infty} x^n\right) &= \frac{d}{dx}\left(\frac{1}{1 - x}\right)\\[6pt] \sum_{n=1}^{\infty} nx^{n-1} &= \frac{1}{(1 - x)^2}\\[6pt] \end{split}\] W wyniku policzenia pochodnej lewej strony zmienił się zakres sumowania z \(n\in \{0,1,2,...\}\) na \(n\in \{1,2,3,...\}\). Wynika to z tego, że pochodna pierwszego wyrazu sumy \(\sum_{n=0}^{\infty} x^n\) jest równa zero (bo jest to liczba stała).
Możemy jednak wrócić z sumowaniem od \(n=0\). Należy tylko zmienić we wzorze wszystkie \(n\) na \(n+1\): \[\sum_{n=1}^{\infty} nx^{n-1} = \sum_{n=0}^{\infty} (n+1)x^n \] Zatem, mamy: \[\sum_{n=0}^{\infty} (n+1)x^n = \frac{1}{(1 - x)^2}\] Pokazaliśmy zatem, że: \[1 + 2x + 3x^2 + 4x^3 + \cdots = \frac{1}{(1 - x)^2}\]

Dla ciągu \(a_n = n(n-1)\), czyli \(a_n=(0,0,2,6,12,\dots)\), funkcja tworząca to:

\(G(x) = \sum_{n=0}^{\infty} n(n-1)\,x^n\) \(= 2x^2 + 6x^3 + 12x^4 + \cdots\)

Spróbujemy wyznaczyć skończony wzór na \(G(x)\).
W tym celu skorzystamy z podstawowego wzoru na sumę szeregu geometrycznego: \[ \sum_{n=0}^{\infty} x^n = \frac{1}{1 - x} \] Różniczkujemy raz stronami: \[ \begin{split} \frac{d}{dx}\Bigl(\sum_{n=0}^{\infty} x^n\Bigr) &= \frac{d}{dx}\Bigl(\tfrac{1}{1-x}\Bigr) \\[6pt] \sum_{n=1}^{\infty} n\,x^{n-1} &= \frac{1}{(1 - x)^2} \\[6pt] \end{split} \] i drugi raz: \[ \begin{split} \frac{d}{dx}\Bigl(\sum_{n=1}^{\infty} n\,x^{n-1}\Bigr) &= \frac{d}{dx}\Bigl(\tfrac{1}{(1 - x)^2}\Bigr) \\[6pt] \sum_{n=2}^{\infty} n(n-1)\,x^{n-2} &= \frac{2}{(1 - x)^3} \end{split} \] Mnożąc obustronnie przez \(x^2\) otrzymujemy: \[ \sum_{n=2}^{\infty} n(n-1)\,x^n = \frac{2x^2}{(1 - x)^3}. \] A ponieważ \(a_0 = a_1 = 0\), można spokojnie zacząć sumowanie od \(n=0\): \[ \sum_{n=0}^{\infty} n(n-1)\,x^n = \frac{2x^2}{(1 - x)^3}. \] Pokazaliśmy zatem, że: \[2x^2 + 6x^3 + 12x^4 + \cdots = \frac{2x^2}{(1 - x)^3}\]

Do pudełka wkładamy nierozróżnialne kule. Wyznacz funkcję tworzącą liczby rozmieszczeń kul w pudełku jeśli w pudełku ma być nieparzysta liczba kul.

Aby zapisać funkcję tworzącą musimy najpierw zdefiniować ciąg. Niech ciąg \(a_n\) oznacza liczbę sposobów na umieszczenie dokładnie \(n\) kul w pudełku, spełniających dany warunek. Skoro tylko nieparzyste \(n\) są dozwolone, to \[ a_n = \begin{cases} 1, & \text{dla }n \text{ nieparzystego},\\ 0, & \text{dla }n \text{ parzystego}. \end{cases} \]

Taka konstrukcja ciągu wynika z tego, że jeżeli włożymy do pudełka konkretną, nieparzystą liczbę kul (np. \(7\) kul), to możemy to zrobić tylko na \(1\) sposób (bo kule są nierozróżnialne). Zatem na \(7\) miejscu w ciągu stoi liczba \(1\) (bo mamy \(1\) sposób na włożenie \(7\) kul do pudełka). Na parzystych miejscach stoją zera, bo mamy \(0\) sposobów żeby włożyć parzystą liczbę kul do pudełka.

Czyli ciąg dla którego mamy stworzyć funkcję tworzącą ma postać: \[(0,1,0,1,...)\] Zatem mamy:

\(G(x) = \sum_{n=0}^{\infty} a_n\,x^n\) \(= x + x^3 + x^5 + \cdots\)

Korzystając ze wzoru na szereg geometryczny o pierwszym wyrazie równym \(x\) i ilorazie \(q=x^2\) mamy: \[ x + x^3 + x^5 + \cdots = \frac{x}{1 - x^2} \]

Do dwóch pudełek wkładamy nierozróżnialne kule. W pierwszym ma być parzysta liczba kul, a w drugim nieparzysta. Wyznacz funkcję tworzącą i oblicz liczbę możliwych rozmieszczeń dla

\(n=13\) kul
\(n=14\) kul

Aby zapisać funkcję tworzącą powinniśmy najpierw zdefiniować ciąg \(a_n\).
Może się okazać, że jeżeli mamy zdarzenie złożone z kilku niezależnych zdarzeń, to trudno jest od razu podać ciąg dla całości. Wtedy konstruujemy niezależne ciągi dla wszystkich niezależnych zdarzeń (u nas dla każdego pudełka oddzielnie) i tworzymy dla nich oddzielne funkcje tworzące.

W pierwszym pudełku mamy mieć parzystą liczbę kul, zatem liczbę sposobów na jaką możemy tam włożyć \(n\) kul określa ciąg \(b_n=(1,0,1,0,...)\), czyli funkcja tworząca dla tego ciągu to: \[ G_1(x) = 1+x^2+x^4+\cdots = \frac{1}{1 - x^2} \] W drugim pudełku mamy mieć nieparzystą liczbę kul, zatem liczbę sposobów na jaką możemy tam włożyć \(n\) kul określa ciąg \(c_n=(0,1,0,1,...)\), czyli funkcja tworząca dla tego ciągu to: \[ G_2(x) = x+x^3+x^5+\cdots = \frac{x}{1 - x^2} \] Ponieważ pudełka są niezależne, to ich łączna funkcja tworząca jest iloczynem funkcji tworzących:

\[ G(x) = G_1(x)\,G_2(x) = \frac{1}{1 - x^2}\;\cdot\;\frac{x}{1 - x^2} = \frac{x}{(1 - x^2)^2} \]

Na podstawie rozwinięcia: \[\displaystyle\frac{1}{(1 - x^2)^2} = \sum_{k=0}^{\infty}(k+1)x^{2k}\] (które pokazaliśmy w poprzednich przykładach), otrzymujemy: \[ G(x) = \sum_{n=0}^{\infty}(n+1)x^{2n+1}. \] Niech \(a_n\) oznacza współczynnik przy \(x^n\) funkcji \(G(x)\). Wówczas: \[ a_n = \begin{cases} \frac{n+1}{2}, & \text{dla }n\text{ nieparzystego},\\ 0, & \text{dla }n\text{ parzystego}. \end{cases} \] Zatem ciąg \(a_n=(a_0,a_1,a_2,a_3,\dots)\) dla całego zdarzenia ma postać: \[ (0,\;1,\;0,\;2,\;0,\;3,\;0,\;4,\;\dots). \] Zatem liczba sposobów rozmieszczeń wynosi:

dla \(13\) kul: \(a_{13} = \frac{13+1}{2} = 7\).
dla \(14\) kul: \(a_{14} = 0\).