Matematyka dyskretna 1/Ćwiczenia 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

From Studia Informatyczne

Zliczanie obiektów

Ćwiczenie 1

Na ile sposobów można rozmienić 1zł używając jedynie monet: 5gr, 10gr, 20gr, 50gr.

Wskazówka

Znajdź postać funkcji tworzącej ciągu \displaystyle p_0,p_1,p_2,\ldots , gdzie \displaystyle p_n to liczba sum złożonych ze składników \displaystyle 5,10,20,50 sumujących się do \displaystyle n . Następnie przedstaw wartości \displaystyle p_n w postaci zależności rekurencyjnej i wylicz \displaystyle p_{100} .

Rozwiązanie

Szukamy współczynnika \displaystyle p_{100} funkcji tworzącej \displaystyle P_{5,10,20,50}\!\left( x \right)=\sum_{n=0}^{\infty}p_n x^n . Korzystając z Obserwacji 8.8 mamy:


\displaystyle \aligned P_{5,10}\!\left( x \right)&=P_{5}\!\left( x \right)\cdotP_{10}\!\left( x \right),\\ P_{5,10,20}\!\left( x \right)&=P_{5,10}\!\left( x \right)\cdotP_{20}\!\left( x \right),\\ P_{5,10,20,50}\!\left( x \right)&=P_{5,10,20}\!\left( x \right)\cdotP_{50}\!\left( x \right). \endaligned


Ponieważ \displaystyle P_k\!\left( x \right)=\frac{1}{1-x^k} , to podstawiając w miejsce \displaystyle P_{5}\!\left( x \right),P_{10}\!\left( x \right),P_{20}\!\left( x \right),P_{50}\!\left( x \right) odpowiednio \displaystyle \frac{1}{1-x^{5}},\frac{1}{1-x^{10}},\frac{1}{1-x^{20}},\frac{1}{1-x^{50}} dostajemy:


\displaystyle \begin{array} {l p{1cm}l} P_{5}\!\left( x \right)=\frac{1}{1-x^5},&& P_{5,10}\!\left( x \right)=P_{5}\!\left( x \right)\cdot\frac{1}{1-x^{10}},\\ P_{5,10,20}\!\left( x \right)=P_{5,10}\!\left( x \right)\cdot\frac{1}{1-x^{20}},&& P_{5,10,20,50}\!\left( x \right)=P_{5,10,20}\!\left( x \right)\cdot\frac{1}{1-x^{50}}, \end{array}

czyli:


\displaystyle  \aligned P_{5}\!\left( x \right)&=1+x^5P_{5}\!\left( x \right),\\ P_{5,10}\!\left( x \right)&=P_{5}\!\left( x \right)+x^{10}P_{5,10}\!\left( x \right),\\ P_{5,10,20}\!\left( x \right)&=P_{5,10}\!\left( x \right)+x^{20}P_{5,10,20}\!\left( x \right),\\ P_{5,10,20,50}\!\left( x \right)&=P_{5,10,20}\!\left( x \right)+x^{50}P_{5,10,20,50}\!\left( x \right). \endaligned      (1)


Po wprowadzeniu funkcji tworzących:


\displaystyle P_{5}\!\left( x \right)=\sum_{n=0}^{\infty}q_n x^n,\quad  P_{5,10}\!\left( x \right)=\sum_{n=0}^{\infty}r_n x^n,\quad  P_{5,10,20}\!\left( x \right)=\sum_{n=0}^{\infty}s_n x^n, \quad P_{5,10,20,100}\!\left( x \right)=\sum_{n=0}^{\infty}p_n x^n,


i podstawieniu do zależności (1) otrzymamy:


\displaystyle q_n=1,\quad r_n=q_n+r_{n-10},\quad s_n=r_n+s_{n-20},\quad p_n=s_n+p_{n-50}.


Korzystając z tych rekurencyjnych zależności między \displaystyle q_n,r_n,s_n,p_n , możemy policzyć wartości w tabeli:


\displaystyle \begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n&10&20&30&40&50&60&70&80&90&100\\ \hline\hline q_n&1&1&1&1&1&1&1&1&1&1\\ \hline r_n&1&2&3&4&5&6&7&8&9&10\\ \hline s_n&1&2&4&6&9&12&16&20&25&30\\ \hline p_n&1&2&4&6&9&13&18&24&31&39\\ \hline \end{array}


