Kombinatoricke pocitani DMI015

• 2.3.2000: KAP 1. Co to je enumerativni kombinatorika? Par prikladu. Generujici funkce (GF) a operace s nimi. Zkuste si udelat priklad 4a a 4b (k 1. kapitole).

• 9.3.2000: Vzorecek e^x = (1-x^1)^{-mi(1)/1}.(1-x^2)^{-mi(2)/2}. ... , kde mi(n) je Moebiova funkce. Dva dukazy toho, ze pocet k tic (X_1, ..., X_k), kde X_i jsou vesmes disjunktni podmnoziny [n] = {1, 2,. .., n}, je prave (2^k-1)^n. Kompozice a slabe kompozice cisla n a jejich pocty. Multimnoziny.

• 16.3.2000: Pocet multipodmnozin [n] mohutnosti k je B(n+k-1, k)=(-1)^k.B(-n, k), kde B(a, b) je bin. koeficient. Multinomicky koeficient. Permutace. Pocet permutaci s danym cyklovym typem. Je-li c(n, k) pocet n-permutaci s k cykly, pak  c(n, 0)x^0 + c(n, 1)x^1 + ... + c(n, n)x^n = x(x+1)...(x+n-1). Je-li i(n, k) pocet n-permutaci s k inverzemi, pak i(n, 0)q^0 + i(n, 1)q^1 + ... = 1.(1 + q^1).(1 + q^1 + q^2). ... .(1 + q^1 + q^2 + ... + q^{n-1}). Zkuste se podivat na priklady 7, 8a a 8b.

• 23.3.2000: Posledni identita s inverzemi je q-zobecnenim triviality sum_{pi} 1 = n!, kde scitame pres vsechny n-permutace pi. Poklesy v permutacich. q-binomicke a q-multinomicke koeficienty. q-zobecneni triviality sum_{pi} 1 = M(n; a_1, ..., a_m), kde scitame pres vsechny permutace multimnoziny { 1^{a_1}, 2^{a_2}, ..., m^{a_m} }, n=a_1+...+a_m, a M(...) je multinomicky koeficient. q-binomicky koeficient B(n,k)_q udava pocet k-rozmernych podprostoru n-rozmerneho vektoroveho prostoru nad konecnym telesem s q prvky. Tabulka tuctu vysledku v ulohach o rozdeleni micu do krabic.

• 30.3.2000: Pocet zpusobu, jak umistit do x rozlisitelnych krabic n rozlisitelnych micu tak, aby v kazde krabici byl alespon jeden mic, je x!.S(n,x), kde S(n,k) je Stirlingovo cislo 2. druhu (=pocet rozkladu [n] na k bloku). Bellova cisla B(n). Sest formulek pro Stirlingova a Bellova cisla. Jsou-li A={1, x, x^2, x^3, ...} a B={1, x, x(x-1), x(x-1)(x-2), ...} baze vektoroveho prostoru C[x], jsou matice (S(n,k)) a (s(n,k)) (s(n,k) jsou St. cisla 1. druhu) maticemi prechodu od B k A a naopak. Zkuste si udelat priklady 29 a 17a.

• 6.4.2000: Vysledky pro zbyle ulohy z tuctu uloh o rozmisteni micu v krabicich. KAP 2. Princip inkluze a exkluze, ruzne formulace: mnozinova, vekt. prostor, vlastnosti. "Derangement problem" neboli satnarka: Pocet n-permutaci bez pevneho bodu je D(n) = n!.(1/0!-1/1!+1/2!-...+(-1)^n/n!). Permutace s danymi poklesy: Pro danou podmnozinu S = {s_1, s_2, ..., s_k}_< mnoziny [n-1] je pocet tech n-permutaci, ktere maji mnozinu poklesu S, roven n!.det( 1/(s_{j+1}-s_i)! ), kde i, j probihaji mnozinu {0, 1, ..., k} (pod hlavni diagonalou je diagonala jednicek a pod ni jsou nuly, klademe s_0=0 a s_{k+1}=n).

• 13.4.2000: Jeste k dukazu posledniho tvrzeni. Odvozeni jeho q-zobecneni. Permutace se zakazanymi pozicemi (zobecneni problemu satnarky): Je-li B podmnozina [n] x [n] a r_k je pocet rozmisteni k nenapadajicich se vezi v B, je pocet rozmisteni n nenapadajicich se vezi v [n] x [n], pricemz zadna vez neni v B, roven sum_k (-1)^k . r_k . (n-k)!, kde scitame pro k=0...n.  Formulace problemu menaze: Kolika zpusoby lze rozesadit kolem stolu n manzelskych dvojic tak, aby se muzi stridali se zenami a manzele nikdy nesedeli vedle sebe.

• 20.4.2000: Vzorec pro problem menaze: # n-permutaci pi takovych, ze pi(i) neni ani i ani i+1, je sum_{k=0}^n 2n/(2n-k) . B(2n-k, k) . (n-k)! . (-1)^k. Je-li F Ferrerova deska tvaru b_1, ..., b_m (b_i jsou slabe rostouci a mohou byt i 0) a s_i=b_i-i+1, mame identitu sum_k r_k . (x)_{m-k} = (x+s_1)(x+s_2) ... (x+s_m)  (r_k je pocet umisteni k vezi v F a (x)_i je klesavy faktorial). Dusledek: Pocet umisteni k vezi v trojuhelnikove F. desce 0,1, 2, ..., m je S(m, m-k), kde S( , .) je Stirlingovo cislo 2. druhu. Formule pro pocet F. desek (bez nulovych sloupcu) s vezovym polynomem rovnym vezovemu polynomu dane F. desky. Napr. je prave 3^{n-1} F. desek, ktere maji stejny vezovy polynom jako [n] x [n].

• 27.4.2000: Dukaz identity pro inkluzi a exkluzi pomoci bijekce. Princip involuce (Garsia & Milne 1981): A a B konecne mnoziny, obe maji + cast a - cast; f je znamenko zachovavajici bijekce mezi A a B; a a b jsou znamenko menici bijekce A a B na sebe, jejichz pevne body jsou +; pak a i b maji stejny pocet pevnych bodu a z f, a a b lze mezi obema mnozinami pevnych bodu sestrojit bijekci. Remmelova veticka o rozkladovych identitach: Jsou-li a_1, a_2, ...  a b_1, b_2, ... dve posloupnosti (ciselnych) rozkladu takovych, ze posloupnosti (a_i) i (b_i) jsou po dvou disj. (ruzne rozklady nemaji spolecnou cast) a pro kazde i rozkladaji a_i i b_i totez cislo, plati identita: (# r. cisla n, ktere neobsahuji jako podrozklad zadny rozklad a_i) = (# r. cisla n, ktere neobsahuji jako podrozklad zadny rozklad b_i). Zatim bez dukazu, ale par aplikaci: a_i = {d} a b_i = {1^d} (Glaisherova identita), (# r. cisla n na casti kongr. +- 1 mod 6) = (# r. cisla n na ruzne casti kongr. +- 1 mod 3) (jednodussi cast Schurovy 1926 identity), a_i = {2i, 2i+2} a b_i = {i, i, i+1, i+1} (zde nutno pouzit obecnejsi verzi vety), atd. Formulace Rogers-Ramanujanovych identit.

• 4.5.2000: Dukaz Remmelovy veticky pomoci involuci. 1. Rogers-Ramanujanova identita: (# r. cisla n na ruzne casti lisici se alespon o 2) = (# r. cisla n na casti kongr. +- 1 mod 5). Naznaceni dukazu Bressouda a Zeilbergera pomoci involuci (jen definice involuci, bez overeni, ze to opravdu jsou involuce).

• 12.5.2000: Formulace R.-R. identit jako identit mezi GF:

prod_{m>=1} 1/ ( (1-q^{5m+1}).(1-q^{5m+4}) ) = sum_{k>=0} q^{k^2}/( (1-q)...(1-q^k) )  a
prod_{m>=1} 1/ ( (1-q^{5m+2}).(1-q^{5m+3}) ) = sum_{k>=0} q^{k^2+k}/( (1-q)...(1-q^k) ) .
Jacobiho identita:
prod_{m>=1} (1+y.q^{2m-1}).(1+y^{-1}.q^{2m-1}).(1-q^{2m}) = sum_{k=-nekon.}^{+nekon.} y^k.q^{k^2} .
Kombinatoricky dukaz Ferrerovymi diagramy. Dva snadne dusledky  Jacobiho identity.

Zkouskove okruhy: 1.  Pocitani v C[[x]] (formalni konvergence, substituce moc. rad), vyjadreni e^x nekonecnym soucinem. 2. Vzorec pro pocet k-tic (X_1, ..., X_k), kde X_i je podmnozina [n] a celkovy prunik je prazdny, dve odvozeni. 3. Mnoziny, multimnoziny, kompozice a jejich pocty. 4. Permutace-vysledky o cyklove strukture a inverzich. 5. Permutace-vysledky o poklesech, vcetne determinantove formule (prednaska 6.4.). 6. q-zobecneni identity sum_{pi} 1 = M(n; a_1, ..., a_m), kde scitame pres vsechny permutace multimnoziny { 1^{a_1}, 2^{a_2}, ..., m^{a_m} }, n=a_1+...+a_m, a M(...) je multinomicky koeficient. Kombinatoricky vyklad q-zobecneni binomickych koeficientu. 7. Vysledky o Stirlingovych cislech 2. druhu. 8. Vysledky o Bellovych cislech. 9. Ruzne formulace PIE (princip inkluze a exkluze), dukaz PIE involuci, problem satnarky. 10. Permutace se zakazanymi pozicemi, problem menaze. 11. Vysledky o vezovych polynomech Ferrerovych desek. 12. Princip involuce a jeho pouziti (Remmelova veticka, bez Rogers-Ramanujanovy identity).

U zkousky si vylosujete jednu otazku. Pripadne (vytahnete-li si jednodussi okruh) muzu dat jeste jednu doplnujici otazku. MK.

kveten 2000