Kombinatoricke pocitani DMI015

Postupujeme podle kapitoly 7 o symetrickych funkcich knihy Enumerative Combinatorics, Volume 2 od R. Stanleyho.

27. 2. 2002 Symetricke funkce stupne n nad okruhem koeficientu R, vekt. prostory sym. funkci s racionalnimi koeficienty. Rozklady cisel a terminologie okolo nich, obsahovaci a dominancni usporadani. Monomicke sym. funkce m_{lambda}. Elementarni symetricke funkce e_n a e_{lambda}. Koeficient M_{lambda, mi} ve vyjadreni e_{lambda} v monomicke bazi {m_{mi}: mi} je pocet jistych 0-1 matic, ekvivalentni formulace pomoci gen. funkci. Hlavni veta o sym. funkcich; dukaz priste. Aplikace: jsou-li a a b algebraicka cisla, je i a+b algebraicke.
6. 3. 2002 Dukaz "Hlavni vety o sym. funkcich": Neni-li mi v dominancnim usporadani mensi ci rovno lambda' (rozklad konjugovany k lambda; mi a lambda jsou rozklady n), mame M_{lambda, mi} = 0. Z toho plyne, ze i elementarni sym. funkce tvori bazi sym. funkci. Uplne sym. funkce h_n a h_{lambda}. Analogicke vysledky o koeficientech N_{lambda, mi} ve vyjadreni h_{lambda} v monomicke bazi {m_{mi}: mi}. Endomorfismus omega, jenz nahrazuje e_n uplnou sym. funkci h_n, je involuce a tudiz automorfismus. Tedy i uplne sym. funkce tvori bazi. Mocninne sym. funkce p_n a p_{lambda} . Kombinatoricky vyklad jejich koeficientu R_{lambda, mi} v monomicke bazi.
13. 3. 2002 Neni-li lambda v dominancnim usporadani mensi ci rovno mi, mame R_{lambda, mi} = 0. Tudiz je matice koeficientu R_{lambda, mi} horni trojuhelnikova a p_{lambda} tvori bazi. Rozvoje p_{lambda} pomoci generujicich funkci a identita omega(p_{lambda}) = +-p_{lambda}. Vyjadreni h_n a e_n pomoci p_{lambda}. Specializace sym. funkci. Specializace r_n redukci poctu promennych: r_n(f) = f(x_1, ..., x_n, 0, 0, ...). Tato specializace zachovava nase ctyri baze m_{lambda}, e_{lambda}, h_{lambda}, p_{lambda} a vlastnosti omega.
20. 3. 2002 q-specializace: f(1, q, q^2, ..., q^{n-1}, 0, 0, ...), f(1, q, q^2, ...), f(1, 1, ..., 1, 0, 0, ...) a jejich pusobeni na nase 4 baze (bez dukazu). Exponencialni specializace: ex(p_n) = t pro n = 1 a ex(p_n) = 0 pro n > 1. Pusobeni ex na ctyri baze a na obecnou sym. funkci f. Skalarni soucin na prostoru sym. funkci a jeho vlastnosti: symetrie, positivni definitnost, p_{lambda} je ortogonalni baze, omega je isometrie. Polostandardni Youngovy tabulky SSYT (semistandard Young tableaux) T tvaru lambda a SSYT T sikmeho tvaru (skew shape) lambda/mi. Kombinatoricka definice Schurovych funkci s_{lambda} a sikmych Schurovych funkci s_{lambda/mi} souctem pres odpovidajici SSYT.
27. 3. 2002 Schurovy funkce s_{lambda/mi} jsou symetricke. Koeficienty s_{lambda/mi} a s_{lambda} v monomicke bazi - Kostkova cisla K_{lambda/ny, mi} a K_{lambda, mi}. Cisla f^{lambda} (=K_{lambda, 1^n}) a standardni Youngovy tabulky SYT. Kombinatoricky vyklad cisel f^{lambda}. Neni-li mi v dominancnim usporadani mensi ci rovno lambda (mi a lambda jsou rozklady n), mame K_{lambda, mi} = 0. Z toho plyne, ze i Schurovy funkce s_{lambda} tvori bazi sym. funkci.

{1, 2, ..., n}

g(n, k)

Veta

g(0, k), g(1, k), g(2, k), ...

k = 0

g(n, 0) = 1

k = 1

g(n, 1) = (n - 1).g(n - 2, 1)

n >= 2, g(0, 1) = 1, g(1, 1) = 0

3. 4. 2002 Definice rekurence s konstantnimi koeficienty a rekurence s polynomialnimi koeficienty (P-rekurzivni posloupnost). Priklady (konst. rekurence): Fibonacciova cisla a pocet slov vahy n nad vazenou abecedou, jejiz pismena maji vahy 1, 2, ..., k, k. Priklady (polyn. rekurence): faktorial, Catalanova cisla, Schroederova cisla - rekurence pomoci diferencialni rovnice pro OGF (OGF je algebraicka). Exponencialni generujici funkce.
10. 4. 2002 Soucinova formule a kompozicni formule pro exponencialni generujici funkce. Priklady na exp. gen. funkce. 1. Bellova cisla: pocty B_n vsech rozkladu mnoziny [n] maji egf e^{e^x - 1}, rekurence. 2. Stirlingova cisla: pocty S(n, k) rozkladu [n] na k bloku maji egf (e^x - 1)^k/k!, rekurence. 3. Uppuluri-Carpenterova cisla: je-li U_n definovano jako rozdil mezi poctem rozkladu [n] na sudy pocet bloku a poctem rozkladu na lichy pocet bloku, maji U_n egf e^{1 - x^x}, tj. 1/B(x). 4. 2-regularni grafy: pocty g(n, 2) 2-regularnich grafu na [n] maji egf rovnou e^{-x/2 - x^2/4}/(1 - x)^{1/2}, z cehoz plyne rekurence g(n, 2) = (n - 1).g(n - 1, 2) + B(n - 1, 2).g(n - 3, 2) (kde n >= 3, g(0, 2) = 1, g(1, 2) = g(2, 2) = 0 a B( , .) je binomicky koeficient).
17. 4. 2002 Prednaska odpadla vzhledem k jarni kombinatoricke skole ve Vysoke Lipe.
24. 4. 2002 5. Souvisle grafy: Je-li V(x) egf pro pocty vsech grafu na [n] (kterych je 2^{B(n , 2)}) a S(x) je egf poctu s_n vsech souvislych grafu na [n], mame podle kompozicni formule vztah V(x) = e^{S(x)}, z cehoz se snadno odvodi rekurence pro s_n. 6. Stromy a Cayleyho formule: Je-li T(x) egf poctu t_n stromu s korenem a mnozinou vrcholu [n], plati T(x) = x.e^{T(x)}, z cehoz jsme overili Cayleyho formuli t_n = n^{n-1}. (Protoze T(x) = (x.e^{-x})^{<-1>} , staci dokazat identitu sum_1^{nekonecno} n^{n - 1}.(x.e^{-x})^n / n! = x. Po jednoduche manipulaci s levou stranou vyjde vnitrni suma pocitajici surjekce z [m-1] na [m] a vse se tedy rovna x . Analogicka suma pocita Stirlingova cisla.) D-konecne mocninne rady, definice a ekvivalence P-rekurzivity a D-konecnosti. Kazda algebraicka mocninna rada je D-konecna, dukaz priste.
1. 5. 2002 Prednaska odpadla kvuli 1. kvetnu.
8. 5. 2002 Prednaska odpadla kvuli 8. kvetnu.
15. 5. 2002 Uzaverove vlastnosti D-konecnych mocninnych rad: (i) algebraicka moc. rada je D-konecna, (ii) soucet a soucin D-konecnych moc. rad je opet D-konecna moc. rada, (iii) je-li u D-konecna a v algebraicka, je u(v) D-konecna a (iv) jsou-li u a v D-konecne, je u*v (Hadamarduv soucin) D-konecna (dukaz (iv) priste).
22. 5. 2002 Dukaz toho, ze Hadamarduv soucin dvou D-konecnych moc. rad je D-konecny. Aplikace: posloupnost Bellovych cisel neni P-rekurzivni (protoze - oznacime-li A ogf Bellovych cisel a B egf Bellovych cisel - A*e^x = B, e^x je D-konecna, ale B = e^{e^x - 1} D-konecna neni, jak se lehce vidi po derivovani, takze A nemuze byt D-konecna). Par poznamek o P-rekurzivite poctu grafu na {1, 2, ..., n} s predepsanymi stupni, dukaz uz jsme nestihli ...

kveten 2002