W konsekwencji otrzymujemy, że \displaystyle p_{100}=39 , co oznacza, że 1zł możemy rozmienić na \displaystyle 39 sposobów.

Ćwiczenie 2

Niech \displaystyle f_{n,k,\left( l \right)} będzie liczbą podziałów liczby \displaystyle n na sumę składników nie większych od \displaystyle l , przy czym składników o tej samej wartości jest co najwyżej \displaystyle k . Pokaż, że dla ustalonego \displaystyle k funkcja tworząca ciągu \displaystyle f_{n,k,\left( l \right)} , wyraża się wzorem


\displaystyle \aligned \sum_{n=0}^{\infty}f_{n,k,\left( l \right)}x^n &=\prod_{j=1}^{l}\frac{1-x^{j\left( k+1 \right)}}{1-x^j}\\ &=\left( 1+x+\ldots+x^k \right)\cdot\ldots\cdot\left( 1+x^l+\ldots+x^{lk} \right). \endaligned


Wskazówka

Uzasadnienie jest analogiczne do rozumowań przeprowadzonych w Obserwacji 8.8.

Rozwiązanie

Uzasadnienie będzie składało się z dwu kroków:

1. Niech \displaystyle f_{n,k,l} będzie liczbą rozkładów liczby \displaystyle n na sumę złożoną z co najwyżej \displaystyle k składników \displaystyle l. Jeśli \displaystyle l dzieli \displaystyle n , to istnieje dokładnie jedna suma złożona z liczb równych \displaystyle l postaci \displaystyle n=l+l+\dots+l . Ponadto liczba wystąpień składników \displaystyle l w podziale jest równa \displaystyle n/l . Jeśli \displaystyle n nie jest podzielne przez \displaystyle l to nie istnieje taki rozkład. Tak więc


\displaystyle f_{n,k,l}=\left\lbrace\begin{array} {rl} 1,&\textrm{jeśli}\ n=al\ \textrm{dla}\ a=0,1,2,\ldots,k,\\ 0,&\textrm{w przeciwnym wypadku.} \end{array} \right.


Funkcja tworząca tego ciągu to więc:


\displaystyle \sum_{n=0}^{\infty}f_{n,k,l}x^n =1+x^l+x^{2l}+\ldots+x^{lk}  = \frac{1-x^{l\left( k+1 \right)}}{1-x^l}.

2. W drugim kroku pokażemy, że

\displaystyle \aligned \sum_{n=0}^{\infty}f_{n,k,\left( l \right)}x^n &=\prod_{j=1}^{l}\frac{1-x^{j\left( k+1 \right)}}{1-x^j}\\ &=\left( 1+x+\ldots+x^k \right)\cdot\ldots\cdot\left( 1+x^l+\ldots+x^{lk} \right). \endaligned


Załóżmy, że iloczyn


\displaystyle \left( 1+x+\ldots+x^k \right)\cdot \left( 1+x^2+\ldots+x^{2k} \right)\cdot \ldots\cdot \left( 1+x^l+\ldots+x^{lk} \right)


jest przedstawiony jako szereg \displaystyle p'_0+p'_1x+p'_2x^2+p'_3x^3+\ldots . Wtedy oczywiście \displaystyle p'_nx^n jest sumą wszystkich jednomianów postaci \displaystyle x^{j_1}\cdot x^{2j_2}\cdot\ldots\cdot x^{lj_l} , dla których \displaystyle x^n=x^{j_1}\cdot x^{2j_2}\cdot\ldots\cdot x^{lj_l} . Współczynnik \displaystyle p'_n więc jest liczbą wszystkich ciągów \displaystyle j_1,\ldots,j_l takich, że \displaystyle j_s=0,1,2,\ldots,k oraz


\displaystyle \aligned n&=j_1+2j_2+\ldots+lj_l\\ &=\left( 1+\ldots+1 \right)+\left( 2+\ldots+2 \right)+\ldots+\left( l+\ldots+l \right), \endaligned


