Zaawansowane metody sumowania

Rozwi _{}azanie I

Lemat Liczba ścieżek długości 2k zaczynaj _{}acych si_{}e i kończ _{}acych w 0 jest równa liczbie ścieżek długości 2k zaczynaj _{}acych si_{}e w 0 i niedotykaj _{}acych potem 0 ponownie.

Dowód Lematu Oczywiście ścieżek zaczynaj _{}acych si_{}e i kończ _{}acych w 0 jest \binom{2k}{k}. Z drugiej strony ścieżki po drugiej stronie równości to odpowiednio:

(a) cały czas dodatnie oprócz pierwszego w_{}ezła

(b) cały czas ujemne oprócz pierwszego w_{}ezła

Przez symetri_{}e liczby ścieżek w (a) i (b) s _{}a równe. Oznaczmy je przez A. Policzmy A - s _{}a to ścieżki zawsze dodatnie. Zatem pierwszym ruchem musi być pójście w gór_{}e. Dalej wszystkich ścieżek kończ _{}acych si_{}e na poziomach 0,2,4 itd. jest:

\binom{2k − 1}{k − 1} + \binom{2k − 1}{k − 2} + \binom{2k − 1}{k − 3} + … + \binom{2k − 1}{0}

Bo wybieramy co najwyżej k − 1 pójść w dół. Jednocześnie z zasady odbicia wśród nich ścieżek które dotykaj _{}a 0 jest tyle co ścieżek kończ _{}acych si_{}e tam gdzie trzeba, ale zaczynaj _{}acych si_{}e w −1, czyli:

\binom{2k − 1}{k − 2} + \binom{2k − 1}{k − 3} + \binom{2k − 1}{k − 4} + … + \binom{2k − 1}{0}

Gdyż wybieram co najwyżej k − 2 pójść w dół. Zatem A musi być różnic _{}a tych dwóch liczb, czyli A = \binom{2k−1}{k−1}. Zatem w sumie po prawej stronie równości z tezy mamy

2A = 2\binom{2k − 1}{k − 1} = \binom{2k − 1}{k − 1} + \binom{2k − 1}{k} = \binom{2k}{k}

Co jest tez _{}a.

Dowód zadania Zauważmy, że ∑ _{i+j=n} \binom{2i}{i} \binom{2j}{j} to przeliczenie wszystkich ścieżek długości 2n o pocz _{}atku i końcu w zerze oraz wyróżnionym punktem z zerem. 4^{n} = 2^{2n} jest zaś liczb _{}a wszystkich ścieżek. Odejmijmy wi_{}ec od obu stron te, w których punkt wyróżniony jest ostatnim zerem (czyli jest na końcu). Musimy teraz pokazać, że liczba ścieżek o pocz _{}atku i końcu w zerze z wyróżnionym niekońcowym zerem jest równa liczbie wszytskich ścieżek niekończ _{}acych si_{}e w zerze. Weźmy zatem t_{}e ścieżk_{}e z wyróżnionym zerem i zamieńmy fragment od wyróżnionego zera do końca za pomoc _{}a bijekcji któr _{}a dostarcza nam lemat. Wówczas uzyskamy ścieżk_{}e niekończ _{}ac _{}a si_{}e w 0, z której da si_{}e odkodować jednoznacznie wejściow _{}a ścieżk_{}e wraz z wyróżnieniem, bo wyróżnione 0 to ostatnie w nowej ścieżce. Zatem skonstruowaliśmy szukan _{}a bijekcj_{}e.

Rozwi _{}azanie II Na pocz _{}atku b_{}edziemy używali kilku faktów. Liczby Catalana zdefiniowane s _{}a rekurencyjnie poprzez:

c_{0} = 1, c_{n} = ∑_{i=0}^{n−1} c_{i}c_{n−1−i}

Można wyprowadzić, (co np. jest w �Matematyce konkretnej”), że zachodzi c_{n} = \frac{\binom{2n}{n}}{n+1}. Rozpatrzmy enumerator liczb Catalana C(z) = ∑ _{i=0}^{∞} c_{i}z^{i} dla z zespolonego w otoczeniu 0 (liczby Catalna s _{}a ograniczone z góry przez 4^{n}, wi_{}ec w otoczeniu 0 szereg jest bezwzgl_{}ednie zbieżny). Z wzoru rekurencyjnego mamy, że splot tego szeregu z samym sob _{}a jest nim samym przesuni_{}etym o jedno miejsce w lewo, wi_{}ec C(z) spełnia równość dla z ≠ 0:

