Funkcja tworząca w zadaniach kombinatorycznych

[Sahaiel]

Cześć,
Jestem totalnym laikiem matematycznym i mam problem ze zrozumieniem jak za pomocą funkcji tworzącej wykonać zadanie typu: Znaleźć funkcję tworzącą dla rozmieszczeń k identycznych kul w 4 rozróżnialnych szufladach, przy czym pierwsze dwie zawierają parzystą liczbę kul, trzecia zawiera nie parzystą a czwarta zawiera jedną, trzy, pięć lub siedem kul. Wyznacz liczbę rozkładu dla 8 kul.

Mam taką postać funkcji: \(\displaystyle{ (1+x^{2}+x^{4}+x^{6}+...)(1+x^{2}+x^{4}+x^{6}+...)(x+x^{3}+x^{5}+x^{7}+...)(x+x^{3}+x^{5}+x^{7})}\)

Rozumiem że nawiasy odpowiadają szufladom a x'y w nawiasach ilości kul. Wiem też że po wymnożeniu nawiasów wynikiem będzie współczynnik przy ósmej potędze.

Mam problem natomiast z wykonywaniem tego typu zadań gdy w grę wchodzą większe liczby, widziałem sposoby w których funkcje tworzące mają postać typu: \(\displaystyle{ \frac{1}{1+x}}\). Przejrzałem już różne fora, sięgałem do książek, lecz dalej nie jestem w stanie zrozumieć jak funkcje przechodzą do takiej postaci i jak wykorzystać tego typu funkcję do obliczania zadań.

Jeśli znajdzie się jakaś dobra dusza, która w miarę łopatologicznie i opisowo wytłumaczy o co w tym chodzi, to będę dozgonnie wdzięczny.

[Janusz Tracz]

Wytłumaczenia jak działają funkcje tworzące się nie podejmę bo mam za małe kompetencje ale mogę Ci pokazać czemu \(\displaystyle{ 1+x+x^2+x^3+...= \frac{1}{1-x}}\). Wzór ten bierze się z sumy szeregu geometrycznego w którym \(\displaystyle{ a_1=1}\) oraz \(\displaystyle{ q=x}\). Można to też wyprowadzić, oznaczmy lewą stronę przez \(\displaystyle{ S}\) wtedy:

\(\displaystyle{ S=1+x+x^2+x^3+...=1+x \cdot \left( 1+x+x^2+x^3+...\right)=1+xS}\)

Czyli po prostych przekształceniach \(\displaystyle{ S= \frac{1}{1-x}}\). Ważne jest że wzór ten działa dla \(\displaystyle{ \left| x\right|<1}\). W innych przykładach będzie oczywiście inaczej bo na przykład

\(\displaystyle{ 1+x^2+x^4+x^6+...= \frac{1}{1-x^2}}\)

Jako że \(\displaystyle{ q=x^2}\) w tym konkretnym przypadku.

[Sahaiel]

To mi trochę rozjaśniło. Czyli dla powyższego przykładu funkcje będą miały postać:
\(\displaystyle{ \left( \frac{1}{1-x^{2}} \right) ^2, \left( \frac{x}{1-x^{2}} \right) , \left( \frac{x \cdot \left( 1-x^{7} \right) }{1-x^{2}} \right)}\) ?

Jeśli tak, to teraz pytanie jak za pomocą tego obliczyć liczbę rozkładu dla 8 elementów?

[Janusz Tracz]

To mi trochę rozjaśniło. Czyli dla powyższego przykładu funkcje będą miały postać:
\(\displaystyle{ (\frac{1}{1-x^{2}})^2, (\frac{x}{1-x^{2}}) ,(\frac{x*(1-x^{7})}{1-x^{2}})}\) ?

Prawie, jedna drobna różnica. Zamiast \(\displaystyle{ \frac{x \cdot (1-x^{7})}{1-x^{2}}}\) powinno być \(\displaystyle{ \frac{x \cdot (1-x^{8})}{1-x^{2}}}\).

Jeśli tak, to teraz pytanie jak za pomocą tego obliczyć liczbę rozkładu dla 8 elementów?

By to zrobić trzeba wyznaczyć rozwinięcie dla funkcji tworzącej postaci

\(\displaystyle{ \left( \frac{1}{1-x^{2}}\right) ^2 \cdot \frac{x}{1-x^{2}} \cdot \frac{x \cdot (1-x^{8})}{1-x^{2}}= \frac{x^2(1-x^8)}{(1-x^2)^4}=x^2 \frac{\left( 1+x^2\right)\left( 1+x^4\right) }{\left( 1-x^2\right)^3 }}\)

Zrobić to można ze wzoru \(\displaystyle{ \sum_{k=0}^{ \infty }t^k= \frac{1}{1-t}}\) którego konsekwencją jest (po dwukrotnym różniczkowaniu) wzór:

\(\displaystyle{ \sum_{k=2}^{ \infty }k(k-1)t^{k-2}= \frac{2}{(1-t)^3}}\)

Co po pomnożeniu storniami przez \(\displaystyle{ \frac{t(1+t)(1+t^2)}{2}}\) daje

\(\displaystyle{ \frac{t(1+t)(1+t^2)}{2} \cdot \sum_{k=2}^{ \infty }k(k-1)t^{k-2}= \frac{t(1+t)(1+t^2)}{(1-t)^3}}\)

I dalej po uproszczeniu lewej strony (wciągamy to pod sumę) mamy:

\(\displaystyle{ \sum_{k=2}^{ \infty } \frac{k(k-1)}{2} \left( t^{k-1}+t^{k}+t^{k+1}+t^{k+2}\right)=\frac{t(1+t)(1+t^2)}{(1-t)^3}}\)

kładąc \(\displaystyle{ t=x^2}\) dostajemy rozwinięcie funkcji tworzącej.

\(\displaystyle{ \sum_{k=2}^{ \infty } \frac{k(k-1)}{2} \left( x^{2k-2}+x^{2k}+x^{2k+2}+x^{2k+4}\right)=\frac{x^2(1+x^2)(1+x^4)}{(1-x^2)^3}}\)

Widać teraz że przy \(\displaystyle{ x^8}\) mamy odpowiednio

\(\displaystyle{ ...+\left( \frac{5(5-1)}{2}+\frac{4(4-1)}{2}+\frac{3(3-1)}{2}+\frac{2(2-1)}{2} \right)x^8+...}\)

Czyli \(\displaystyle{ 20}\)

[Sahaiel]

A czemu do tego wzoru akurat druga pochodna? \(\displaystyle{ \sum_{k=0}^{ \infty }t^k= \frac{1}{1-t}}\) jest na to jakaś zasada?