tzn. \displaystyle p'_n jest liczbą rozkładów liczby \displaystyle n na sumy o składnikach ze zbioru \displaystyle \left\lbrace 1, 2,\ldots,n \right\rbrace , przy czym składników o tej samej wartości jest nie więcej niż \displaystyle k , a zatem \displaystyle p'_n jest \displaystyle n -tym współczynnikiem funkcji tworzącej \displaystyle \sum_{n=0}^{\infty}f_{n,k,l}x^n .

Ćwiczenie 3

Niech \displaystyle f_{n,k} będzie liczbą podziałów liczby \displaystyle n na składniki wykorzystujących co najwyżej \displaystyle k składników o tej samej wartości. Pokaż, że dla ustalonego \displaystyle k funkcja tworząca ciągu \displaystyle f_{n,k} , wyraża się wzorem


\displaystyle \sum_{n=0}^{\infty}f_{n,k}x^n= \prod_{j=1}^{\infty}\frac{1-x^{j\left( k+1 \right)}}{1-x^j} =\left( 1+x+\ldots+x^k \right)\left( 1+x^2+\ldots+x^{2k} \right)\ldots.


Wskazówka

Korzystając z ćwiczenia 2 przeprowadź rozumowanie analogiczne do przedstawionego w dowodzie Twierdzenia 8.9.

Rozwiązanie

Niech formalny nieskończony splot


\displaystyle \prod_{j=1}^{\infty}\frac{1-x^{j\left( k+1 \right)}}{1-x^j}=\left( 1+x+\ldots+x^k \right)\left( 1+x^2+\ldots+x^{2k} \right)\ldots


zwija się do szeregu formalnego


\displaystyle \sum_{n=0}^{\infty}g_nx^n=g_0+g_1x+g_2x^2+g_3x^3+\ldots.


Oczywiście przy liczeniu \displaystyle g_n z czynników \displaystyle \left( 1+x^l+x^{2l}+x^{3l}+\ldots+x^{kl} \right) , gdzie \displaystyle l>n , jedynie jednomian \displaystyle 1 odgrywa rolę, gdyż jednomiany \displaystyle x^{rl} z \displaystyle r\geq1 dają zbyt duże potęgi. A zatem z ćwiczenia 2 mamy \displaystyle g_n=f_{n,k,\left( n \right)} . Ponieważ żaden składnik w rozkładzie \displaystyle n=a_0+a_1+\ldots+a_s nie może przekraczać \displaystyle n , mamy \displaystyle f_{n,k,\left( n \right)}=f_{n,k} , skąd natychmiast \displaystyle g_n=f_{n,k} , co kończy dowód.

Ćwiczenie 4

Używając funkcji tworzących pokaż, że liczba podziałów liczby \displaystyle n składająca się z liczb nieparzystych jest równa liczbie podziałów \displaystyle n na różne składniki.

Wskazówka

Wyzanacz funkcje tworzące obu ciągów i sprawdź, czy są równe. Skorzystaj ponadto z faktu, że


\displaystyle 1+x=\frac{1-x^2}{1-x}.


Rozwiązanie

Niech \displaystyle F\!\left( x \right)=\sum_{n=0}^{\infty}f_nx^n będzie funkcją tworzącą ciągu liczb \displaystyle f_n podziałów liczby \displaystyle n na składniki nieparzyste, a \displaystyle G\!\left( x \right)=\sum_{n=0}^{\infty}g_nx^n będzie funkcją tworzącą ciągu liczb \displaystyle g_n podziałów liczby \displaystyle n na składniki parami różne. Korzystając z Obserwacji 8.8 mamy:


\displaystyle P_{1,3,5,\ldots,2n+1}\!\left( x \right) =\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdot\ldots\cdot\frac{1}{1-x^{2n+1}}.


W wyniku rozumowania analogicznego do dowodu Twierdzenia 8.9 oraz ćwiczenia 3 otrzymujemy:


\displaystyle F\!\left( x \right) =\prod_{n=0}^{\infty}\frac{1}{1-x^{2n+1}} =\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdot\ldots.


Bazując z kolei na ćwiczeniu 3 otrzymujemy:


\displaystyle G\!\left( x \right) =\prod_{n=0}^{\infty}\left( 1+x^n \right) =\left( 1+x \right)\cdot\left( 1+x^2 \right)\cdot\left( 1+x^3 \right)\cdot\ldots,


co wraz z


\displaystyle 1+y=\frac{1-y^2}{1-y}


daje


\displaystyle \aligned G\!\left( x \right)&=\left( 1+x \right)\cdot\left( 1+x^2 \right)\cdot\left( 1+x^3 \right)\cdot\left( 1+x^4 \right)\cdot\ldots\\ &=\frac{1-x^2}{1-x}\cdot\frac{1-x^4}{1-x^2}\cdot\frac{1-x^6}{1-x^3}\cdot\frac{1-x^8}{1-x^4}\cdot\ldots\\ &=\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^7}\cdot\ldots\\ &=F\!\left( x \right), \endaligned


co kończy dowód.

Ćwiczenie 5

Policz ile jest drzew binarnych o \displaystyle n węzłach, a ile o szerokości nie większej niż \displaystyle n .

Wskazówka

Skorzystaj z Obserwacji 7 wykładu 2 oraz z Twierdzenia opisującego liczby Catalana.

Rozwiązanie

Każdy węzeł w drzewie binarnym jest albo liściem albo węzłem wewnętrznym. Wielkość drzewa to liczba wszystkich węzłów, a szerokość drzewa to liczba liści. Ponieważ \displaystyle \left\vert T \right\vert=2\cdot w \displaystyle  (T)-1, to dla drzewa \displaystyle T o \displaystyle m węzłach wewnętrznych mamy:


\displaystyle \aligned  \textrm{ w } \displaystyle  (T)&=m+1, \\ \left\vert T \right\vert&=2m+1. \endaligned


Wiemy, że liczba drzew binarnych o \displaystyle m węzłach wewnętrznych to liczba Catalana \displaystyle c_m = \frac{1}{m+1}{2m \choose m}. Drzewo o \displaystyle n węzłach ma \displaystyle m= \frac{n-1}{2} węzłów wewnętrznych, a zatem drzew takich jest


\displaystyle \frac{2}{n+1}{n-1\choose \left( n-1 \right)/2}.


Z kolei drzewo binarne o \displaystyle n liściach (czyli szerokości \displaystyle n ) ma \displaystyle n-1 węzłów wewnętrznych, czyli drzew takich jest


\displaystyle \frac{1}{n}{2n-2\choose n-1}.


Ćwiczenie 6

Będziemy poruszać się po punktach zbioru \displaystyle \mathbb{N}^2 w ten sposób, że w jednym ruchu z punktu \displaystyle \left( a,b \right) można się przejść jedynie do \displaystyle \left( a+1,b \right) lub \displaystyle \left( a,b+1 \right) , czyli możliwy jest ruch w "prawo" o \displaystyle 1 lub w "górę" o \displaystyle 1 . Policz na ile sposobów można przejść z punktu \displaystyle \left( 0,0 \right) do punktu \displaystyle \left( n,n \right) poruszając się zgodnie z powyższymi zasadami jedynie po punktach ze zbioru \displaystyle \left\lbrace \left( a,b \right)\in \mathbb{N}^2 :\ a\geq b \right\rbrace .

Wskazówka

Pokaż, że liczba \displaystyle c_n przejść z punktu \displaystyle \left( 0,0 \right) do punktu \displaystyle \left( n,n \right) zgodnie z zasadami postawionymi w zadaniu spełnia


\displaystyle \left\lbrace \aligned c_0&=1,\\ c_n&=c_{n-1}c_0 + c_{n-2}c_1 + \ldots + c_0c_{n-1}\quad\textrm{dla}\ n>1. \endaligned  \right.


Rozwiązanie

<flash>file=Zliczanie catalan N2.swf|width=250|height=250</flash>

Przykładowa ścieżka z punktu \displaystyle \left( 0,0 \right) do punktu \displaystyle \left( n,n \right)=\left( 7,7 \right)

