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 $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} (x) = \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ż $P_{k} (x) = \frac{1}{1 - x^{k}}$ , to podstawiając w miejsce $P_{5} (x), P_{10} (x), P_{20} (x), P_{50} (x)$ 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} (x) = \frac{1}{1 - x^{5}}, & P_{5, 10} (x) = P_{5} (x) \cdot \frac{1}{1 - x^{10}}, \\ P_{5, 10, 20} (x) = P_{5, 10} (x) \cdot \frac{1}{1 - x^{20}}, & P_{5, 10, 20, 50} (x) = P_{5, 10, 20} (x) \cdot \frac{1}{1 - x^{50}}, \end{array}

czyli:

\begin{array}{rcl} P_{5} (x) & = 1 + x^{5} P_{5} (x), \\ P_{5, 10} (x) & = P_{5} (x) + x^{10} P_{5, 10} (x), \\ P_{5, 10, 20} (x) & = P_{5, 10} (x) + x^{20} P_{5, 10, 20} (x), \\ P_{5, 10, 20, 50} (x) & = P_{5, 10, 20} (x) + x^{50} P_{5, 10, 20, 50} (x) . \end{array}

Po wprowadzeniu funkcji tworzących:

P_{5} (x) = \sum_{n = 0}^{\infty} q_{n} x^{n}, P_{5, 10} (x) = \sum_{n = 0}^{\infty} r_{n} x^{n}, P_{5, 10, 20} (x) = \sum_{n = 0}^{\infty} s_{n} x^{n}, P_{5, 10, 20, 100} (x) = \sum_{n = 0}^{\infty} p_{n} x^{n},

i podstawieniu do zależności (Uzupelnic eq zlotowka zaleznosci|) 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}{ccccccccccccccccccccc} 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 ex zlicz obs78

Niech $f_{n, k, (l)}$ 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, (l)}$ , 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

Rozwiązanie

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

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}^{\infty} f_{n, k, l} x^{n} = 1 + x^{l} + x^{2 l} + \dots + x^{l k} = \frac{1 - x^{l (k + 1)}}{1 - x^{l}} .

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^{2 k}) \cdot \dots \cdot (1 + x^{l} + \dots + x^{l k})

jest przedstawiony jako szereg $p'_{0} + p'_{1} x + p'_{2} x^{2} + p'_{3} x^{3} + \dots$ . Wtedy oczywiście $p'_{n} x^{n}$ jest sumą wszystkich jednomianów postaci $x^{j_{1}} \cdot x^{2 j_{2}} \cdot \dots \cdot x^{l j_{l}}$ , dla których $x^{n} = x^{j_{1}} \cdot x^{2 j_{2}} \cdot \dots \cdot x^{l j_{l}}$ . Współczynnik $p'_{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'_{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'_{n}$ jest $n$ -tym współczynnikiem funkcji tworzącej $\sum_{n = 0}^{\infty} f_{n, k, l} x^{n}$ .

Ćwiczenie ex zlicz tw9

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}^{\infty} f_{n, k} x^{n} = \prod_{j = 1}^{\infty} \frac{1 - x^{j (k + 1)}}{1 - x^{j}} = (1 + x + \dots + x^{k}) (1 + x^{2} + \dots + x^{2 k}) \dots .

Wskazówka

Rozwiązanie

Niech formalny nieskończony splot

\prod_{j = 1}^{\infty} \frac{1 - x^{j (k + 1)}}{1 - x^{j}} = (1 + x + \dots + x^{k}) (1 + x^{2} + \dots + x^{2 k}) \dots

zwija się do szeregu formalnego

