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 $p_0,p_1,p_2,\dots$ , gdzie $p_n$ to liczba sum złożonych ze składników $5,10,20,50$ sumujących się do $n$ . Następnie przedstaw wartości $p_n$ w postaci zależności rekurencyjnej i wylicz $p_{100}$ .

Rozwiązanie

Szukamy współczynnika $p_{100}$ funkcji tworzącej $P_{5,10,20,50}\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{p}_n{x}^n$ . Korzystając z Obserwacji 8.8 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ż $P_k\left(x\right)=\frac{1}{1-x^k}$ , to podstawiając w miejsce $P_5\left(x\right),P_{10}\left(x\right),P_{20}\left(x\right),P_{50}\left(x\right)$ odpowiednio $\frac{1}{1-x^5},\frac{1}{1-x^{10}},\frac{1}{1-x^{20}},\frac{1}{1-x^{50}}$ dostajemy:

$\begin{array}{lcl}{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:

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

$P_5\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{q}_n{x}^n,P_{5,10}\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{r}_n{x}^n,P_{5,10,20}\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{s}_n{x}^n,P_{5,10,20,100}\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{p}_n{x}^n,$

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

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

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

$\begin{array}{ccccccccccc}n& 10& 20& 30& 40& 50& 60& 70& 80& 90& 100\\ HLINE\; TBD{q}_n& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1\\ r_n& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ s_n& 1& 2& 4& 6& 9& 12& 16& 20& 25& 30\\ p_n& 1& 2& 4& 6& 9& 13& 18& 24& 31& 39\end{array}$

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

Ćwiczenie 2

Niech $f_{n,k,\left(l\right)}$ będzie liczbą podziałów liczby $n$ na sumę składników nie większych od $l$ , przy czym składników o tej samej wartości jest co najwyżej $k$ . Pokaż, że dla ustalonego $k$ funkcja tworząca ciągu $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 8.8.

Rozwiązanie

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

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

$\sum _{n=0}^{\mathrm{\infty }}{f}_{n,k,l}{x}^n=1+x^l+x^{2l}+\dots +x^{lk}=\frac{1-x^{l(k+1)}}{1-x^l}.$

2. 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

$(1+x+\dots +x^k)\cdot (1+x^2+\dots +x^{2k})\cdot \dots \cdot (1+x^l+\dots +x^{lk})$

jest przedstawiony jako szereg $p{\text{'}}_0+p{\text{'}}_{1}x+p{\text{'}}_2{x}^2+p{\text{'}}_3{x}^3+\dots$ . Wtedy oczywiście $p{\text{'}}_n{x}^n$ jest sumą wszystkich jednomianów postaci $x^{j_1}\cdot x^{2j_2}\cdot \dots \cdot x^{l{j}_l}$ , dla których $x^n=x^{j_1}\cdot x^{2j_2}\cdot \dots \cdot x^{l{j}_l}$ . Współczynnik $p{\text{'}}_n$ więc jest liczbą wszystkich ciągów $j_1,\dots ,j_l$ takich, że $j_s=0,1,2,\dots ,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. $p{\text{'}}_n$ jest liczbą rozkładów liczby $n$ na sumy o składnikach ze zbioru $\{1,2,\dots ,n\}$ , przy czym składników o tej samej wartości jest nie więcej niż $k$ , a zatem $p{\text{'}}_n$ jest $n$ -tym współczynnikiem funkcji tworzącej $\sum _{n=0}^{\mathrm{\infty }}{f}_{n,k,l}{x}^n$ .

Ćwiczenie 3

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

$\sum _{n=0}^{\mathrm{\infty }}{f}_{n,k}{x}^n=\prod _{j=1}^{\mathrm{\infty }}\frac{1-x^{j(k+1)}}{1-x^j}=(1+x+\dots +x^k)(1+x^2+\dots +x^{2k})\dots .$

Wskazówka

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

Rozwiązanie

Niech formalny nieskończony splot

$\prod _{j=1}^{\mathrm{\infty }}\frac{1-x^{j(k+1)}}{1-x^j}=(1+x+\dots +x^k)(1+x^2+\dots +x^{2k})\dots$

zwija się do szeregu formalnego

$\sum _{n=0}^{\mathrm{\infty }}{g}_n{x}^n=g_0+g_{1}x+g_2{x}^2+g_3{x}^3+\dots .$

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

Ćwiczenie 4

Używając funkcji tworzących pokaż, że liczba podziałów liczby $n$ składająca się z liczb nieparzystych jest równa liczbie podziałów $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

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

Rozwiązanie

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

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

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

$F\left(x\right)=\prod _{n=0}^{\mathrm{\infty }}\frac{1}{1-x^{2n+1}}=\frac{1}{1-x}\cdot \frac{1}{1-x^3}\cdot \frac{1}{1-x^5}\cdot \dots .$

Bazując z kolei na ćwiczeniu 3 otrzymujemy:

$G\left(x\right)=\prod _{n=0}^{\mathrm{\infty }}(1+x^n)=(1+x)\cdot (1+x^2)\cdot (1+x^3)\cdot \dots ,$

co wraz z

$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 5

Policz ile jest drzew binarnych o $n$ węzłach, a ile o szerokości nie większej niż $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ż $\left|T\right|=2\cdot$ w $(T)-1$, to dla drzewa $T$ o $m$ węzłach wewnętrznych mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \textrm{ w } \displaystyle (T)&=m+1, \\ \left\vert T \right\vert&=2m+1. \endaligned}

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

