Combinatorial Counting, NDMI015, summer term 2019/20
Lectures are on Friday 17:20 - 18:50 in the lecture room S1 at the 4th floor in the Mala Strana building.
On exam and exam questions. Exam is in Czech or English and is preferably in contact form (oral with written
preparation) but distant form is possible on request, see SIS for terms.
1. Determine (with a proof) when the Catalan numbers c_n are odd and prove lower and upper exponential bounds on them.
2. Give a combinatorial proof of the formula c_n = (1/n)binom(2n - 2, n - 1).
3. Give two proofs that the Catalan numbers (c_n) do not satisfy any linear recurrence with constant coefficients.
4. Prove that the ring C[[x]] of formal power series is an integral domain and find (with a proof) its units.
5. Prove that if K is a subfield of L and (a_n) is a LRS (linear recurrence sequence) that is a subset of K but is
given by a recurrence with coefficients in L, then (a_n) satisfies a recurrence with coefficients in K.
6. State and derive the algebraic TMM formula (you do not have to prove the following blabla of mine on isomorphisms
of the rings U and V).
7. State and prove the combinatorial TMM formula.
8. State the LIF and deduce by it the formula for the Catalan numbers.
1st lecture on February 28, 2020 (M. Klazar). Catalan numbers c_n,
set-theoretically and intuitively. A bijection and the basic recurrence. When is c_n odd? Lower and upper exponential bounds on c_n.
Derivation of a formula for c_n by means of a GF, to be continued.
Lecture notes for the 1st lecture.
2nd lecture on March 6, 2020 (M. Klazar). Further counting with the Catalan numbers. A combinatorial proof
of the formula c_n = (1/n)binom(2n - 2, n - 1). Containment of permutations and the Catalan numbers again.
Lecture notes for the 2nd lecture.
Starting March 11 classes in person are cancelled because of the coronavirus quarantine.
I will post my scanned handwritten lecture notes here on each Friday. The form of the exam will be determined later.
March 13, 2020 (M. Klazar). Holonomic sequences and holonomic formal power series. A sequence is holonomic iff
its OGF is holonomic, proof. Any algebraic power series is holonomic, proof. study text replacing the 3rd lecture.
March 20, 2020 (M. Klazar). Four proofs that the Catalan numbers (c_n) do not satisfy any linear recurrence
with constant coefficients: 1) by 2-adic valuation, 2) by irrationality of the OGF, and 3) by asymptotics. The ultimate fourth proof next time.
study text replacing the 4th lecture.
March 27, 2020 (M. Klazar).
I apologize that the study text replacing the 5th lecture
has been posted here on Saturday. Here it is: 4) again by algebra. ``A sequence is holonomic iff its OGF is holonomic'' revisited, careful
proof that a nontrivial recurrence yields a nontrivial diff. equation and vice versa.
April 3, 2020 (M. Klazar). Still an addendum to the proof that if the OGF A(x) is holonomic then the sequence
of its coefficients is holonomic too. LRS (linear recurrence sequences), Theorem: A sequence is a LRS iff its OGF
is rational, precise proof in the next lecture - we need some preparation for it. The ring C[[x]] of formal power series (with complex coefficients and
one formal variable x), the orders ord(A) of elements A in it. Proposition: this ring is an integral domain, proof.
Proposition: an element A=A(x) in this ring is a unit iff ord(A)=0, proof.
study text replacing the 6th lecture.
April 10, 2020. No lecture - Good Friday. However, there will be lectures on May 1 and 8.
April 17, 2020. I am sorry for the delay, the study text will be posted here tomorrow on April 21. Well,
on April 22. Here it is: study text replacing the 7th lecture. Theorem:
a sequence (a_n) in C is a LRS (linear recurrence sequence) iff its generating function A(x) is rational (this is an approximate formulation, some
conditions have to be imposed so that the equivalence really holds), proof. The Fibonacci numbers and Binet's formula for them, proof/derivation.
April 24, 2020. study text replacing the 8th lecture (updated on April 28).
Power sums. Theorem: every LRS (linear recurrence sequence) (a_n) = (a_1, a_2, ...) has expression a_n = S(n)
for some power sum S(x); for every power sum S(x), the sequence (S(n)) is a LRS; proof. Lemma (used in the proof):
every system of homogeneous linear equations with more unknowns than equations has a nontrivial (not everything is 0) solution, proof left as an
exercise. This lemma can be also used to prove the Proposition: if K subfield of L is an extension of fields,
(a_n) subset of K is a LRS given by a recurrence with coefficients in L, then (a_n) satisfies a recurrence with coefficients in K, proof next time.
May 1, 2020. See May 8.
May 8, 2020. study text replacing the 9th lecture (sorry for the week delay).
Proof of the previous Proposition. The Fatou lemma: Every integral LRS follows an integral recurrence, without proof.
The SML (Skolem - Mahler - Lech) theorem: Every nonzero and non-degenerate power sum S(x)
defined over a field K with char(K) = 0 has the property
that S(n) = 0_K for only finitely many integers n, without proof. Example that for K = Z_p(x) this does not
hold. study text replacing the 10th lecture. The SML theorem (equivalently) again:
For every LRS (a_n) in a field K with char(K) = 0 there is a natural number m such that for every j = 1, 2, ..., m we have a_{mn+j} = 0_K either
for every nonnegative integer n, or for only finitely many n, without proof. The ATMM (algebraic transfer matrix method):
formulation as an identity in the ring of formal power series R[[x]], proof. An algebraic comment to the proof.
May 15, 2020. study text replacing the 11th lecture (updated on May 21).
Proposition: the rings R[[x]]^{nxn} and R^{nxn}[[x]] are isomorphic, proof. The proof of the TMM formula revisited in
the light of this isomorphism. Beginning of the combinatorial aspect of the TMM formula, to be continued in the last lecture tomorrow.
May 22, 2020. study text replacing the 12th lecture (updated on May 22).
Combinatorial aspect of the TMM formula. Proposition: the (i,j)-position of the power A^n of the adjacency matrix
A of a weighted digraph D is the sum of weights of all walks from v_i to v_j with length n, proof. The CTMM
(combinatorial transfer matrix method): GF of weighted paths in D is --- as a ratio of two determinants --- rational, proof.
Operation of composition of power series. Definition, Proposition:
if in a monoid every element has a left inverse, these are also right inverses and are unique, proof. This gives the formal inverse f(x)^{(-1)} to
any formal power series f(x) = a_1x + a_2x^2 + ... with nonzero coefficient a_1. LIF (the Lagrange inversion formula: if f(x)
= x +a_2x^2 + ... then [x^n]f(x)^{(-1)} = (1/n)[x^{n-1}](x/f(x))^n, without proof. Example: yet another derivation
of the formula c_n = (1/n)binom(2n-2, n-1) for the Catalan numbers, this time by the LIF.
April 2020