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

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 {\begin{aligned}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{aligned}}$

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{aligned}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{aligned}}$      (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 {\begin{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).\end{aligned}}$

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,&{\text{jeśli}}\ n=al\ {\text{dla}}\ a=0,1,2,\ldots ,k,\\0,&{\text{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 {\begin{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).\end{aligned}}$

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

$\displaystyle {\begin{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),\end{aligned}}$

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_{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 ć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_{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 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 {\begin{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),\end{aligned}}$

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 {\begin{aligned}{\mbox{ w }}\displaystyle (T)&=m+1,\\\left\vert T\right\vert &=2m+1.\end{aligned}}$

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

Rozwiązanie

Plik:Zliczanie catalan N2.svg

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

Niech

• $\displaystyle {\mathcal {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 {\mathcal {P}}_{n}\right\vert$ będzie szukaną liczbą ścieżek.

Dla ścieżki $\displaystyle P\in {\mathcal {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 {\mathcal {P}}_{n,k}\subseteq {\mathcal {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 {\mathcal {P}}_{k-1}\times {\mathcal {P}}_{n-k}$ . Zachodzi więc

$\displaystyle \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 .$

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

$\displaystyle \left\lbrace {\begin{aligned}c_{0}&=1,\\c_{n}&=c_{n-1}c_{0}+c_{n-2}c_{1}+\ldots +c_{0}c_{n-1},\quad {\text{dla}}\ n>1.\end{aligned}}\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 {\mathcal {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 {\begin{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}\end{aligned}}\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{aligned}a_{n+1}&=a_{n}+b_{n}\\b_{n+1}&=a_{n}+2b_{n}.\end{aligned}}\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{aligned}a_{1}&=1,\\a_{2}&=2,\\a_{n+2}&=3a_{n+1}-a_{n}\quad {\mbox{dla}}\ n\geq 1.\end{aligned}}\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{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 ,\end{aligned}}\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}.$