Niech

  • \displaystyle \mathscr{P}_n będzie rodziną ścieżek z punktu \displaystyle \left( 0,0 \right) do punktu \displaystyle \left( n,n \right) przechodzących poniżej prostej opisanej funkcją \displaystyle f\!\left( x \right)=x, czyli zawierających punkty ze zbioru \displaystyle \left\lbrace \left( a,b \right):\ a\geq b \right\rbrace ,
  • \displaystyle c_n=\left\vert \mathscr{P}_n \right\vert będzie szukaną liczbą ścieżek.

Dla ścieżki \displaystyle P\in\mathscr{P}_n niech \displaystyle \left( k,k \right) będzie pierwszym punktem prostej \displaystyle f\!\left( x \right)=x na ścieżce \displaystyle P .

Oznacza to, że odwiedzone pozycje pomiędzy punktami \displaystyle \left( 0,0 \right) oraz \displaystyle \left( k,k \right) były poniżej prostej \displaystyle g\!\left( x \right)=x-1 .

Ścieżkę \displaystyle P można więc rozłożyć na dwie ścieżki:

  • ścieżkę \displaystyle P_1 z punktu \displaystyle \left( 1,0 \right) do \displaystyle \left( k,k-1 \right) poniżej prostej \displaystyle g\!\left( x \right)=x-1 , oraz
  • ścieżkę \displaystyle P_2 z punktu \displaystyle \left( k,k \right) do \displaystyle \left( n,n \right) poniżej prostej \displaystyle f\!\left( x \right)=x .

Z kolei para \displaystyle \left( P_1,P_2 \right) jednoznacznie wyznacza ścieżkę \displaystyle P . Rodzina \displaystyle \mathscr{P}_{n,k}\subseteq\mathscr{P}_n ścieżek, na których punkt \displaystyle \left( k,k \right) jest pierwszym spotkaniem z prostą \displaystyle f\!\left( x \right)=x jest więc równoliczna z produktem \displaystyle \mathscr{P}_{k-1}\times\mathscr{P}_{n-k} . Zachodzi więc


\displaystyle \left\vert \mathscr{P}_{n,k} \right\vert=\left\vert \mathscr{P}_{k-1} \right\vert\cdot\left\vert \mathscr{P}_{n-k} \right\vert.


Ponieważ zbiór ścieżek z \displaystyle \left( 0,0 \right) do \displaystyle \left( n,n \right) jest rozłączną sumą \displaystyle \mathscr{P}_n=\mathscr{P}_{n,1}\cup\mathscr{P}_{n,2}\cup\ldots\cup\mathscr{P}_{n,n} , to


\displaystyle \left\lbrace \aligned c_0&=1,\\ c_n&=c_{n-1}c_0 + c_{n-2}c_1 + \ldots + c_0c_{n-1},\quad\textrm{dla}\ n>1. \endaligned  \right.


A zatem ciąg \displaystyle c_n przedstawia kolejne liczby Catalana, czyli szukana liczba ścieżek z \displaystyle \left( 0,0 \right) do \displaystyle \left( n,n \right) , to


\displaystyle \left\vert \mathscr{P}_n \right\vert=c_n=\frac{1}{n+1}{2n \choose n}.


Ćwiczenie 7

Policz ile jest słów złożonych z liter \displaystyle a,b,c o długości \displaystyle n , w których nie występuje podsłowo \displaystyle ab .

Wskazówka

Niech \displaystyle a_n, b_n, c_n będzie liczbą \displaystyle n -literowych słów zaczynających się odpowiednio od litery \displaystyle a, b lub \displaystyle c i nie zawierających podsłowa \displaystyle ab . Znajdź zależność rekurencyjną pomiędzy liczbami \displaystyle a_n, b_n, c_n , a następnie rozwiąż ją używając funkcji tworzących.

Rozwiązanie

Jeśli \displaystyle w jest słowem \displaystyle n -literowym, to słowo \displaystyle aw nie zawiera podsłowa \displaystyle ab wtedy i tylko wtedy gdy \displaystyle w nie zaczyna się od litery \displaystyle b oraz \displaystyle w nie posiada podsłowa \displaystyle ab . A zatem \displaystyle a_{n+1} to suma liczby \displaystyle n -literowych słów zaczynających się od \displaystyle a bądź \displaystyle c i nie zawierających słowa \displaystyle ab i mających \displaystyle n liter. Otrzymujemy więc, że \displaystyle a_{n+1}=a_n+c_n . Z kolei jeśli \displaystyle n -literowe słowo \displaystyle v nie zawiera podsłowa \displaystyle ab , to także słowa \displaystyle bv , oraz \displaystyle cv nie zawierają podsłowa \displaystyle ab . W konsekwencji otrzymujemy układ równań rekurencyjnych:


\displaystyle \left\lbrace \aligned a_{n+1}&=a_n+c_n\\ b_{n+1}&=a_n+b_n+c_n\\ c_{n+1}&=a_n+b_n+c_n \endaligned  \right.


dla \displaystyle n\geq1 oraz \displaystyle a_1=b_1=c_1=1 . Ponieważ


\displaystyle b_{n+1} = a_n+b_n+c_n= c_{n+1}\quad dla \displaystyle  \ n\geq1,


to układ ten redukuje się do:


\displaystyle \left\lbrace \aligned a_{n+1}&=a_n+b_n\\ b_{n+1}&=a_n+2b_n. \endaligned  \right.


dla \displaystyle n\geq1 . Z pierwszego równania wynika, że \displaystyle b_n=a_{n+1}-a_n , co po podstawieniu do drugiego równania daje


\displaystyle a_{n+2}-a_{n+1}=a_n+2\left( a_{n+1}-a_n \right).


Po uproszczeniu oraz wyliczeniu \displaystyle a_2 dostajemy:


\displaystyle \left\lbrace \aligned a_1&=1,\\ a_2&=2,\\ a_{n+2}&=3a_{n+1}-a_n\quad\textrm{dla}\ n\geq1. \endaligned  \right.


Następnie korzystamy z metody rozwiązywania jednorodnych liniowych równań rekurencyjnych dla \displaystyle k=2 przedstawionej na wykładzie. Rozkładamy na iloczyn wielomian:


\displaystyle 1-3x+x^2=\left( 1-\frac{3-\sqrt{5}}{2}x \right)\left( 1-\frac{3+\sqrt{5}}{2}x \right),


By dostać, że rozwiązanie jest postaci:


\displaystyle a_n=\alpha\left( \frac{3-\sqrt{5}}{2} \right)^n+\beta\left( \frac{3+\sqrt{5}}{2} \right)^n.


Korzystając z początkowych wartości \displaystyle a_1=1,\ a_2=2 tworzymy układ równań:


\displaystyle \left\lbrace \aligned 1&=\left( \frac{3-\sqrt{5}}{2} \right)\alpha+\left( \frac{3+\sqrt{5}}{2} \right)\beta\\ 2&=\left( \frac{7-3\sqrt{5}}{2} \right)\alpha+\left( \frac{7+3\sqrt{5}}{2} \right)\beta, \endaligned  \right.


którego rozwiązaniem są \displaystyle \alpha=\frac{5+\sqrt{5}}{10} oraz \displaystyle \beta=\frac{5-\sqrt{5}}{10} . Otrzymujemy więc postać zwartą na \displaystyle n -ty wyraz ciągu:


\displaystyle a_n=\frac{5+\sqrt{5}}{10}\left( \frac{3-\sqrt{5}}{2} \right)^n+\frac{5-\sqrt{5}}{10}\left( \frac{3+\sqrt{5}}{2} \right)^n.


Ponieważ \displaystyle c_n=b_n=a_{n+1}-a_n , to po przeliczeniach dostajemy:


\displaystyle c_n=b_n=-\frac{\sqrt{5}}{5}\left( \frac{3-\sqrt{5}}{2} \right)^n+\frac{\sqrt{5}}{5}\left( \frac{3+\sqrt{5}}{2} \right)^n.


W konsekwencji ilość wszystkich słów \displaystyle n -literowych bez podsłowa \displaystyle ab wynosi \displaystyle a_n+b_n+c_n , czyli:


\displaystyle \frac{5-3\sqrt{5}}{10}\left( \frac{3-\sqrt{5}}{2} \right)^n+\frac{5+3\sqrt{5}}{10}\left( \frac{3+\sqrt{5}}{2} \right)^n.