\sum_{n = 0}^{\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^{2 l} + x^{3 l} + \dots + x^{k l})$ , gdzie $l > n$ , jedynie jednomian $1$ odgrywa rolę, gdyż jednomiany $x^{r l}$ z $r \geq 1$ dają zbyt duże potęgi. A zatem z Zadania Uzupelnic ex zlicz obs78| mamy $g_{n} = f_{n, k, (n)}$ . Ponieważ żaden składnik w rozkładzie $n = a_{0} + a_{1} + \dots + a_{s}$ nie może przekraczać $n$ , mamy $f_{n, k, (n)} = f_{n, k}$ , skąd natychmiast $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 $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 (x) = \sum_{n = 0}^{\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 (x) = \sum_{n = 0}^{\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 [obs][obs P=P1*P2*...] mamy:

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

W wyniku rozumowania analogicznego do dowodu Twierdzenia [th][Twierdzenie 9 L. Eulera] oraz Zadania Uzupelnic ex zlicz tw9| otrzymujemy:

F (x) = \prod_{n = 0}^{\infty} \frac{1}{1 - x^{2 n + 1}} = \frac{1}{1 - x} \cdot \frac{1}{1 - x^{3}} \cdot \frac{1}{1 - x^{5}} \cdot \dots .

Bazując z kolei na Zadaniu Uzupelnic ex zlicz tw9| otrzymujemy:

G (x) = \prod_{n = 0}^{\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 ex zlicz drzewa

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

Wskazówka

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ż $| T | = 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} (\binom{2 m}{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} (\binom{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} (\binom{2 n - 2}{n - 1}) .

Ćwiczenie ex movement po szachownicy Catalan

Będziemy poruszać się po punktach zbioru $ℕ^{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 ℕ^{2} : a \geq 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

{\begin{array}{rcl} c_{0} & = 1, \\ c_{n} & = c_{n - 1} c_{0} + c_{n - 2} c_{1} + \dots + c_{0} c_{n - 1} dla n > 1 . \end{array}

Rozwiązanie

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 (x) = x$ , czyli zawierających punkty ze zbioru ${(a, b) : a \geq 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 (x) = x$ na ścieżce $P$ .

[!ht]

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

Oznacza to, że odwiedzone pozycje pomiędzy punktami $(0, 0)$ oraz $(k, k)$ były poniżej prostej $g (x) = 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 (x) = x - 1$ , oraz

ścieżkę $P_{2}$ z punktu $(k, k)$ do $(n, n)$

poniżej prostej $f (x) = 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 (x) = 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

{\begin{array}{rcl} c_{0} & = 1, \\ c_{n} & = c_{n - 1} c_{0} + c_{n - 2} c_{1} + \dots + c_{0} c_{n - 1}, dla n > 1 . \end{array}

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 ex zlicz drzewa

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 $a b$ .

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 $a b$ . 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 $a w$ nie zawiera podsłowa $a b$ wtedy i tylko wtedy gdy $w$ nie zaczyna się od litery $b$ oraz $w$ nie posiada podsłowa $a b$ . 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 $a b$ 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 $a b$ , to także słowa $b v$ , oraz $c v$ nie zawierają podsłowa $a b$ . W konsekwencji otrzymujemy układ równań rekurencyjnych:

{\begin{array}{rcl} 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}

dla $n \geq 1$ oraz $a_{1} = b_{1} = c_{1} = 1$ . Ponieważ

b_{n + 1} = a_{n} + b_{n} + c_{n} = c_{n + 1}

dla

n \geq 1,

to układ ten redukuje się do:

{\begin{array}{rcl} a_{n + 1} & = a_{n} + b_{n} \\ b_{n + 1} & = a_{n} + 2 b_{n} . \end{array}

dla $n \geq 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:

{\begin{array}{rcl} a_{1} & = 1, \\ a_{2} & = 2, \\ a_{n + 2} & = 3 a_{n + 1} - a_{n} dla n \geq 1 . \end{array}

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 - 3 x + 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} = α {(\frac{3 - \sqrt{5}}{2})}^{n} + β {(\frac{3 + \sqrt{5}}{2})}^{n} .

Korzystając z początkowych wartości $a_{1} = 1, a_{2} = 2$ tworzymy układ równań:

{\begin{array}{rcl} 1 & = (\frac{3 - \sqrt{5}}{2}) α + (\frac{3 + \sqrt{5}}{2}) β \\ 2 & = (\frac{7 - 3 \sqrt{5}}{2}) α + (\frac{7 + 3 \sqrt{5}}{2}) β, \end{array}

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

a_{n} = \frac{5 + \sqrt{5}}{10} {(\frac{3 - \sqrt{5}}{2})}^{n} + \frac{5 - \sqrt{5}}{10} {(\frac{3 + \sqrt{5}}{2})}^{n} .

Ponieważ $c_{n} = b_{n} = a_{n + 1} - a_{n}$ , to po przeliczeniach dostajemy:

c_{n} = b_{n} = - \frac{\sqrt{5}}{5} {(\frac{3 - \sqrt{5}}{2})}^{n} + \frac{\sqrt{5}}{5} {(\frac{3 + \sqrt{5}}{2})}^{n} .

W konsekwencji ilość wszystkich słów $n$ -literowych bez podsłowa $a b$ wynosi $a_{n} + b_{n} + c_{n}$ , czyli:

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

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

Zliczanie obiektów

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia