Kombinatorické počítání NDMI015, LS 2013/14

Místo a čas přednášky: S 221 (chodba KAM v 2. patře), středa 12:20-13:50.
Výuka tohoto předmětu v minulých letech: zde .
Plán letošní přednášky. Vyložím různé výsledky kombinatorické enumerace pomocí v ní hojně používané techniky generujících funkcí, s důrazem na algebraické manipulace s nimi. Analytickým přístupem ke generujícím funkcím v kombinatorické enumeraci  se zabývá přednáška V. Jelínka, kterou vřele doporučuji.

Otázky ke zkoušce/Exam questions (for dates and times of exams see the information system SIS or contact me): 1. Give (and sometimes prove) basic properties of Catalan numbers. 2. Prove Stirling's approximation of factorial. 3. State and prove the theorem characterizing rational GF and the theorem characterizing quasipolynomials.  4. Deduce transfer matrix formula and give some applications. 5. Ehrhart's theorem: prove that |Z^d intersection nP| is a quasipolynomial in n.  6. The product formula and the composition formula for EGFs, examples. 

Literatura. Literatura bude uvedena na přednášce.


lecture 1, February 26, 2015.  Introduction via Catalan numbers. c_n = number of rooted plane trees with n vertices. Derivation of c_n = (1/n)Binom(2n - 2, n - 1) by generating "function" C = C(x) = c_1x + c_2x^2 + ... . New recurrence c_{n + 1} = ((4n - 2) / (n - 1))c_n and its deduction from C^2 - C + x = 0: C satisfied the DE (1 - 4x)C' = 1 - 2C. Parity of c_n. Estimates of the growth of c_n and two formulae for c_n using binomial coefficients. Roughly sections 1.1 and 1.3 of these preliminary lecture notes (correct the URL as was said in the lecture) .  

lecture 2, March 4, 2015. Precise asymptotics of c_n by means of the Stirling formula for factorial. A bijective proof of c_n = (1/n)binom(2n - 2, n - 1) by means of Dyck words. Two proofs of the fact that the sequence of Catalan numbers (c_n) does not satisfy any linear recurrence with constant coefficients: by parity of c_n and by the formula C(x) = (1/2)(1 - sqrt{1 - 4x}). Sections 1.4 and 1.5 of the preliminary lecture notes

lecture 3, March 11, 2015. Narayana numbers c_{n, k} - a refinement of Catalan numbers, count rp trees with n vertices and k leaves, their symmetry c_{n, k} = c_{n-k, k} proved by GF. Other structures counted by Catalan numbers: 123-free permutations. Valtr's theorem, a particular case: can you prove that Prob(they form a convex chain | four random and independent points in a unit square form a convex quadrangle) = 1/5 ? 1st proof of Stirling's formula n! = (1 + o(1))(2pi.n)^{1/2}(n/e)^n by real analysis, based on the identity log(n!) = int_{1/2}^{n+1/2} log(x) dx + c + O(1/n). Sections 1.6, 1.7 and 2.1 of the preliminary lecture notes.

lecture 4, March 18, 2015. Finishing the 1st proof of Stirling's formula, the constant c = (2pi)^{1/2} is deduced by means of Wallis integral. The 2nd proof of Stirling's formula based on the Gamma function representation of n! and Laplace's method for asymptotics of integrals. Sections 2.1 and 2.2 of the preliminary lecture notes.

lecture 5, March 25, 2015. We turn to rational generating functions. The urexample: Fibonacci numbers (see here). Schur's asymptotics for numbers of partitions of n into (coprime) parts a_1, a_2, ..., a_k (see here).

lecture 6, April 1, 2015. The numbers of horizontally convex polyominoes with n squares satisfy for n > 4 recurrence relation a_n = 5a_{n - 1} - 7a_{n - 2} + 4a_{n - 3}, see here (str. 33-35). Theorem characterizing rational GF, see here .

lecture 7, April 8, 2015. Rademacher's conjecture on the partial fractions decomposition 1 / ((1 - x)(1 - x^2)...(1 - x^n)) = b_n / (1 - x) + ...  : for n --> oo there exists the limit lim b_n (and the same holds for other partial fractions); conjectured by Rademacher in 1973. Drmota and Gerhold disproved it here.) General algebraic properties of formal power series: the ring C[[x]]. Characterization of units. The field of fractions of C[[x]] is the field of formal Laurent series C((x)). Formal convergence and summation of infinite series in C[[x]]. Expressing 1/f as a sum of formal geometric series, see here. Quasipolynomials, the conjecture of Roune and Woods (see their preprint): the Frobenius number F(a_1(t), ..., a_n(t)) (=the last integer not expressible as a nonnegative linear combination of the arguments a_i(t)), where each a_i(t) is an integral-valued and eventually positive  eventual quasipolynomial, is given by an eventual quasipolynomial; they proved it for n <= 3 and for linear a_i(t).

lecture 8, April 15, 2015. Theorem characterizing quasipolynomials: 1) a_n is a qpoly for large n, 2) The GF A(x) of a_n has form p(x) / (1-x^m)^n and 3) a_n = lin. combination of terms n^j.u^n where u is a root of 1, for large n.  Transfer matrix formula/method (see here).

lecture 9, April 22, 2015. Combinatorial aplication of the transfer matrix formula/method: counting walks in a weighted digraph. Ehrhart's theorem on the numbers of lattice points in polytopes, according to these lectures notes (at present preliminary, incorrect, unfinished).

lecture 10, April 29, 2015. Ehrhart's theorem on the numbers of lattice points in polytopes, according to these lectures notes (at present preliminary, incorrect, unfinished).

lecture 11, May 6, 2015. Application of Ehrhart's theorem and reciprocity relation to counting semimagical squares (square matrices with fixed dimension, entries in N_0 and all row and column sums equal to n), the case of 3 by 3 matrices worked out in detail.

lecture 12, May 20, 2015.  (May 13 there was no class because of (rector's) sports day). Remarks on reciprocity relations: 1) if q(x) is the quasi-polynomial of Ehrhart's theorem  for polytope P then q(-n) = (-1)^{dim P}#(latt. points in nP^o) where P^o is the relative interior of P and 2) if K is a cone with vertex v then F_{v + K}(1/x) = (-1)^{dim K}F_{-v + K^o}(x); proof of 2) for v = 0 and simplicial K. Exponential generating functions (EGF), the product formula and the composition formula (see these lecture notes (chapter VIII) in Czech),  EGF of the Bell numbers B_n (= # sets {X_1, ..., X_k} such that the X_i are nonempty, disjoint and their union is [n]), of ordered Bell numbers C_n (= # tuples (X_1, ..., X_k) such that ...), and (as an exercise) of the plus-minus Bell numbers (= # sets {X_1, ..., X_k} such that ..., weighted by (-1)^k).


květen (May) 2015