$\frac{2}{n+1}(\genfrac{}{}{0ex}{}{n-1}{(n-1)/2}).$

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

$\frac{1}{n}(\genfrac{}{}{0ex}{}{2n-2}{n-1}).$

Ćwiczenie 6

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

Wskazówka

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

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

<div.thumbcaption>Przykładowa ścieżka z punktu $(0,0)$ do punktu $(n,n)=(7,7)$

Niech

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_n } będzie rodziną ścieżek z punktu $(0,0)$ do punktu $(n,n)$ przechodzących poniżej prostej opisanej funkcją $f\left(x\right)=x$, czyli zawierających punkty ze zbioru $\{(a,b):a\ge b\}$ ,
• Parser nie mógł rozpoznać (błąd składni): {\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ć (błąd składni): {\displaystyle \displaystyle P\in\mathscr{P}_n } niech $(k,k)$ będzie pierwszym punktem prostej $f\left(x\right)=x$ na ścieżce $P$ .

Oznacza to, że odwiedzone pozycje pomiędzy punktami $(0,0)$ oraz $(k,k)$ były poniżej prostej $g\left(x\right)=x-1$ . Ścieżkę $P$ można więc rozłożyć na dwie ścieżki:

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

Z kolei para $(P_1,P_2)$ jednoznacznie wyznacza ścieżkę $P$ . Rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n,k}\subseteq\mathscr{P}_n } ścieżek, na których punkt $(k,k)$ jest pierwszym spotkaniem z prostą $f\left(x\right)=x$ jest więc równoliczna z produktem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{k-1}\times\mathscr{P}_{n-k} } . Zachodzi więc

Parser nie mógł rozpoznać (błąd składni): {\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 $(0,0)$ do $(n,n)$ jest rozłączną sumą Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_n=\mathscr{P}_{n,1}\cup\mathscr{P}_{n,2}\cup\ldots\cup\mathscr{P}_{n,n} } , to

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $c_n$ przedstawia kolejne liczby Catalana, czyli szukana liczba ścieżek z $(0,0)$ do $(n,n)$ , to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $a,b,c$ o długości $n$ , w których nie występuje podsłowo $ab$ .

Wskazówka

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

Rozwiązanie

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $n\ge 1$ oraz $a_1=b_1=c_1=1$ . Ponieważ

$b_{n+1}=a_n+b_n+c_n=c_{n+1}$ dla $n\ge 1,$

to układ ten redukuje się do:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \left\lbrace \aligned a_{n+1}&=a_n+b_n\\ b_{n+1}&=a_n+2b_n. \endaligned \right. }

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

$a_{n+2}-a_{n+1}=a_n+2(a_{n+1}-a_n).$

Po uproszczeniu oraz wyliczeniu $a_2$ dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $k=2$ przedstawionej na wykładzie. Rozkładamy na iloczyn wielomian:

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

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

$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 $a_1=1,a_2=2$ tworzymy układ równań:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ą $\alpha =\frac{5+\sqrt{5}}{10}$ oraz $\beta =\frac{5-\sqrt{5}}{10}$ . Otrzymujemy więc postać zwartą na $n$ -ty wyraz ciągu:

$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ż $c_n=b_n=a_{n+1}-a_n$ , to po przeliczeniach dostajemy:

$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 $n$ -literowych bez podsłowa $ab$ wynosi $a_n+b_n+c_n$ , czyli:

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