C(z)C(z) = \frac{C(z) − 1}{z}

Wi_{}ec przeliczaj _{}ac:

z(C(z))^{2} − C(z) + 1 = 0

Rozwi _{}azuj _{}ac równanie kwadratowe:

C(z) = \frac{1 − \sqrt{1 − 4z}}{2z}

Gdzie wybrany jest minus, C(z) było ci _{}agłe w zerze. Zatem

\frac{1 − \sqrt{1 − 4z}}{2z} = ∑_{i=0}^{∞} \frac{\binom{2i}{i}}{i + 1} z^{i} =

St _{}ad:

\frac{1 − \sqrt{1 − 4z}}{2} = ∑_{i=0}^{∞} \frac{\binom{2i}{i}}{i + 1} z^{i+1}

Obustronnie różniczkuj _{}ac w obszarze zbieżności:

(\frac{1 − \sqrt{1 − 4z}}{2} )′= ∑_{i=0}^{∞} \binom{2i}{i} z^{i}

\frac{1}{\sqrt{1 − 4z}} = ∑_{i=0}^{∞} \binom{2i}{i} z^{i}

Zauważmy że teraz jeśli przez l_{n} oznaczymy lew _{}a stron_{}e tożsamości zadania, to enumeratorem L(z) ci _{}agu l_{n} b_{}edzie splot szeregu po lewej stronie tej równości z samym sob _{}a. St _{}ad:

\frac{1}{1 − 4z} = L(z)

∑_{i=0}^{∞} 4^{i}z^{i} = L(z)

St _{}ad mamy, że l_{n} = 4^{n}, czyli tez_{}e.

Plan wykładu

1 Liczby Catalana i ich interpretacje kombinatoryczne:

(a) Liczba poprawnych wyrażeń nawiasowych długości 2n.

(b) Liczba n wierzchołkowych niepełnych drzew binarnych (bijekcja z b - w nawiasie lewy syn, potem prawy)

(c) Liczba różnych triangulacji otykietowanego n-k _{}ata foremnego.

(d) Liczba nieujemnych ścieżek długości 2n zaczynaj _{}acych si_{}e i kończ _{}acych w 0.

(e) Wzór rekurencyjny: C_{n} = ∑ _{i=0} n − 1 C_{i}C_{n−1−i} 2 Dowód zasad _{}a odbicia, że C_{n} = \frac{\binom{2n}{n}}{n+1}. 3 Pokazanie rozwi _{}azania zadania jako zaawansowanej metody odbicia. 4 Pokazanie funkcji tworz _{}acych na przykładzie ci _{}agu Fibonacciego. 5 Pokazanie, że ∑ _{i=0}^{n} 2^{i} = 2^{n+1} − 1 przez splot \frac{1}{1−z} i \frac{1}{1−2z} . 6 Pokazanie rozwi _{}azania zadania.

4. F (z) = ∑ _{i=0}^{∞} f_{n}z^{n}. Wi_{}ec z^{2}F (z) + zF (z) = F (z) − z. Czyli F (z) = \frac{z}{1−z−z^{2}} . Pierwistki tego na dole to \frac{1±\sqrt{5}}{2} i sprawdzaj _{}ac \frac{z}{1−z−z^{2}} = \frac{A}{1−za_{1}} + \frac{B}{1−za_{2}} dostajemy A i B. Dalej rozwijamy 1 − za_{i} i mamy pro. (A + B = 0, Aa_{2} + Ba_{1} = −1, czyli A(a_{2} − a_{1}) = −1, czyli A = \frac{1}{\sqrt{5}})

5. Oczywiście ∑ _{i=0}^{n} 2^{i} to współczynnik przy z^{n} w \frac{1}{(1−z)(1−2z)} . Rozkładaj _{}ac na ułamki proste \frac{A}{1−z} + \frac{B}{1−2z} mamy A + B = 1 oraz −2A − B = 0, czyli B = 2 i A = −1. St _{}ad −\frac{1}{1−z} + \frac{2}{1−2z} i współczynnik z pierwszego wyrazu to −1 a z drugiego to 2.