Tekst źródłowy strony Matematyka dyskretna 1/Ćwiczenia 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

==Zliczanie obiektów==

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

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Znajdź postać funkcji tworzącej ciągu  <math>p_0,p_1,p_2,\ldots</math> , 
gdzie  <math>p_n</math>  to liczba sum złożonych ze składników  <math>5,10,20,50</math>  
sumujących się do  <math>n</math> . 
Następnie przedstaw wartości  <math>p_n</math>  w postaci zależności rekurencyjnej 
i wylicz  <math>p_{100}</math> .
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Szukamy współczynnika  <math>p_{100}</math>  funkcji tworzącej 
<math>P_{5,10,20,50}\!\left( x \right)=\sum_{n=0}^{\infty}p_n x^n</math> . 
Korzystając z Obserwacji [[Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych#obs_8.8|8.8]] mamy:


<center><math>\begin{align} P_{5,10}\!\left( x \right)&=P_{5}\!\left( x \right)\cdot P_{10}\!\left( x \right),\\
P_{5,10,20}\!\left( x \right)&=P_{5,10}\!\left( x \right)\cdot P_{20}\!\left( x \right),\\
P_{5,10,20,50}\!\left( x \right)&=P_{5,10,20}\!\left( x \right)\cdot P_{50}\!\left( x \right)
\end{align}</math></center>


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


<center><math>\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} 
</math></center>

czyli:


{{wzor|1|1|
<math>
\begin{align}
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)
\end{align} 
</math>}}


Po wprowadzeniu funkcji tworzących:


<center><math>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
</math></center>


i podstawieniu do zależności ([[#1|1]]) otrzymamy:


<center><math>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}</math></center>


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


<center><math>\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} 
</math></center>


W konsekwencji otrzymujemy, że  <math>p_{100}=39</math> , co oznacza, że 1zł 
możemy rozmienić na  <math>39</math>  sposobów.
</div></div>

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


<center><math>\begin{align} \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).
\end{align}</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Uzasadnienie jest analogiczne do rozumowań przeprowadzonych 
w Obserwacji [[Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych#obs_8.8|8.8]].
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Uzasadnienie będzie składało się z dwu kroków:
;1. Niech  <math>f_{n,k,l}</math> będzie liczbą rozkładów liczby  <math>n</math> na sumę złożoną z co najwyżej <math>k</math>  składników  <math>l</math>. Jeśli  <math>l</math>  dzieli  <math>n</math> , to istnieje dokładnie jedna suma złożona z liczb równych  <math>l</math>  postaci  <math>n=l+l+\dots+l</math> . Ponadto liczba wystąpień składników  <math>l</math>  w podziale jest równa  <math>n/l</math> . Jeśli  <math>n</math>  nie jest podzielne przez  <math>l</math>  to nie istnieje taki rozkład. Tak więc


<center><math>f_{n,k,l}=\left\lbrace\begin{array} {rl}
1,&\text{jeśli}\ n=al\ \text{dla}\ a=0,1,2,\ldots,k,\\
0,&\text{w przeciwnym wypadku.}
\end{array} \right.</math></center>


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


<center><math>\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}</math></center>

;2. W drugim kroku pokażemy, że

<center><math>\begin{align} \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).
\end{align}</math></center>


Załóżmy, że iloczyn


<center><math>\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)
</math></center>


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


<center><math>\begin{align} n&=j_1+2j_2+\ldots+lj_l\\
&=\left( 1+\ldots+1 \right)+\left( 2+\ldots+2 \right)+\ldots+\left( l+\ldots+l \right),
\end{align}</math></center>


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

</div></div>

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


