Monety w fontannie

Monety w fontannie to problem w matematyce kombinatorycznej , który obejmuje funkcję generującą . Problem jest opisany poniżej:

 Na ile różnych sposobów można ułożyć  n  monet z  k  monetami u podstawy, tak aby wszystkie monety znajdujące się powyżej warstwy podstawowej stykały się dokładnie z dwiema monetami warstwy dolnej. 

Rozwiązanie :

Kilka pierwszych wyrazów ciągu

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	1	2	3	5	9	15	26	45	78	135	234	...

Powyższa sekwencja pokazuje, na ile sposobów można ułożyć n monet. I tak np. za 9 monet mamy 45 różnych sposobów ułożenia ich w fontannie. Liczba , która jest rozwiązaniem powyższego problemu, jest wtedy dana przez współczynniki wielomianu następującej funkcji generującej: ${\ Displaystyle f (n, k)}$

${\ Displaystyle {\ rozpocząć {wyrównane} f (n, k) = {\ dfrac {1} {1- {\ dfrac {xy}{1-{\dfrac {x^{2}y}{1-{\dfrac {x^{3}y}{\cdots}}}}}}}}\end{wyrównane}}}$

 

 

 

 

()

Taka funkcja generująca jest szeroko badana w

W szczególności liczbę takich fontann, które można stworzyć za pomocą n monet, określają współczynniki:

${\ Displaystyle {\ rozpocząć {wyrównane} f (n) i = & {\ dfrac {1} {1- {\ dfrac {x} 1-{\dfrac {x^{2}}{1-{\dfrac {x^{3}}{\cdots}}}}}}}}\,\end{wyrównane}}}$

 

 

 

 

()

Można to łatwo zauważyć, podstawiając wartość y na 1. Jest tak, ponieważ załóżmy, że funkcja generująca dla ( 1 ) ma postać:

${\ Displaystyle \ suma _ {n} \ suma _ {k} C_ {n, k} x ^ {n} y ^ {k}}$

następnie, jeśli chcemy uzyskać całkowitą liczbę fontann, musimy wykonać sumowanie po k . Tak więc liczbę fontann z n monet można wyrazić wzorem:

${\ Displaystyle \ suma _ {k} C_ {n, k} x ^ {n} y ^ {k}}$

co można otrzymać, podstawiając wartość y na 1 i obserwując współczynnik x ⁿ .

Dowód funkcji generującej ( 1 ). Rozważmy, ile sposobów uformowania fontanny z n monet z k monetami u podstawy daje ${\ Displaystyle f (n, k)}$ . Rozważmy teraz, na ile sposobów można uformować to samo, ale z zastrzeżeniem, że druga od dołu warstwa (powyżej warstwy bazowej) nie zawiera luk, czyli zawiera dokładnie k − 1 monet. Nazwijmy to prymitywną fontanną i oznaczmy ją przez ${\ Displaystyle g (n, k)}$ . Te dwie funkcje są powiązane następującym równaniem:

${\ Displaystyle {\ rozpocząć {wyrównane} g (n, k) i = f (nk, k-1) \, \ koniec {wyrównane}} }$

 

 

 

 

()

Dzieje się tak, ponieważ możemy postrzegać prymitywną fontannę jako normalną fontannę n - k' monet z k - 1 monetami w warstwie podstawowej ułożonymi na wierzchu pojedynczej warstwy k monet bez żadnych przerw. Weźmy również pod uwagę normalną fontannę z rzekomą przerwą w przedostatniej warstwie (w warstwie podstawowej) w pozycji r . Tak więc normalną fontannę można postrzegać jako zestaw dwóch fontann:

1. Prymitywna fontanna zawierająca n ' monet i warstwę podstawową zawierającą r monet.
2. Zwykła fontanna z n − n ' monetami i warstwą bazową zawierającą k − r monet.

Otrzymujemy więc następującą zależność:

${\ Displaystyle {\ rozpocząć {wyrównane} f (n, k) & = \ suma _ {r }g(n',r)\czasy f(nn',kr)\end{wyrównane}}}$

 

 

 

 

()

Teraz możemy łatwo zaobserwować, że relacja funkcji generującej dla ( 4 ) ma postać:

${\ Displaystyle F (x, y) = 1 + F (x, y). G (x, y)}$

 

 

 

 

()

i aby ( 3 ) było:

${\ Displaystyle G (x, y) = xyF (x, xy)}$

 

 

 

 

()

Podstawiając ( 6 ) w ( 5 ) i przestawiając, otrzymujemy zależność:

${\ Displaystyle {\ rozpocząć {wyrównane} F (x, y) & = {\ dfrac {1} {1-xyF (x, xy)}} i = {\ dfrac {1} 1-{\dfrac {xy}{1-x^{2}yF(x,x^{2}y)}}}}&=\cdots &={\dfrac {1}{1-{\dfrac { xy}{1-{\dfrac {x^{2}y}{1-{\dfrac {x^{3}y}{\cdots}}}}}}}}\end{wyrównane}}}$