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

Zliczanie obiektów

Ćwiczenie ex zlicz zlotowka

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 [obs][obs P=P1*P2*...] mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 {\begin{array}{r c l}P_{5}\!\left(x\right)&=1+x^{5}P_{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{array}}$

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 (Uzupelnic eq zlotowka zaleznosci|) 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 ex zlicz obs78

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 [obs][Obserwacja 7], [obs][obs P=P1*P2*...].

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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}}}.$

1. W drugim kroku pokażemy, że

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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'_{1}x+p'_{2}x^{2}+p'_{3}x^{3}+\ldots$ . Wtedy oczywiście $\displaystyle p'_{n}x^{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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 ex zlicz tw9

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 Zadania Uzupelnic ex zlicz obs78| przeprowadź rozumowanie analogiczne do przedstawionego dowodzie Twierdzenia [th][Twierdzenie 9 L. Eulera].

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_{n}x^{n}=g_{0}+g_{1}x+g_{2}x^{2}+g_{3}x^{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\geq 1$ dają zbyt duże potęgi. A zatem z Zadania Uzupelnic ex zlicz obs78| 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 ex zlicz sumy

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_{n}x^{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_{n}x^{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 [obs][obs P=P1*P2*...] 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 [th][Twierdzenie 9 L. Eulera] oraz Zadania Uzupelnic ex zlicz tw9| 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 Zadaniu Uzupelnic ex zlicz tw9| 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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 ex zlicz drzewa

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned } w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 ex movement po szachownicy Catalan

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 {\begin{array}{r c l}c_{0}&=1,\\c_{n}&=c_{n-1}c_{0}+c_{n-2}c_{1}+\ldots +c_{0}c_{n-1}\quad {\textrm {dla}}\ n>1.\end{array}}\right.$

Rozwiązanie

Niech

• Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \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$ ,

• Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \displaystyle c_n=\left\vert \mathscr{P}_n \right\vert } będzie szukaną liczbą ścieżek.

Dla ścieżki Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \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$ .

[!ht]

{zliczanie_catalan_N2} {Przykładowa ścieżka z punktu $\displaystyle \left(0,0\right)$ do punktu $\displaystyle \left(n,n\right)=\left(7,7\right)$ . [Rysunek z pliku: zliczaniecatalanN2.eps]}

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 Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \displaystyle \mathscr{P}_{k-1}\times\mathscr{P}_{n-k} } . Zachodzi więc

Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \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ą Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \displaystyle \mathscr{P}_n=\mathscr{P}_{n,1}\cup\mathscr{P}_{n,2}\cup\ldots\cup\mathscr{P}_{n,n} } , to

$\displaystyle \left\lbrace {\begin{array}{r c l}c_{0}&=1,\\c_{n}&=c_{n-1}c_{0}+c_{n-2}c_{1}+\ldots +c_{0}c_{n-1},\quad {\textrm {dla}}\ n>1.\end{array}}\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

Parser nie mógł rozpoznać (nieznana funkcja „\mathscr”): {\displaystyle \displaystyle \left\vert \mathscr{P}_n \right\vert=c_n=\frac{1}{n+1}{2n \choose n}. }

Ćwiczenie ex zlicz drzewa

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 {\begin{array}{r c l}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{array}}\right.$

dla $\displaystyle n\geq 1$ 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\geq 1,$

to układ ten redukuje się do:

$\displaystyle \left\lbrace {\begin{array}{r c l}a_{n+1}&=a_{n}+b_{n}\\b_{n+1}&=a_{n}+2b_{n}.\end{array}}\right.$

dla $\displaystyle n\geq 1$ . 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 {\begin{array}{r c l}a_{1}&=1,\\a_{2}&=2,\\a_{n+2}&=3a_{n+1}-a_{n}\quad {\textrm {dla}}\ n\geq 1.\end{array}}\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 {\begin{array}{r c l}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{array}}\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}.$