<center><math>\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</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Korzystając z [[#cw_2|ćwiczenia 2]] przeprowadź rozumowanie analogiczne 
do przedstawionego w dowodzie Twierdzenia [[Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych#tw_8.9|8.9]].
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Niech formalny nieskończony splot 


<center><math>\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
</math></center>


zwija się do szeregu formalnego


<center><math>\sum_{n=0}^{\infty}g_nx^n=g_0+g_1x+g_2x^2+g_3x^3+\ldots</math></center>


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

{{cwiczenie|4|cw 4|
Używając funkcji tworzących pokaż, że liczba podziałów liczby  <math>n</math>  składająca się z liczb nieparzystych jest równa liczbie podziałów  <math>n</math>  na różne składniki.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Wyzanacz funkcje tworzące obu ciągów i sprawdź, czy są równe. Skorzystaj ponadto z faktu, że


<center><math>1+x=\frac{1-x^2}{1-x}</math></center>


</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Niech  <math>F\!\left( x \right)=\sum_{n=0}^{\infty}f_nx^n</math>  
będzie funkcją tworzącą ciągu liczb  <math>f_n</math>  podziałów liczby  <math>n</math>  
na składniki nieparzyste, 
a  <math>G\!\left( x \right)=\sum_{n=0}^{\infty}g_nx^n</math>  
będzie funkcją tworzącą ciągu liczb  <math>g_n</math>  podziałów liczby  <math>n</math>  
na  składniki parami różne. 
Korzystając z Obserwacji [[Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych#obs_8.8|8.8]] mamy:


<center><math>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}}</math></center>


W wyniku rozumowania analogicznego do dowodu 
Twierdzenia [[Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych#tw_8.9|8.9]] oraz [[#cw_3|ćwiczenia 3]] otrzymujemy:


<center><math>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</math></center>


Bazując z kolei na [[#cw_3|ćwiczeniu 3]] otrzymujemy:


<center><math>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</math>,</center>


co wraz z


<center><math>1+y=\frac{1-y^2}{1-y}
</math></center>


daje


<center><math>\begin{align} 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),
\end{align}</math></center>


co kończy dowód.
</div></div>

{{cwiczenie|5|cw 5|
Policz ile jest drzew binarnych o <math>n</math> węzłach, a ile o szerokości nie większej niż <math>n</math> .

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Skorzystaj z Obserwacji 7 wykładu 2 oraz 
z Twierdzenia opisującego liczby Catalana.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
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ż <math>\left\vert T \right\vert=2\cdot</math>  w <math>(T)-1</math>, 
to dla drzewa  <math>T</math>  o  <math>m</math>  węzłach wewnętrznych mamy:


<center><math>\begin{align}  \mbox{ w } (T)&=m+1, \\
\left\vert T \right\vert&=2m+1.
\end{align}</math></center>


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


<center><math>\frac{2}{n+1}{n-1\choose \left( n-1 \right)/2}</math></center>


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


<center><math>\frac{1}{n}{2n-2\choose n-1}</math></center>


</div></div>

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

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Pokaż, że liczba  <math>c_n</math>  przejść z punktu  <math>\left( 0,0 \right)</math>  do punktu  <math>\left( n,n \right)</math>  
zgodnie z zasadami postawionymi w zadaniu spełnia


<center><math>\left\lbrace
\begin{align}
c_0&=1,\\
c_n&=c_{n-1}c_0 + c_{n-2}c_1 + \ldots + c_0c_{n-1}\quad\mbox{dla}\ n>1.
\end{align} 
\right.</math></center>


</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

[[File:Zliczanie catalan N2.svg|250x250px|thumb|right|Przykładowa ścieżka z punktu  <math>\left( 0,0 \right)</math>  do punktu  <math>\left( n,n \right)=\left( 7,7 \right)</math>]]

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

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

Oznacza to, że odwiedzone pozycje pomiędzy punktami <math>\left( 0,0 \right)</math>  oraz  <math>\left( k,k \right)</math>  były poniżej prostej  <math>g\!\left( x \right)=x-1</math> . 
Ścieżkę  <math>P</math>  można więc rozłożyć na dwie ścieżki:
* ścieżkę  <math>P_1</math>  z punktu  <math>\left( 1,0 \right)</math>  do  <math>\left( k,k-1 \right)</math> poniżej prostej  <math>g\!\left( x \right)=x-1</math> , oraz
* ścieżkę  <math>P_2</math>  z punktu  <math>\left( k,k \right)</math>  do  <math>\left( n,n \right)</math> poniżej prostej  <math>f\!\left( x \right)=x</math> .

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


<center><math>\left\vert \mathcal{P}_{n,k} \right\vert=\left\vert \mathcal{P}_{k-1} \right\vert\cdot\left\vert \mathcal{P}_{n-k} \right\vert</math></center>


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


<center><math>\left\lbrace
\begin{align}
c_0&=1,\\
c_n&=c_{n-1}c_0 + c_{n-2}c_1 + \ldots + c_0c_{n-1},\quad\text{dla}\ n>1.
\end{align} 
\right.</math></center>


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


<center><math>\left\vert \mathcal{P}_n \right\vert=c_n=\frac{1}{n+1}{2n \choose n}</math></center>


</div></div>

{{cwiczenie|7|cw 7|
Policz ile jest słów złożonych z liter  <math>a,b,c</math>  o długości  <math>n</math> , w których 
nie występuje podsłowo  <math>ab</math> .

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Niech  <math>a_n, b_n, c_n</math>   będzie liczbą  <math>n</math> -literowych słów zaczynających się 
odpowiednio od litery  <math>a, b</math>  lub  <math>c</math>  i nie zawierających podsłowa  <math>ab</math> .
Znajdź zależność rekurencyjną pomiędzy liczbami  <math>a_n, b_n, c_n</math> , 
a następnie rozwiąż ją używając funkcji tworzących.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Jeśli  <math>w</math>  jest słowem  <math>n</math> -literowym, to słowo  <math>aw</math>  
nie zawiera podsłowa  <math>ab</math>  wtedy i tylko wtedy gdy 
<math>w</math>  nie zaczyna się od litery  <math>b</math>  oraz  <math>w</math>  nie posiada podsłowa  <math>ab</math> . 
A zatem  <math>a_{n+1}</math>  
to suma liczby  <math>n</math> -literowych słów zaczynających się od  <math>a</math>  bądź  <math>c</math> 
i nie zawierających słowa  <math>ab</math>  
i  mających  <math>n</math>  liter. Otrzymujemy więc, że  <math>a_{n+1}=a_n+c_n</math> . 
Z kolei jeśli  <math>n</math> -literowe słowo  <math>v</math>  nie zawiera podsłowa  <math>ab</math> , 
to także słowa  <math>bv</math> , oraz  <math>cv</math>  nie zawierają podsłowa  <math>ab</math> . 
W konsekwencji otrzymujemy układ równań rekurencyjnych:


<center><math>\left\lbrace
\begin{align}
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
\end{align} 
\right.</math></center>


dla  <math>n\geq1</math>  oraz   <math>a_1=b_1=c_1=1</math> . 
Ponieważ


<center><math>b_{n+1} = a_n+b_n+c_n= c_{n+1}\quad</math> dla <math>\ n\geq1</math>,</center>


to układ ten redukuje się do:


<center><math>\left\lbrace
\begin{align}
a_{n+1}&=a_n+b_n\\
b_{n+1}&=a_n+2b_n.
\end{align} 
\right.</math></center>


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


<center><math>a_{n+2}-a_{n+1}=a_n+2\left( a_{n+1}-a_n \right)</math></center>


Po uproszczeniu oraz wyliczeniu   <math>a_2</math>  dostajemy:


<center><math>\left\lbrace
\begin{align}
a_1&=1,\\
a_2&=2,\\
a_{n+2}&=3a_{n+1}-a_n\quad\mbox{dla}\ n\geq1.
\end{align} 
\right.</math></center>


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


<center><math>1-3x+x^2=\left( 1-\frac{3-\sqrt{5}}{2}x \right)\left( 1-\frac{3+\sqrt{5}}{2}x \right)</math>,</center>


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


<center><math>a_n=\alpha\left( \frac{3-\sqrt{5}}{2} \right)^n+\beta\left( \frac{3+\sqrt{5}}{2} \right)^n</math></center>


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


<center><math>\left\lbrace
\begin{align}
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,
\end{align} 
\right.</math></center>


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


<center><math>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</math></center>


Ponieważ  <math>c_n=b_n=a_{n+1}-a_n</math> , to po przeliczeniach dostajemy:


<center><math>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</math></center>


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


<center><math>\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</math></center>


</div></div>