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} (x) = \sum_{n = 0}^{\infty} p_{n} x^{n}$ . Korzystając z Obserwacji 8.8 mamy:

\begin{aligned} P_{5, 10} (x) & = P_{5} (x) \cdot P_{10} (x), \\ P_{5, 10, 20} (x) & = P_{5, 10} (x) \cdot P_{20} (x), \\ P_{5, 10, 20, 50} (x) & = P_{5, 10, 20} (x) \cdot P_{50} (x) \end{aligned}

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{aligned} 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{aligned}$ (1)

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 (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}{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 2

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

\begin{aligned} \sum_{n = 0}^{\infty} f_{n, k, (l)} x^{n} & = \prod_{j = 1}^{l} \frac{1 - x^{j (k + 1)}}{1 - x^{j}} \\ = (1 + x + \dots + x^{k}) \cdot \dots \cdot (1 + x^{l} + \dots + x^{l k}) . \end{aligned}

Wskazówka

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

f_{n, k, l} = {\begin{aligned} 1, & jeśli n = a l dla a = 0, 1, 2, \dots, k, \\ 0, & w przeciwnym wypadku. \end{aligned}

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}}

2. W drugim kroku pokażemy, że

\begin{aligned} \sum_{n = 0}^{\infty} f_{n, k, (l)} x^{n} & = \prod_{j = 1}^{l} \frac{1 - x^{j (k + 1)}}{1 - x^{j}} \\ = (1 + x + \dots + x^{k}) \cdot \dots \cdot (1 + x^{l} + \dots + x^{l k}) . \end{aligned}

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

\begin{aligned} n & = j_{1} + 2 j_{2} + \dots + l j_{l} \\ = (1 + \dots + 1) + (2 + \dots + 2) + \dots + (l + \dots + l), \end{aligned}

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 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}^{\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 ćwiczenia 2 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 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 (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 8.8 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 8.9 oraz ćwiczenia 3 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 ćwiczeniu 3 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

\begin{aligned} G (x) & = (1 + x) \cdot (1 + x^{2}) \cdot (1 + x^{3}) \cdot (1 + x^{4}) \cdot \dots \\ = \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 \dots \\ = \frac{1}{1 - x} \cdot \frac{1}{1 - x^{3}} \cdot \frac{1}{1 - x^{5}} \cdot \frac{1}{1 - x^{7}} \cdot \dots \\ = F (x), \end{aligned}

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

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:

\begin{aligned} w (T) & = m + 1, \\ | T | & = 2 m + 1 . \end{aligned}

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 6

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{aligned} 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{aligned}

Rozwiązanie

Plik:Zliczanie catalan N2.svg

Przykładowa ścieżka z punktu

(0, 0)

do punktu

(n, n) = (7, 7)

Niech

$𝒫_{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}$ ,
$c_{n} = | 𝒫_{n} |$ będzie szukaną liczbą ścieżek.

Dla ścieżki $P \in 𝒫_{n}$ niech $(k, k)$ będzie pierwszym punktem prostej $f (x) = x$ na ścieżce $P$ .

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 $𝒫_{n, k} \subseteq 𝒫_{n}$ ścieżek, na których punkt $(k, k)$ jest pierwszym spotkaniem z prostą $f (x) = x$ jest więc równoliczna z produktem $𝒫_{k - 1} \times 𝒫_{n - k}$ . Zachodzi więc

| 𝒫_{n, k} | = | 𝒫_{k - 1} | \cdot | 𝒫_{n - k} |

Ponieważ zbiór ścieżek z $(0, 0)$ do $(n, n)$ jest rozłączną sumą $𝒫_{n} = 𝒫_{n, 1} \cup 𝒫_{n, 2} \cup \dots \cup 𝒫_{n, n}$ , to

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

A zatem ciąg $c_{n}$ przedstawia kolejne liczby Catalana, czyli szukana liczba ścieżek z $(0, 0)$ do $(n, n)$ , to

| 𝒫_{n} | = c_{n} = \frac{1}{n + 1} (\binom{2 n}{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 $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{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}

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{aligned} a_{n + 1} & = a_{n} + b_{n} \\ b_{n + 1} & = a_{n} + 2 b_{n} . \end{aligned}

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{aligned} a_{1} & = 1, \\ a_{2} & = 2, \\ a_{n + 2} & = 3 a_{n + 1} - a_{n} dla n \geq 1 . \end{aligned}

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{aligned} 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{aligned}

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