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