Lecture Notes on the course Combinatorics (Honours) by Helmut Prodinger,

Wits University, Johannesburg

Course notes are related to the version given in 2000.

Updated November 2, 2001

1. Basic counting

Assume that we are given an n–element set {a_{1}, …, a_{n}}. Without loss of generality we may assume that the set is {1, …, n}. Our first counting problem is about ordered samples of size k (ordered subsets of k elements). Example: n = 4 and k = 2. The ordered samples in question are

12 13 14 21 23 24 31 32 34 41 42 43.

The general formula is: n\underline{k}. (Read “n to the k falling,” with the meaning n\underline{k} := n(n − 1) … (n − k + 1).)

Proof: For the first element of the sample we have n possibilities, for the second n − 1, and so on. Observe that n\underline{k} = \frac{n!}{(n−k)!}. The special case k = n means permutations, and we have n! of them.

The next problem is about ordered samples of size k, where repetitions are allowed. That means, that we have n possibilities for every element of the sample, thus n^{k}.

Now we turn to unordered samples. As the word says, the order in the sample does not count. Thus we can order the sample canonically. (E. g. in increasing order.)

The samples of size k are simply the subsets with k elements. They are counted by binomial coefficients \binom{n}{k}. We want a formula for that: Recursion \binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}. \binom{n}{n} = \binom{n}{0} = 1, and we have Pascal’s triangle. (Justification is simple: The element n + 1 might be in the sample, giving a contribution \binom{n}{k}, or not, giving a contribution \binom{n}{k+1}.)

From the formula for ordered samples n\underline{k} we get by division by k! (disregarding the order) the formula \binom{n}{k} = \frac{n!}{k!(n−k)!}. Note that also

\binom{n}{k} = ∑_{1≤i_{1}<i_{2}<···<i_{k}≤n} 1.

The case of unordered samples with repetitions is the hardest: The number of interest is

∑_{1≤i_{1}≤i_{2}≤···≤i_{k}≤n} 1.

This is the same as

∑_{1≤i_{1}<i_{2}+1<i_{3}+2···<i_{k}+k−1≤n+k−1} 1 = ∑_{1≤j_{1}<j_{2}<j_{3}···<j_{k}≤n+k−1} 1

which is the binomial coefficient \binom{n+k−1}{k}. Another way of seeing that is this: A sample of size k can be coded as a sequence of length k + n − 1 of k ones and n − 1 zeros. The ones represent the element chosen, and the zeros the change from one group to another. Example: Let n = 4 and k = 7. A particular subset (with repetitions allowed) is 1113344. It is coded by 1110011011, which is a sequence of length 10, with 3 zeros. How many such sequences are there? Well, \binom{n+k−1}{k}, since we can choose k places out of n + k − 1 for the k zeros. Example. 22 books are on a bookshelf. We want to pick out 5, and never take two adjacent ones. The answer is

∑_{1≤i_{1}<·i_{2}<····<·i_{5}≤22} 1 = ∑_{1≤i_{1}<i_{2}−1<···<i_{5}−4≤22−4} 1 = \binom{18}{5},

with the shorthand notation

a < ·b ⟺ b − a ≥ 2.

From calculus we know that

(1 + x)^{α} = ∑_{k≥0} \binom{α}{k}x^{k},

and the generalized binomial coefficients involved are defined to be

\binom{α}{n} := \frac{α(α − 1) … (α − n + 1)}{n!},  n ∈ ℕ,
\binom{α}{0} := 1.

And thus

(1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}.

This formula has a combinatorial meaning: We can think about (1+x)(1+x) … (1+x) and multiplying out. The first factor 1+x means take the element 1 or not. The second factor 1 + x means take the element 2 or not, etc.

If n = 3, and we compute

(1 + x)(1 + x)(1 + x) = 111 + 11x + 1x1 + x11 + 1xx + x1x + xx1 + xxx,

then we might think about the subsets (in this order)

∅
{3}
{2}
{1}
{2, 3}
{1, 3}
{1, 2}
{1, 2, 3}.

Notation:

\binom{n}{k} = [x^{k}](1 + x)^{n}.

(Read: coefficient of x^{k} in (1 + x)^{n}.)

This idea applies as well to the case of repetitions: Instead of taking an element or not, we might take it k times, for k ∈ ℕ_{0}. This refers to a term

1 + x + x^{2} + ⋯ = \frac{1}{1 − x}

(recall the formula for the geometric series).

We thus get the formula again for the number of samples of size k out of a set of n elements, with repetitions allowed:

[x^{k}](1 + x + …)^{n} = [x^{k}](1 − x)^{−n} = \binom{−n}{k}(−1)^{k} = \binom{n + k − 1}{k}.

Note the following computation:

\binom{−n}{k} = \frac{(−n)(−n − 1) … (−n + k − 1)}{k!} = (−1)^{k} \frac{(n)(n + 1) … (n + k − 1)}{k!}

= (−1)^{k}\binom{n + k − 1}{k}.

Compositions of an integer. A composition of an integer n is a representation n = i_{1} + ⋯ + i_{k}, with natural numbers i_{j}. The number k is called the number of parts of the composition.

How many compositions are there? How many with k parts? The idea is to think about n ones, separated by k − 1 “+” signs, which are not allowed to be adjacent:

[x^{n}](x + x^{2} + …)^{k} = [x^{n}]\frac{x^{k}}{(1 − x)^{k}} = [x^{n−k}](1 − x)^{−k} = (−1)^{n−k}\binom{−k}{n − k} = \binom{n − 1}{k − 1}.

The total number of compositions of n is thus

∑_{k=1}^{n} \binom{n − 1}{k − 1} = ∑_{k=0}^{n−1} \binom{n − 1}{k} = 2^{n−1}.

Some other binomial coefficients of interest are \binom{−1/2}{n} and \binom{1/2}{n}.

\binom{−1/2}{n} = \frac{(−\frac{1}{2})(−\frac{3}{2}) … (−\frac{1}{2} − n + 1)}{n!}

= \frac{(−1)(−3) … (−2n + 1)}{2^{n}n!}

= (−1)^{n} \frac{1 · 3 … (2n − 1)}{2^{n}n!}

= (−1)^{n} \frac{(2n)!}{2^{n}n!2 · 4 … (2n)}

= (−1)^{n} \frac{(2n)!}{4^{n}n!n!}

= (−1)^{n} \frac{1}{4^{n}} \binom{2n}{n}

[x^{n}]\frac{1}{\sqrt{1 − 4x}} = [x^{n}](1 − 4x)^{−1/2}

= (−4)^{n}\binom{−\frac{1}{2}}{n}

= (−4)^{n}\binom{2n}{n}\frac{(−1)^{n}}{4^{n}}

= \binom{2n}{n}.

That means

\frac{1}{\sqrt{1 − 4x}} = ∑_{n≥0} \binom{2n}{n}x^{n}.

Now

[x^{n}]\frac{1 − \sqrt{1 − 4x}}{2x} = \frac{1}{2}[x^{n+1}](1 − \sqrt{1 − 4x})

= \frac{1}{2}[x^{n+1}](1 − ∑_{k≥0}(−4)^{k}\binom{\frac{1}{2}}{k}x^{k})

= \frac{1}{2}[x^{n+1}] ∑_{k≥1} 4^{k}(−1)^{k−1}\binom{\frac{1}{2}}{k}x^{k}

= \frac{1}{2}4^{n+1}(−1)^{n}\binom{\frac{1}{2}}{n + 1}

= \frac{1}{2}4^{n+1}(−1)^{n} \frac{(\frac{1}{2})(−\frac{1}{2}) … (−\frac{2n−1}{2})}{(n + 1)!}

= \frac{1}{2}2^{n+1}(−1)^{n} \frac{(−1)(−3) … (−(2n − 1))}{(n + 1)!}

= 2^{n} \frac{1 · 3 … (2n − 1)}{(n + 1)!}

= 2^{n} \frac{(2n)!}{(n + 1)!2^{n}n!}

= \frac{1}{n + 1}\binom{2n}{n}.

In other words,

\frac{1 − \sqrt{1 − 4x}}{2x} = ∑_{n≥0} \frac{1}{n + 1}\binom{2n}{n}x^{n} = 1 + x + 2x^{2} + 5x^{3} + 14x^{4} + …

Vandermonde formula. From

(1 + x)^{m+n} = (1 + x)^{m}(1 + x)^{n}

we find, by looking at the coefficient of x^{k},

\binom{m + n}{k} = ∑_{i=0}^{k} \binom{m}{i}\binom{n}{k − i}.

The special case m = n = k is of interest:

\binom{2n}{n} = ∑_{i=0}^{n} \binom{n}{i}\binom{n}{n − i} = ∑_{i=0}^{n} \binom{n}{i}^{2}.

The Vandermonde formula can be easily interpreted combinatorially:

Consider the set {1, 2, …, m, …, m + n} and select k–element subset in all possible ways. A certain number of i elements must be drawn from {1, 2, …, m}, and the remaining k − i (independently) from {m + 1, …, m + n}, whence the formula.

A slight variation is:

\binom{n + 1}{p + q + 1} = ∑_{p≤k≤n−q} \binom{k}{p}\binom{n − k}{q}

which can again be interpreted as selecting p + q + 1 elements from n + 1 elements. We look at the p + 1 element from the sample, which is k + 1; then, p elements must be drawn from {1, 2, …, k} and q elements must be drawn from {k + 2, …, n + 1}.

Simple summations.

∑_{k=0}^{n} \binom{n}{k}(−1)^{k} = δ_{n,0}

(Plug in x = −1 in the binomial theorem.)

∑_{k≤m} \binom{k}{a} = \binom{m + 1}{a + 1}

(by Pascal’s recursion or combinatorially).

∑_{k=0}^{n} k\binom{n}{k} = ∑_{k=1}^{n} k\binom{n}{k}

= ∑_{k=1}^{n} n\binom{n − 1}{k − 1}

= n ∑_{k=0}^{n−1} \binom{n − 1}{k}

= n2^{n−1}.

∑_{k=0}^{n} k^{2}\binom{n}{k} = ∑_{k=1}^{n}(k(k − 1) + k)\binom{n}{k}

= n(n − 1) ∑_{k=2}^{n} \binom{n − 2}{k − 2} + n2^{n−1}

= n(n − 1)2^{n−2} + n2^{n−1}

= n2^{n−2}(n + 1).

Model. Balls into boxes: n distinguishable boxes, k balls (distinguishable) distribute, each box at most 1 ball: n\underline{k}. Each box can contain an arbitrary number: n^{k}. Balls are undistinguishable: \binom{n}{k} resp.\binom{n+k−1}{k}.

Example. Distribute 27 undistinguishable balls into 7 boxes, but the first can contain at most 9 balls.

Answer:

[x^{27}](1 + x + ⋯ + x^{9})(1 + x + x^{2} + …)^{6} = \frac{1 − x^{10}}{(1 − x)^{7}}

= [x^{27}]\frac{1}{(1 − x)^{7}} − [x^{17}]\frac{1}{(1 − x)^{7}} = \binom{33}{6} − \binom{23}{6} = 100621

Example: Choose 25 objects from 7 types, but every type must appear at least 2 times and at most 6 times. Answer

[x^{25}](x^{2} + ⋯ + x^{6})^{7} = [x^{25}]x^{14}(1 + ⋯ + x^{4})^{7} = [x^{11}]\frac{(1 − x^{5})^{7}}{(1 − x)^{7}}

= [x^{11}]\frac{1 − 7x^{5} + 21x^{10}}{(1 − x)^{7}} = \binom{17}{11} − 7\binom{12}{6} + 21\binom{7}{1} = 6055.

2. Reflection principle of D. André

We consider paths in the plane, where in one unit of time one can do either a step ↗ or a step ↘.

We start in the origin (0, 0) and end in (2n, 0). It is plain to see that there are \binom{2n}{n} such paths. (If you don’t see it, think about the fact that n steps must go up and n steps must go down, and any relative arrangement is possible.)

The more challenging question is to count the subset of these paths with the additional property that the path never goes below the x–axis. The number of these equals the number of all paths minus the number of paths that do go below the x–axis. For them, we perform a bijection, as indicated in the picture.

[figure: _{.....}; _{.....}; _{.....}; _{.....}; _{.....}; _{.....}; _{.....}; _{.....}; _{.....}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; O; (0, −2); (22, 0)]

(We take the first part, until the level −1 is reached for the first time, and reflect it along the −1–axis. That gives us a path from (0, −2) to (2n, 0). On the other hand, if we have such a path, the reverse operation transforms it into a “bad” path.)

We must enumerate the paths from (0, −2) to (2n, 0). They consist of n + 1 steps ↗ and n − 1 steps ↘, in any order. Thus the answer is \binom{2n}{n+1}.

Altogether we find

\binom{2n}{n} − \binom{2n}{n + 1} = \frac{1}{n + 1}\binom{2n}{n}.

These numbers are called Catalan numbers and appear in many enumeration problems. Observe that another way of drawing the diagram is like this (with steps ↑ and →).

[figure: _{.....}; _{.....}; . . . . .; .....; . . . . .; ^{.....}; . . . . .; . . . . .; . . . . .; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; O]

Let us discuss Ballot numbers. A has m votes, B has n votes, m ≥ n. How many “histories” are there, in which B never leads? In terms of lattice paths, this means paths from (0, 0) to (m + n, m − n), never going below the x–axis. All such paths are enumerated by \binom{m+n}{m}. We must subtract the bad guys, and the same type of bijection works, with the result \binom{m+n}{m+1}. Altogether

\binom{m + n}{m} − \binom{m + n}{m + 1}.

These numbers are called ballot numbers, and Catalan numbers are the special instance m = n.

3. Generating functions

For a given sequence a_{0}, a_{1}, … we define the (ordinary) generating function as the (formal) series

f(x) := ∑_{n≥0} a_{n}x^{n}.

Convergence is not a subject here, although most of our generating functions do converge anyway (in an appropriate domain). If we have another generating function

g(x) := ∑_{n≥0} b_{n}x^{n},

then we can define the sum (obviously) by

f(x) + g(x) := ∑_{n≥0}(a_{n} + b_{n})x^{n}.

The product is defined as

f(x) · g(x) := ∑_{n≥0} ( ∑_{k=0}^{n} a_{k}b_{n−k})x^{n}.

If b_{i} ≡ 1, then g(x) = \frac{1}{1−x}, and we find

\frac{1}{1 − x}f(x) = ∑_{n≥0} ( ∑_{k=0}^{n} a_{k})x^{n}.

So going to partial sums means on the level of generating functions the multiplication with \frac{1}{1−x}.

This is quite useful, as we will see now.

Example.

1^{2} + 2^{2} + ⋯ + n^{2} = [x^{n}]\frac{1}{1 − x} ∑_{k} k^{2}x^{k}

We need the following formulæ:

∑_{k} x^{k} = \frac{1}{1 − x}

∑_{k} kx^{k} = x\frac{d}{dx} \frac{1}{1 − x} = \frac{x}{(1 − x)^{2}}

∑_{k} k(k − 1)x^{k} = x^{2} \frac{d^{2}}{dx^{2}} \frac{1}{1 − x} = \frac{2x^{2}}{(1 − x)^{3}}

In general (proof by induction on m or applying the formula for the binomial series to the right hand side)

∑_{k} k\underline{m}x^{k} = \frac{m!x^{m}}{(1 − x)^{m+1}} .

Thus

[x^{n}]\frac{1}{1 − x} ∑_{k} k^{2}x^{k} = [x^{n}]\frac{1}{1 − x}(\frac{2x^{2}}{(1 − x)^{3}} + \frac{x}{(1 − x)^{2}} )

= [x^{n}]\frac{x(1 + x)}{(1 − x)^{4}} = \binom{n + 2}{3} + \binom{n + 1}{3} = \frac{n(n + 1)(2n + 1)}{6}

We want also 1^{3} + 2^{3} + ⋯ + n^{3}. It is useful to write k^{3} = k(k − 1)(k − 2) + 3k(k − 1) + k

1^{3} + 2^{3} + ⋯ + n^{3} = [x^{n}]\frac{1}{1 − x} ∑_{k≥0} k^{3}x^{k}

= [x^{n}]\frac{1}{1 − x} ∑_{k≥0} (k(k − 1)(k − 2) + 3k(k − 1) + k)x^{k}

= [x^{n}]\frac{1}{1 − x}\{\frac{6x^{3}}{(1 − x)^{4}} + 3\frac{2x^{2}}{(1 − x)^{3}} + \frac{x}{(1 − x)^{2}} \}

= 6[x^{n−3}]\frac{1}{(1 − x)^{5}} + 6[x^{n−2}]\frac{1}{(1 − x)^{4}} + [x^{n−1}]\frac{1}{(1 − x)^{3}}

= 6\binom{n + 1}{n − 3} + 6\binom{n + 1}{n − 2} + \binom{n + 1}{n − 1}

= \frac{(n + 1)(n)(n − 1)(n − 2)}{4} + (n + 1)(n)(n − 1) + \frac{(n + 1)(n)}{2}

= \frac{(n + 1)n}{4}[(n − 1)(n − 2) + 4(n − 1) + 2]

= \frac{(n + 1)n}{4}(n + 1)n

= (\frac{(n + 1)n}{2})^{2}.

Generally (with some coefficients that are still to be determined):

x^{n} = ∑_{k} \left\{{n \atop k}\right\}x\underline{k}.

Since

x^{n+1} = ∑_{k} \left\{{n \atop k}\right\}x\underline{k}x = ∑_{k} \left\{{n \atop k}\right\}x\underline{k}(x − k + k)

= ∑_{k} \left\{{n \atop k}\right\}x\underline{k+1} + ∑_{k} k\left\{{n \atop k}\right\}x\underline{k}

we have the recursion

\left\{{n + 1 \atop k}\right\} = \left\{{n \atop k − 1}\right\} + k\left\{{n \atop k}\right\}

with the boundary conditions

\left\{{0 \atop 0}\right\} = 1, \left\{{1 \atop 0}\right\} = 0, \left\{{1 \atop 1}\right\} = 1.

It is easy to produce a small table. The numbers in question are called Stirling subset numbers (older version: Stirling numbers of the second kind).

The name subset numbers stems from the enumeration of set partitions.

As we all know, a set partition of {1, …, n} is a representation

{1, …, n} = A_{1} ∪ ⋯ ∪ A_{k},

with nonempty sets which are mutally disjoint. The order of these sets (“blocks”) is unimportant (otherwise one would speak about ordered set partitions).

In an obvious notation, I list all of them for n = 4:

{1, …, 4} = 1234

= 123 | 4

= 124 | 3

= 134 | 2

= 234 | 1

= 12 | 34

= 13 | 24

= 14 | 23

= 12 | 3 | 4

= 13 | 2 | 4

= 14 | 2 | 3

= 23 | 1 | 4

= 24 | 1 | 3

= 34 | 1 | 1

= 1 | 2 | 3 | 4

We get 15 of them. We get 1 with one block, 7 with two blocks, 6 with three blocks, and 1 with four blocks. It is no coincidence that the numbers 1, 7, 6, 1 are \left\{{4 \atop 1}\right\}, \left\{{4 \atop 2}\right\}, \left\{{4 \atop 3}\right\}, \left\{{4 \atop 4}\right\}.

It is immediate to check the boundary conditions. For the recursion we argue as follows:

A set partition of {1, …, n + 1} into k blocks can either be a set partition of {1, …, n} into k − 1 blocks, and element n + 1 alone in one block, or a set partition of {1, …, n} into k blocks, and element n + 1 joins any of the k blocks.

1234 123|4 124|3 12|34 12|3|4 134|2 13|24 13|2|4 14|23 1|234 1|23|4 14|2|3 1|24|3 1|2|34 1|2|3|4 123  12|3  13|2  1|23  1|2|3 12  1|2 1

The figure shows the generation of set partitions by inserting a new element into the all existing blocks (or creating a new one).

We want an algorithm to generate the set partitions of {1, …, n}, as they appear in the diagram, from left to right.

The principle is this: Define the active digit m to be the largest number that is not alone in a block. (Except for the last set partition, this is well defined.) The active digit moves into the next block (which might be a new one), and then all the numbers greater than m move into the block of 1.

The chain of set partitions is

1234 ⟶ 123|4 ⟶ 124|3 ⟶ 12|34 ⟶ 12|3|4 ⟶ 134|2 ⟶ 13|24 ⟶ 13|2|4

⟶ 14|23 ⟶ 1|234 ⟶ 1|23|4 ⟶ 14|2|3 ⟶ 1|24|3 ⟶ 1|2|34 ⟶ 1|2|3|4,

as desired.

After this little excursion to set partitions, let us come back to some more examples for the use of generating functions.

Examples. Use generating functions to prove

\binom{0}{k} + \binom{1}{k} + ⋯ + \binom{n}{k} = \binom{n + 1}{k + 1} :

Well,

\binom{0}{k} + \binom{1}{k} + ⋯ + \binom{n}{k} = [x^{n}]\frac{1}{1 − x} ∑_{j≥0} \binom{j}{k}x^{j}

= [x^{n}]\frac{1}{1 − x} \frac{x^{k}}{(1 − x)^{k+1}}

= [x^{n−k}]\frac{1}{(1 − x)^{k+2}}

= \binom{n + 1}{n − k} = \binom{n + 1}{k + 1}.

Another one:

∑_{k=0}^{m}(−1)^{k}\binom{n}{k} = (−1)^{m}\binom{n − 1}{m};

it goes like this:

∑_{k=0}^{m}(−1)^{k}\binom{n}{k} = [x^{m}]\frac{1}{1 − x} ∑_{k≥0}(−1)^{k}\binom{n}{k}x^{k}

= [x^{m}]\frac{1}{1 − x}(1 − x)^{n}

= [x^{m}](1 − x)^{n−1}

= (−1)^{m}\binom{n − 1}{m}.

4. Permutations: Inversions and Cycles

Assume that we have a permutation (\begin{matrix}1 & 2 & … & n \\ π_{1} & π_{2} & … & π_{n} \end{matrix}). We prefer the one–line notation π = π_{1}π_{2} … π_{n}. An inversion is a pair (i, j) such that i < j and π_{i} > π_{j}; and I(π) is the number of inversions of permutation π. We list all 6 permutations of 1, 2, 3 and the number of inversions:

123  0
132  1
213  1
231  2
312  2
321  3

More specific information is contained in the inversion table b_{1}b_{2} … b_{n}, where b_{i} is the number of elements larger than i standing to the left of i. Again, here is a little list:

123  (0, 0, 0)
132  (0, 1, 0)
213  (1, 0, 0)
231  (2, 0, 0)
312  (1, 1, 0)
321  (2, 1, 0)

We see that the first entry can vary between 0 and 2, the second between and 0 and 1, and the third one is always 0. This is true in general: 0 ≤ b_{i} ≤ n − i.

If an inversion table is given, the permutation can be reconstructed:

Leave b_{1} empty places (from the left), then insert 1. Leave b_{2} empty places (from the left), then insert 2, etc.

Example. The inversion table (4, 4, 0, 3, 2, 1, 1, 0, 0) is given. We insert elements 1, …, 9:

\begin{matrix}. & . & . & . & . & . & . & . & . \\ . & . & . & . & 1 & . & . & . & . \\ . & . & . & . & 1 & 2 & . & . & . \\ 3 & . & . & . & 1 & 2 & . & . & . \\ 3 & . & . & . & 1 & 2 & 4 & . & . \\ 3 & . & . & 5 & 1 & 2 & 4 & . & . \\ 3 & . & 6 & 5 & 1 & 2 & 4 & . & . \\ 3 & . & 6 & 5 & 1 & 2 & 4 & 7 & . \\ 3 & 8 & 6 & 5 & 1 & 2 & 4 & 7 & . \\ 3 & 8 & 6 & 5 & 1 & 2 & 4 & 7 & 9 \end{matrix}

So instead of talking about permutations we may as well discuss inversion tables. This has advantages. First, note, that the sum of the entries is just the number of inversions.

Then, the entries may be chosen indepently from each other. (In the one-line notation, this is not so, because one can only choose elements that were not already there.)

The number of permutations of n elements with exactly k inversions is given by

[x^{k}](1 + x + ⋯ + x^{n−1})(1 + x + ⋯ + x^{n−2}) … (1 + x)(1).

Each parenthesis reflects the possible choices of the various entries of the inversion table.

Thus

∏_{k=1}^{n} \frac{1 − x^{k}}{1 − x} = \begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ i=0 \end{matrix} [number of permutations of n elements with i inversions]x^{i}.

Note that

\begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ i=0 \end{matrix} \frac{1}{n!}[number of permutations of n elements with i inversions] i

is the expected number of inversions. It can be computed by a differentiation of

(1 + x + ⋯ + x^{n−1})(1 + x + ⋯ + x^{n−2}) … (1 + x)(1),

followed by plugging in x = 1, and dividing by n!.

The differentation gives

(1 + x + ⋯ + x^{n−1})(1 + x + ⋯ + x^{n−2}) … (1 + x)(1) ×

× ∑_{k=1}^{n} \frac{1 + 2x + 3x^{2} + ⋯ + (k − 1)x^{k−2}}{1 + x + ⋯ + x^{k−1}} .

Plugging in gives

n! ∑_{k=1}^{n} \frac{1 + 2 + 3 + ⋯ + (k − 1)}{k}.

Division by n! gives

∑_{k=1}^{n} \frac{\frac{k(k−1)}{2}}{k} = \frac{1}{2} ∑_{k=1}^{n}(k − 1)

= \frac{1}{2} ∑_{k=0}^{n−1} k = \frac{1}{2} \frac{n(n − 1)}{2} = \frac{n(n − 1)}{4}.

This is half of the maximal number of inversions \binom{n}{2}, which occurs for n, n−1, …, 2, 1. —————

Every permutation can be written as a product (collection of) cycles. Again, a list illustrates this:

123  (1)(2)(3)
132  (1)(23)
213  (12)(3)
231  (123)
312  (132)
321  (13)(2)

Often, people leave out fix points (singletons):

123  Id
132  (23)
213  (12)
231  (123)
312  (132)
321  (13)

However, we want to discuss the canonical representation as a product of cycles. The cycle (1356) can also be described as (3561), (5613), and (6135). However, we choose the form where the smallest number of the cycle (cycle leader) is in the first position. Thus here (1356). Now every cycle has a cycle leader. We arrange the cycles, according to their cycle leaders, from left to right in descending order.

Example. Take (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 7 & 3 & 6 & 2 & 8 & 5 & 1 & 10 & 9 & 4 \end{matrix}).

We find cycles (1 7), (2 3 6 5 8 10 4), and (9), with cycle leaders 1, 2, 9. In descending order 9, 2, 1. Thus the permutation is given in the canonical representation as

(9)(2 3 6 5 8 10 4)(1 7).

Now parantheses can be removed!

9 2 3 6 5 8 10 4 1 7.

The reason is that each left–to–right minimum (an element that is smaller than all the elements to the left) opens a new parenthesis, so that they can be reconstructed. In particular, we see that the number of cycles equals the number of left–to–right minima.

Now define

\left[{n \atop k}\right] = the number of permutations of n elements with k cycles.

Boundary conditions:

\left[{n \atop 0}\right] = δ_{n0},

\left[{n \atop n}\right] = 1,

recursion:

\left[{n \atop k}\right] = (n − 1)\left[{n − 1 \atop k}\right] + \left[{n − 1 \atop k − 1}\right],

because a new element can be alone in a new cycle, or can be inserted after each element in the respective cycle. It is a good idea to write a little table. The numbers are called Stirling’s cycle numbers (or signless Stirling numbers of the first kind).

On the other hand, consider this exercise: Express (in a unique way)

x\underline{n} = ∑_{k=0}^{n} a_{n,k}x^{k}

Then

a_{0,0} = 1,

and by plugging in x = 0,

a_{n,0} = 0, for n ≥ 1.

Also

a_{n,n} = 1,

since there is no other choice to get x\underline{n}. For the recursion, do this:

x\underline{n+1} = (x − n) · x\underline{n}

= (x − n) ∑_{k=0}^{n} a_{n,k}x^{k}

= ∑_{k=0}^{n} a_{n,k}x^{k+1} − n ∑_{k=0}^{n} a_{n,k}x^{k}.

Now compare that with

x\underline{n+1} = ∑_{k=0}^{n+1} a_{n+1,k}x^{k};

the comparison leads to

a_{n+1,k} = a_{n,k−1} − na_{n,k},

or

a_{n,k} = a_{n−1,k−1} − (n − 1)a_{n−1,k}.

This is not the recursion for the Stirling cycle numbers, but it is close: Define b_{n,k} = (−1)^{n−k}a_{n,k}, then

b_{n,k} = b_{n−1,k−1} + (n − 1)b_{n−1,k}.

Hence

x\underline{n} = ∑_{k=0}^{n}(−1)^{n−k}\left[{n \atop k}\right]x^{k}.

5. The Inclusion–Exclusion principle

Everybody knows this formula.

|A ∪ B| = |A| + |B| − |A ∩ B|

The generalisation to n sets is

|A_{1} ∪ ⋯ ∪ A_{n}| = ∑_{∅⊆I⊆{1,...,n},I≠∅}(−1)^{|I|+1}| ⋂_{i∈I} A_{i}|,

and we will prove it by induction: The cases n = 1 and n = 2 are clear.

|A_{1} ∪ ⋯ ∪ A_{n+1}| = |A_{1} ∪ ⋯ ∪ A_{n}| + |A_{n+1}| − |(A_{1} ∪ ⋯ ∪ A_{n}) ∩ A_{n+1}|

= |A_{1} ∪ ⋯ ∪ A_{n}| + |A_{n+1}| − |(A_{1} ∩ A_{n+1}) ∪ ⋯ ∪ (A_{n} ∩ A_{n+1})|

= ∑_{∅⊆I⊆{1,...,n},I≠∅}(−1)^{|I|+1}| ⋂_{i∈I} A_{i}| + |A_{n+1}|

− ∑_{∅⊆I⊆{1,...,n},I≠∅}(−1)^{|I|+1}| ⋂_{i∈I}(A_{i} ∩ A_{n+1})|

= ∑_{∅⊆I⊆{1,...,n+1},I≠∅}(−1)^{|I|+1}| ⋂_{i∈I} A_{i}|.

The following variation is often useful: Assume A_{1}, …, A_{n} ⊆ X, then

|A_{1}^{c} ∩ ⋯ ∩ A_{n}^{c}| = |(A_{1} ∪ ⋯ ∪ A_{n})^{c}|

= |X| − |A_{1} ∪ ⋯ ∪ A_{n}|

= ∑_{∅⊆I⊆{1,...,n}}(−1)^{|I|}| ⋂_{i∈I} A_{i}|.

Application: A_{i} = {x | x has property P_{i}}. Then we are interested in the set of elements having none of the properties P_{1}, …, P_{n}.

Example. The number of permutations of n elements without fixpoints. Often, one sees this as the probability that n (cliché professors), who ask for their (n) hats (after Hamlet in the Civic Theatre), all have a wrong hat.

Set A_{i} = {permutations having i as fixpoint}, then we compute

| ⋂_{i∈I} A_{i}| = (n − |I|)!.

Our formula tells us

∑_{k=0}^{n} \binom{n}{k}(−1)^{k}(n − k)! = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} .

To go to probabilities, we divide by n!, and get a quantity that goes to \frac{1}{e} (very quickly).

Alternative proof of the formula. Observe

| ⋂_{i∈∅} A_{i}| = |X|.

Consider an element x. If x is in none of the sets A_{i}, it is counted once on the left side, and occurs only for I = ∅ on the right side, thus also once.

If x occurs in exactly m ≥ 1 of the sets: left 0, right: in A_{i} : m times, in A_{i} ∩ A_{j} \binom{m}{2} times, etc.

1 − m + \binom{m}{2} − \binom{m}{3} + ⋯ = 0

Another standard application is this. How many numbers between 1 and n are neither divisible by 2,3, or 5?

Set

A_{2} := {1 ≤ k ≤ n | 2 divides k},
A_{3} := {1 ≤ k ≤ n | 3 divides k},
A_{5} := {1 ≤ k ≤ n | 5 divides k},
A_{6} := {1 ≤ k ≤ n | 6 divides k} = A_{2} ∩ A_{3},
A_{10} := {1 ≤ k ≤ n | 10 divides k} = A_{2} ∩ A_{5},
A_{15} := {1 ≤ k ≤ n | 15 divides k} = A_{3} ∩ A_{5},
A_{30} := {1 ≤ k ≤ n | 30 divides k} = A_{2} ∩ A_{3} ∩ A_{5}.

It is easy to see that

A_{i} = ⌊\frac{n}{i}⌋ .

Our answer is then

|A_{1}^{c} ∩ A_{2} ∩ A_{3}^{c}| = n − |A_{2}| − |A_{3}| − |A_{5}| + |A_{6}| + |A_{10}| + |A_{15}| − |A_{30}|

= n − ⌊\frac{n}{2}⌋ − ⌊\frac{n}{3}⌋ − ⌊\frac{n}{5}⌋ + ⌊\frac{n}{6}⌋ + ⌊\frac{n}{10}⌋ + ⌊\frac{n}{15}⌋ − ⌊\frac{n}{30}⌋ .

6. Fibonacci numbers and linear recursions

The Fibonacci numbers F_{n} are defined by F_{0} = 0, F_{1} = 1, and the recursion F_{n+2} = F_{n+1} + F_{n}, so that the first few values are 0, 1, 1, 2, 3, 5, 8, 13, 21, . . ..

There are many “popular” versions of the nature and origin of this sequence; a whole journal is devoted to it!

We are interested in a explicit formula for F_{n}; for that, we use generating functions. Define

F (z) = ∑_{n≥0} F_{n}z^{n},

then

F_{n+2}z^{n+2} = F_{n+1}z^{n+2} + F_{n}z^{n+2},

which we sum from n = 0, 1, … to get

F (z) − F_{1}z − F_{0} = z(F (z) − F_{0}) + z^{2}F (z),

or

F (z)(1 − z − z^{2}) = z.

This gives us the explicit form

F (z) = \frac{z}{1 − z − z^{2}} .

This is nice, but how can we get the coefficients? The keyword is partial fraction decomposition, and we compute the zeros of 1 − z − z^{2} = 0 as

z_{1,2} = \frac{−1 ± \sqrt{5}}{2}.

We know that we can achieve the form

\frac{z}{1 − z − z^{2}} = \frac{A}{z − z_{1}} + \frac{B}{z − z_{2}} ,

with some constants A, B.

However, in combinatorial contexts, it is more useful to achieve the form

\frac{z}{1 − z − z^{2}} = \frac{A}{1 − z/z_{1}} + \frac{B}{1 − z/z_{2}} ,

with some (different) constants A, B. In the light of that we compute

\frac{1}{z_{1}} = \frac{1 + \sqrt{5}}{2} =: α,
\frac{1}{z_{2}} = \frac{1 − \sqrt{5}}{2} =: β.

So we are interested in

\frac{z}{1 − z − z^{2}} = \frac{A}{1 − αz} + \frac{B}{1 − βz} .

From this we get

z = A(1 − βz) + B(1 − αz),

which gives us two equations,

1 = −Aβ − Bα
0 = A + B,

or

1 = −Aβ + Aα = A(α − β) = A\sqrt{5},

and thus A = \frac{1}{\sqrt{5}} and B = −\frac{1}{\sqrt{5}}. Altogether

\frac{z}{1 − z − z^{2}} = \frac{1}{\sqrt{5}} [\frac{1}{1 − αz} − \frac{1}{1 − βz} ] .

Reading off the coefficient of z^{n}, this gives us

F_{n} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}] .

This famous formula is called Binet’s formula. Some people might be puzzled by the fact that natural numbers are represented by an expression with irrational numbers like \sqrt{5}. However, they cancel out, as can be seen as follows. (There is no need to demonstrate that, but it is fun anyway.)

F_{n} = \frac{1}{\sqrt{5} 2^{n}} [∑_{k=0}^{n} \binom{n}{k}5^{k/2} − ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}5^{k/2}] ,

or

F_{n} = \frac{1}{2^{n}} ∑_{k=0}^{n} \binom{n}{k}5^{(k−1)/2}(1 − (−1)^{k}).

Now only odd indices survive, and then the factor is 2. Thus

F_{n} = \frac{1}{2^{n−1}} ∑_{j≥0} \binom{n}{2j + 1}5^{j},

from which it is plain to see that there are no more \sqrt{5} ’s.

This principle works also for systems of recursions; we demonstrate that for the instance

2a_{n+1} = 5a_{n} + b_{n},  a_{0} = 2,
2b_{n+1} = a_{n} + 5b_{n},  b_{0} = 0.

We define generating functions

A(z) = ∑_{n≥0} a_{n}z^{n} and B(z) = ∑_{n≥0} b_{n}z^{n}.

We multiply the recursions by z^{n+1} and sum from n = 0, 1, . . .. Thus

2(A(z) − 2) = 5zA(z) + zB(z),
2(B(z) − 0) = zA(z) + 5zB(z).

The second equation gives us

A(z) = \frac{B(z)}{z}(2 − 5z),

which we plug into the first equation;

(2 − 5z)\frac{B(z)}{z}(2 − 5z) − 4 = zB(z),

or

((2 − 5z)^{2} − z^{2})B(z) = 4z,

or

(1 − 2z)(1 − 3z)B(z) = z,

or

B(z) = \frac{z}{(1 − 2z)(1 − 3z)} = \frac{1}{1 − 3z} − \frac{1}{1 − 2z} .

Hence b_{n} = [z^{n}]B(z) = 3^{n} − 2^{n}. Now

A(z) = \frac{B(z)}{z}(2 − 5z) = \frac{2 − 5z}{(1 − 2z)(1 − 3z)} = \frac{1}{1 − 3z} + \frac{1}{1 − 2z} ,

hence a_{n} = [z^{n}]A(z) = 3^{n} + 2^{n}. The Towers of Hanoi We have 3 sticks, and n discs on one of them; they are decreasing in size from bottom to top. The exercise is to move them from stick 1 to stick 3, but never should a larger disc be on top of a smaller one. Let a_{n} be the minimal number of moves. We must free the bottom disc, using a_{n−1} moves. Then we use one move, to move the largest disc to stick 3, and then another a_{n−1} moves to complete the task. Altogether

a_{n} = 2a_{n−1} + 1, a_{0} = 0.

This is a first order recursion, and perhaps the simplest approach is this: Divide by 2^{n}, to get

\frac{a_{n}}{2^{n}} = \frac{a_{n−1}}{2^{n−1}} + \frac{1}{2^{n}} .

Now sum this from n = 1, …, N to get

\frac{a_{N}}{2^{N}} = \frac{a_{0}}{2^{0}} + ∑_{n=1}^{N} \frac{1}{2^{n}} ,

or

\frac{a_{N}}{2^{N}} = ∑_{n=1}^{N} \frac{1}{2^{n}} = \frac{1}{2} \frac{1 − 2^{−N}}{1 − \frac{1}{2}} = 1 − 2^{−N}.

Finally

a_{N} = 2^{N} − 1.

Now let us do it with our thrusty generating functions technique: Introduce

A(z) = ∑_{n≥0} a_{n}z^{n},

and write

a_{n}z^{n} = 2a_{n−1}z^{n} + z^{n}.

Sum this from n = 1, 2, …;

A(z) = 2zA(z) + \frac{z}{1 − z} ,

or

A(z) = \frac{z}{(1 − z)(1 − 2z)} = \frac{1}{1 − 2z} − \frac{1}{1 − z} .

Hence

a_{n} = 2^{n} − 1,

as before.

If we have a recursion

C_{d}a_{n+d} + C_{d−1}a_{n+d−1} + ⋯ + C_{0}a_{n} = 0,

and we do our generating function thing, we get

\frac{p(z)}{q(z)},

where

q(z) = C_{d} + zC_{d−1} + ⋯ + z^{d}C_{0}

and p(z) depends on the initial values. The reciprocals of the zeros of q(z) play a major role. They are the zeros of the reciprocal polynomial

C_{d}λ^{d} + C_{d−1}λ^{d−1} + ⋯ + C_{0}.

This polynomial is called the characteristic polynomial.

If we have only simple zeros α_{1}, …, α_{d}, then the solution is of the form

a_{n} = D_{1}α_{1}^{n} + ⋯ + D_{d}α_{d}^{n},

where the coefficients D_{1}, …, D_{d} depend on the initial values. Let us redo the Fibonacci case: The characteristic equation is

λ^{2} = λ + 1,

with solutions

\frac{1 ± \sqrt{5}}{2}.

Hence the general solution is

C_{1} (\frac{1 + \sqrt{5}}{2})^{n} + C_{2} (\frac{1 − \sqrt{5}}{2})^{n} .

The constants are computed by plugging in n = 0, 1:

0 = F_{0} = C_{1} + C_{2},
1 = F_{1} = C_{1} \frac{1 + \sqrt{5}}{2} + C_{2} \frac{1 − \sqrt{5}}{2} = \frac{C_{1} + C_{2}}{2} + \frac{\sqrt{5}}{2}(C_{1} − C_{2}).

Hence

0 = C_{1} + C_{2},
\frac{2}{\sqrt{5}} = C_{1} − C_{2}.

From this we conclude

C_{1} = \frac{1}{\sqrt{5}}, C_{2} = −\frac{1}{\sqrt{5}}.

If we have a zero of multiplicity m, then this would (in terms of generating functions) mean that we get a term

\frac{r(z)}{(1 − zα)^{m}} ,

with a polynomial r(z) of degree at most m. Expanding this using the binomial series leads to a contribution

α^{n}(C_{m−1}n^{m−1} + ⋯ + C_{0}),

where again the coefficients depend on the initial conditions.

Consider

a_{n} − 4a_{n−1} + 4a_{n−2} = 0.

The characteristic polynomial is

λ^{2} − 4λ + 4,

with 2 being a double solution. Hence the general solution is

a_{n} = 2^{n}(Cn + D).

This covers already all possible situations of homogenous linear recursions with constant coefficients. Consider the characteristic polynomial and its solutions (with multiplicities). The general solution consists of terms α^{n} × polynomial where the polynomial is of degree m − 1 if α is a zero of multiplicity m. Altogether there are d unspecified parameters if the recursion is of order d. They can be computed provided the initial values are given.

Example. Compute the general solution of the recursion

a_{n+4} − 10a_{n+3} + 32a_{n+2} − 38a_{n+1} + 15a_{n} = 0.

We consider the characteristic equation

λ^{4} − 10λ^{3} + 32λ^{2} − 38λ + 15 = 0.

Fortunately it factors as

15(1 − λ)^{2}(1 − \frac{λ}{3})(1 − \frac{λ}{5}).

Therefore the general solution is

a_{n} = An + B + C3^{n} + D5^{n}.

Inhomogenous equations can also be treated. All justifications go via the corresponding generating functions. So we merely cite the corresponding rules.

One needs a particular solution a_{n}^{P} of the linear recursion. Then the general solution is this plus the general solution of the homogenous equation. To get such a particular solution, there are several rules. First, if the extra term (usually on the right hand side) is split additively into two terms, one can do the exercise separately and add the particular solutions. If there is a term p(n)α^{n} with a polynomial p(n), and α is not a solution of the characteristic equation (the regular case), then try q(n)α^{n}, where the polynomial q(n) has the same degree as p(n), with unspecified coefficients. Plug that in and match the coefficients. If α should happen to be an r–fold solution of the characteristic equation, then modify the “ansatz” as n^{r}q(n)α^{n}.

Example.

a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = n + 1 − 5 · 2^{n} + 3^{n}.

Find the general solution. First, consider the homogenous equation

a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = 0.

The characteristic equation is

λ^{3} − 4λ^{2} + 5λ − 2 = 0.

In factored form, it is

(λ − 1)^{2}(λ − 2) = 0.

So 1 is a double and 2 is a simple solution, and the general solution of the homogenous equation is

a_{n} = An + B + C2^{n}.

For the particular solution, start with the term 3^{n}.

Take a_{n} = D3^{n} and plug it into:

a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = 3^{n} :
D3^{n+3} − 4D3^{n+2} + 5D3^{n+1} − 2D3^{n} = 3^{n},

or

D3^{3} − 4D3^{2} + 5D3 − 2D = 1,

or

D(27 − 36 + 15 − 2) = 1,

so D = \frac{1}{4}. Now treat 5 · 2^{n}. Since 2 is a simple zero, our ansatz is nE2^{n}.

Plug it into:

a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = 5 · 2^{n} :

(n + 3)E2^{n+3} − 4(n + 2)E2^{n+2} + 5(n + 1)E2^{n+1} − 2nE2^{n} = 5 · 2^{n}.

or

(n + 3)E2^{3} − 4(n + 2)E2^{2} + 5(n + 1)E2 − 2nE = 5.

The coefficient of n gives us

8E − 16E + 10E − 2E = 0,

which gives us no information; The coefficient of n^{0} gives us

24E − 32E + 10E = 5,

or E = \frac{5}{2}. Finally, treat the term n. The ansatz should be F n + G, but since 1 is a double zero, it must be modified to n^{2}(F n + G) = F n^{3} + Gn^{2}. Plug it into:

a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = n + 1 :

F (n+3)^{3}+G(n+3)^{2}−4F (n+2)^{3}−4G(n+2)^{2}+5F (n+1)^{3}+5G(n+1)^{2}−2F n^{3}−2Gn^{2} = n+1.

The coefficient of n^{3} leads to

F − 4F + 5F − 2F = 0,

so no information, and the coefficient of n^{2} leads to

9F + G − 24F − 4G + 15F + 5G − 2G = 0,

also no information. But the coefficient of n leads to

−6F = 1

and

−2G = 1.

Therefore F = −\frac{1}{6} and G = −\frac{1}{2}. So we found a particular solution

−\frac{1}{6}n^{3} − \frac{1}{2}n^{2} − \frac{5}{2}n2^{n} + \frac{1}{4}3^{n}.

The general solution is therefore

a_{n} = An + B + C2^{n} − \frac{1}{6}n^{3} − \frac{1}{2}n^{2} − \frac{5}{2}n2^{n} + \frac{1}{4}3^{n}.

If initial values would be given, say a_{0} = 0, a_{1} = 2, a_{2} = 6, then we would have to solve

0 = B + C − \frac{5}{2} + \frac{1}{4},
2 = A + B + 2C − \frac{1}{6} − \frac{1}{2} − 5 + \frac{3}{4},
6 = 2A + B + 4C − \frac{4}{3} − 2 − 10 + \frac{9}{4},

or

B + C = \frac{9}{4},
A + B + 2C = \frac{83}{12},
2A + B + 4C = \frac{205}{12}.

Hence

A = −\frac{5}{6}, B = −\frac{13}{4}, C = \frac{11}{2}.

If the characteristic equation would have complex solutions, then always also the conjugate one, and one could make the solution free from complex numbers. Quantities like sin(ρn) and cos(ρn) would then appear, where ρ is the argument of the complex root. This is nothing like the application of Euler’s formula e^{ix} = cos x + i sin x. However, we don’t go into that any further.

Let us do the Towers of Hanoi again:

a_{n} − 2a_{n−1} = 1, a_{0} = 0.

The homogenous equation is

a_{n} − 2a_{n−1} = 0.

The characteristic equation is

λ − 2 = 0,

so the general solution is

a_{n} = C2^{n}.

To find a particular solution of the inhomogenous equation we try a_{n} = D and find

D − 2D = 1,

so

a_{n} = C2^{n} − 1.

The constant C can be computed from a_{0} = 0:

0 = C − 1,

and the solution is

a_{n} = 2^{n} − 1.

We can also compute S_{n} = 1^{2} + 2^{2} + ⋯ + n^{2} in this style. Obviously, S_{n} − S_{n−1} = n^{2}, and the general solution of the homogenous equation is S_{n} = A. To find a particular solution, we try (not!) a_{n} = B + Cn + Dn^{2}, but rather (modified!) a_{n} = n(B + Cn + Dn^{2}).

a_{1} = 1 = B + C + D,
a_{2} = 5 = 2B + 4C + 8D,
a_{3} = 14 = 3B + 9C + 27D,

The solution is (of course) B = \frac{1}{6}, C = \frac{1}{2}, D = \frac{1}{3}. Finally, S_{0} = 0 gives us A = 0.

7. Binary and other trees

Binary trees are recursively defined. The symbol □ is a binary tree, called a leaf (or

external node), and if t_{1} and t_{2} are binary trees, then also ^{}t^{1} t^{2}.

Therefore the first few binary trees are

[figure: …]

The nodes of type ∘ are called internal nodes. The size of a tree is the number of internal nodes. Denote by b_{n} the number of binary trees of size n. We clearly have b_{0} = 1 and the following recursion:

b_{n+1} = b_{n}b_{0} + b_{n−1}b_{1} + … b_{1}b_{n−1} + b_{n}b_{0}.

This recursion can be translated via the generating function

B(z) := ∑_{n≥0} b_{n}z^{n} :

∑_{n≥0} b_{n+1}z^{n+1} = z ∑_{n≥0} z^{n}(b_{n}b_{0} + b_{n−1}b_{1} + … b_{1}b_{n−1} + b_{n}b_{0})

or

B(z) − 1 = zB^{2}(z).

Boundary condition is B(0) = 1.

We solve that

B(z) = \frac{1 ± \sqrt{1 − 4z}}{2z} .

Only one solution is useful, and, because of B(0) = 1 it must be

B(z) = \frac{1 − \sqrt{1 − 4z}}{2z} ,

because otherwise B(0) would not be finite.

So we found our old friends, the Catalan numbers:

b_{n} = \frac{1}{n + 1}\binom{2n}{n}.

We want a faster method to derive the equation

B(z) = 1 + zB^{2}(z).

Assume that we have objects from C × D, i. e. ordered pairs (c, d). There is a size defined for elements from C and D, and for objects from C × D we define it to be the sum of the sizes of the components. Denote by c_{n} the number of objects of size n in C and similar for d_{n}. If e_{n} the number of objects of size n in C × D, then clearly

e_{n} = c_{0}d_{n} + c_{1}d_{n−1} + ⋯ + c_{n}d_{0}.

This is just the Cauchy product for ordinary generating functions, and so (with obvious notations) E(z) = C(z)D(z).

We are in such an instance. Denote B the family of binary trees. Then it decomposes as

B = □ + B × {∘} × B,

and this translates into

B(z) = 1 + B(z) · z · B(z).

Let us consider the family of planar trees (planted plane tree, ordered trees): The recursive definitions is this: ∘ is a planar tree, and if t_{1}, …, t_{r} are planar trees, then also

[figure: …; t_{1}; t_{2}; t_{r}]

The size is the number of nodes.

Consequently we get the formal (symbolic) equation for the family P of planar trees:

[figure: …; t_{1}; t_{2}; t_{r}].

This translates into

P (z) = z + zP (z) + zP^{2}(z) + zP^{3}(z) + …,

or

P (z) = \frac{z}{1 − P (z)},

whence

P (z) − P^{2}(z) = z,

with the solutions

P (z) = \frac{1 ± \sqrt{1 − 4z}}{2} .

Since p_{0} = 0 (no tree of size 0), we find

P (z) = \frac{1 − \sqrt{1 − 4z}}{2} = ∑_{n≥1} \frac{1}{n}\binom{2n − 2}{n − 1}z^{n}.

Our old friends the Catalan numbers show up again, but shifted by one. Note that P_{n+1} = B_{n}. Can you find a natural explanation for that?

Let me consider the nonnegative paths again. The size of such a path is its length, and denote by P the family of such paths. We want to set up a symbolic equation for them. They decompose with respect to their returns to the x–axis:

P = ∅ + /P\ + /P\/P\ + /P\/P\/P\ + …

Translating,

P (z) = 1 + z^{2}P (z) + (z^{2}P (z))^{2} + (z^{2}P (z))^{3} + …

Hence

P (z) = \frac{1}{1 − z^{2}P (z)},

or

P (z) = \frac{1 − \sqrt{1 − 4z^{2}}}{2z^{2}} .

If we consider the coefficient [z^{n}]P (z), we find 0 for n odd, and \frac{1}{m+1} \binom{2m}{m} for n = 2m.

Another decomposition is with respect to the first return to the x–axis:

P = ∅ + /P\P,

and so

P (z) = 1 + z^{2}P^{2}(z),

with the same result.

Let us consider well formed parantheses, formed from (,). For example ((()())) is, but ())( is not. We must have the same number of opening and closing parantheses. Also, in every prefix, the number of closing parantheses can never be larger than the opening parantheses. Denote by P the family of these objects. Then

P = ∅ + (P)P,

and, we find

P (z) = 1 + z^{2}P^{2}(z) = \frac{1 − \sqrt{1 − 4z^{2}}}{2z^{2}} = ∑_{n≥1} \frac{1}{n}\binom{2n − 2}{n − 1}z^{2n}.

This is after all not too surprising, since we can identify these strings of (,) and the nonnegative lattice paths. (How?)

We can also perform the rotation correspondence between binary trees with n nodes

and planar trees with n + 1 nodes. I had no energy to draw that in TEX, so please take notes in class.

A correspondence between nonnegative lattice paths of length 2n and planar trees with

n + 1 nodes is also easy. I had no energy to draw that in TEX, so please take notes in class.

Assume that we have a lattice of size 2 × n (2 rows, n columns), and we want to tile it with 2 × 1 dominos in all possible ways. We denote the set of all such tilings by F. A recursion (symbolic equation is easy):

F = ϵ + |F + F.

Denote by f_{n} the number of tilings of the lattice of size 2 × n and

F (z) = ∑_{n≥0} f_{n}z^{n},

then we translate

F (z) = 1 + zF (z) + z^{2}F (z),

and

F (z) = \frac{1}{1 − z − z^{2}} .

Hence f_{n} = F_{n+1}, a Fibonacci number.

If we try this with 3 × n, we get

F = | +  F +  G +  H F + G =  G F + H =  H

Hence G(z) = H(z), and

F (z) = 1 + z^{3}F (z) + 2z^{2}G(z)
G(z) = zF (z) + z^{3}G(z),

or

F (z) = \frac{1 − z^{3}}{1 − 4z^{3} + z^{6}} = 1 + 3z^{3} + 11z^{6} + ….

Observe that we count the number of dominos. If we want n to appear in the counting, we must translate:

1 + 3z^{2} + 11z^{4} + ….

Polya’s money change problem allows a symbolic representation: Write 1 for a coin of value 1 cent, etc, then

(ϵ + 1 + 1 1 + …)(ϵ + 5 + 5 5 + …)(ϵ + 25 + 25 25 + …)(ϵ + 50 + 50 50 + …)

describes the whole problem, with translation into generating functions

\frac{1}{1 − z} \frac{1}{1 − z^{5}} \frac{1}{1 − z^{25}} \frac{1}{1 − z^{50}} .

If we allow coins of all sizes 1, 2, …, then we obtain partitions. A representation of

n = i_{1} + i_{2} + ⋯ + i_{k}

with natural numbers i_{s}, such that i_{1} ≥ i_{2} ≥ ⋯ ≥ i_{k} is called a partition. The number k is called the number of parts of the partition. And p(n) is the number of partitions of n. We have

∑_{n≥0} p(n)z^{n} = ∏_{k≥1} \frac{1}{1 − z^{k}} .

Here is an example:

7 61 52 511 43 421 4111 331 322 3211 31111 2221 22111 211111 1111111

We want to generate such a list. What is the principle?!

Write n = r_{1} + ⋯ + r_{k}, with r_{1} ≥ ⋯ ≥ r_{k}. If r_{k} > 1, then replace it by (r_{k−1} − 1)1. Take R_{s}11 … 1 and replace it by (R_{s} − 1) … (R_{s} − 1)t, where t is the “rest.”

How is the principle if we want this list in reversed order? If we have the smallest number several times, like aa … a, replace it by (a + 1)11 … 1. This is only impossible when it is single. Then we take bb … ba, with b the second smallest number and replace it by (b + 1)11 … 1.

The last symbolic equation deals with a regular n–gon and partitions of it into triangles via diagonals. In how many ways is it possible? Of course, we get n − 2 triangles. Let us think about the vertices 1 and 2, say, and the triangle having the side \overline{12}. It leaves us with two smaller m–gons, and the size (number of triangles!) is additive. Hence

D = | + D△D,

where | stands for no triangle. Translating, we have

D(z) = 1 + zD^{2}(z),

and thus

D(z) = ∑_{n≥0} \frac{1}{n + 1}\binom{2n}{n}z^{n},

with the Catalan numbers. This was known to Euler.

8. Bernoulli numbers

If a_{0}, a_{1}, … is a sequence, the associated exponential generating function is defined by

A(z) = ∑_{n≥0} a_{n} \frac{z^{n}}{n!} .

The multiplication of two exponential generating function goes like this:

A(z)B(z) = ∑_{n≥0} \frac{a_{n}}{n!} z^{n} · ∑_{n≥0} \frac{b_{n}}{n!}z^{n}

= ∑_{n≥0} ( ∑_{k=0}^{n} \frac{a_{k}b_{n−k}}{k!(n − k)!})z^{n}

= ∑_{n≥0} ( ∑_{k=0}^{n} \binom{n}{k}a_{k}b_{n−k})\frac{z^{n}}{n!} .

The Bernoulli numbers B_{n} are defined by the exponential generating function

∑_{n≥0} B_{n} \frac{z^{n}}{n!} = \frac{z}{e^{z} − 1}

so that the first few values are 1, −\frac{1}{2}, \frac{1}{6}, 0, −\frac{1}{30}, 0, \frac{1}{42}, 0, −\frac{1}{30}, . . .. We may write

(e^{z} − 1) ∑_{n≥0} B_{n} \frac{z^{n}}{n!} = z

and compare coefficients:

∑_{k=1}^{n} \binom{n}{k}B_{n−k} = δ_{n1}

or, better,

∑_{k=0}^{n−1} \binom{n}{k}B_{k} = δ_{n1}.

Of course, also,

∑_{k=0}^{n} \binom{n}{k}B_{k} = B_{n} + δ_{n1}.

The Bernoulli polynomials B_{m}(x) are defined as

B_{m}(x) = ∑_{k=0}^{m} \binom{m}{k}B_{k}x^{m−k}.

One notes immediately that B_{m}(0) = B_{m}, but also that

B_{m}(1) = ∑_{k=0}^{m} \binom{m}{k}B_{k} = B_{m} + δ_{m1}.

The exponential generating function is

∑_{m≥0} \frac{z^{m}}{m!} ∑_{k=0}^{m} \binom{m}{k}B_{k}x^{m−k} = ∑_{k≥0} \frac{B_{k}}{k!} ∑_{m≥k} \frac{z^{m}}{(m − k)!}x^{m−k}

= ∑_{k≥0} \frac{B_{k}}{k!} z^{k} ∑_{m≥0} \frac{z^{m}}{m} x^{m}

= \frac{z}{e^{z} − 1}e^{zx} = \frac{ze^{zx}}{e^{z} − 1}.

Now let us come back to

S_{m} = S_{m}(n) = ∑_{0≤k<n} k^{m}.

Consider the exponential generating function

f(z) = ∑_{m≥0} S_{m} \frac{z^{m}}{m!}

= ∑_{m≥0} ∑_{0≤k<n} k^{m} \frac{z^{m}}{m!}

= ∑_{0≤k<n} ∑_{m≥0} \frac{(kz)^{m}}{m!}

= ∑_{0≤k<n} e^{kz}

= \frac{e^{nz} − 1}{e^{z} − 1}.

Therefore

S_{m}(n) = m![z^{m}]f(z)

= m![z^{m}]\frac{e^{nz} − 1}{e^{z} − 1}

= m![z^{m+1}]\frac{z(e^{nz} − 1)}{e^{z} − 1}

= m!\frac{1}{(m + 1)!}(B_{m+1}(n) − B_{m+1})

= \frac{1}{m + 1}(B_{m+1}(n) − B_{m+1}).

In just a few lines we got a closed formula!

Let us derive some conseqences.

\frac{z}{e^{z} − 1} + \frac{z}{2} = \frac{z}{2} \frac{e^{z} + 1}{e^{z} − 1} = \frac{z}{2} \frac{e^{z/2} + e^{−z/2}}{e^{z/2} − e^{−z/2}} = \frac{z}{2} coth \frac{z}{2}.

Hence

z coth z = \frac{2z}{e^{2z} − 1} + z = ∑_{n≥0} B_{2n} \frac{(2z)^{2n}}{(2n)!} = ∑_{n≥0} 4^{n}B_{2n} \frac{z^{2n}}{(2n)!}.

Remember

sin z = −i sinh iz, cos z = cosh iz,

and

cot z = \frac{cos z}{sin z} = i\frac{cosh iz}{sinh iz} = i coth iz.

So

z cot z = ∑_{n≥0} B_{2n} \frac{(2iz)^{2n}}{(2n)!} = ∑_{n≥0}(−4)^{n}B_{2n} \frac{z^{2n}}{(2n)!}.

Bernoulli numbers also appear in the coefficients of the tangent function

tan z = \frac{sin z}{cos z} = ∑_{n≥0}(−1)^{n−1}4^{n}(4^{n} − 1)B_{2n} \frac{z^{2n−1}}{(2n)!} .

Here is why: Note that

\frac{z}{e^{z} + 1} = \frac{z}{e^{z} − 1} − \frac{2z}{e^{2z} − 1} = ∑_{n≥0}(1 − 2^{n})B_{n} \frac{z^{n}}{n!} .

This means that tan z = cot z − 2 cot 2z (why?), and we conclude

tan z = cot z − 2 cot 2z

= ∑_{n≥0}(−4)^{n}B_{2n} \frac{z^{2n−1}}{(2n)!} − ∑_{n≥0}(−4)^{n}4^{n}B_{2n} \frac{z^{2n−1}}{(2n)!} ,

and this is our formula. Let us define the Tangent numbers by

T_{2n−1} = (−1)^{n−1} \frac{4^{n}(4^{n} − 1)}{2n}B_{2n},

so that

tan z = ∑_{n≥1} T_{2n−1} \frac{z^{2n−1}}{(2n − 1)!}.

We prove that these numbers are integers, as follows: Set

\frac{sin z + x cos z}{cos z − x sin z} := ∑_{n≥0} T_{n}(x)\frac{z^{n}}{n!} ,  (1)

and T_{n} = T_{n}(0). We differentiate (1) with respect to x:

\frac{1}{(cos z − x sin z)^{2}} = ∑_{n≥0} T′_{n}(x)\frac{z^{n}}{n!} ;

however, if we differentiate (1) with respect to z, we get

\frac{1 + x^{2}}{(cos z − x sin z)^{2}} = ∑_{n≥1} T_{n}(x)\frac{z^{n−1}}{(n − 1)!} = ∑_{n≥0} T_{n+1}(x)\frac{z^{n}}{n!} .

Therefore

T_{n+1}(x) = (1 + x^{2})T′_{n}(x), T_{0}(x) = x.

From this we see that the coefficients of T_{n}(x) must be nonnegative integers.

Here is another formula involving Bernoulli numbers:

\frac{z}{sin z} = z cot z + z tan \frac{z}{2}  (check!)

= ∑_{n≥0}(−4)^{n}B_{2n} \frac{z^{2n}}{(2n)!} + 2 ∑_{n≥0}(−1)^{n−1}(4^{n} − 1)B_{2n} \frac{z^{2n}}{(2n)!}

= ∑_{n≥0}(−1)^{n−1}[2 · 4^{n} − 2 − 4^{n}]B_{2n} \frac{z^{2n}}{(2n)!}

= ∑_{n≥0}(−1)^{n−1}(4^{n} − 2)B_{2n} \frac{z^{2n}}{(2n)!}.

The last one: Note that

\frac{d}{dz} log sin z = cot z, \frac{d}{dz} log cos z = − tan z.

Now

log \frac{tan z}{z} = log \frac{sin z}{z} − log cos z

= ∑_{n≥1}(−1)^{n} \frac{4^{n}B_{2n}z^{2n}}{(2n)(2n)!} − ∑_{n≥1}(−1)^{n} \frac{4^{n}(4^{n} − 1)B_{2n}z^{2n}}{(2n)(2n)!}

= ∑_{n≥1}(−1)^{n−1} \frac{4^{n}(4^{n} − 2)B_{2n}z^{2n}}{(2n)(2n)!} .

9. Eulerian numbers

They are denoted by

\left⟨{n \atop k}\right⟩

and count the number of permutations π_{1} … π_{n} with k ascents. (Places with π_{i} < π_{i+1}.) We list the permutations of 3 elements and the number of ascents:

123  2
132  1
213  1
231  1
312  1
321  0

Simple observations: n− the number of ascents equals the number of ascending runs. Also: n − 1− number of ascents = number of descents. 1+ number of descents = number of ascending runs.

There is a trivial symmetry (by reflection, π_{n} … π_{1}):

\left⟨{n \atop k}\right⟩ = \left⟨{n \atop n − 1 − k}\right⟩.

And now we want to find a recursion:

We have a permutation ρ_{1} … ρ_{n−1} and insert the number n in all possible ways. Assume that we do it in position j:

π = ρ_{1} … ρ_{j−1}nρ_{j+1} … ρ_{n−1}.

If j = 1 or ρ_{j−1} < ρ_{j} then the number of ascents is the same. If j = n or ρ_{j−1} > ρ_{j} it is one greater than before. This gives us

\left⟨{n \atop k}\right⟩ = (k + 1)\left⟨{n − 1 \atop k}\right⟩ + (n − k)\left⟨{n − 1 \atop k − 1}\right⟩.

Note that n − k = (n + 1) − (k + 1) = 1 + (n − 2) − (k − 1).

As boundary condition we have \left⟨{0 \atop k}\right⟩ = δ_{k0}. Note also \left⟨{n \atop n}\right⟩ = δ_{n0}.

Produce a small table as an exercise.

Now we are going to prove Worpitzky’s identity.

x^{n} = ∑_{k} \left⟨{n \atop k}\right⟩\binom{x + k}{n}.

x^{1} = \binom{x}{1}
x^{2} = \binom{x}{2} + \binom{x + 1}{2}
x^{3} = \binom{x}{3} + 4\binom{x + 1}{3} + \binom{x + 2}{3}, …

Claim:

x\binom{x + k}{n} = (k + 1)\binom{x + k}{n + 1} + (n − k)\binom{x + k + 1}{n + 1}.

Dividing by \binom{x+k}{n} this means

x = (k + 1)\frac{x + k − n}{n + 1} + (n − k)\frac{x + k + 1}{n + 1},

or

(n + 1)x = (k + 1)(x + k − n) + (n − k)(x + k + 1),

which is easily seen to be true. Now our identity follows by induction; the induction step is this:

x^{n+1} = xx^{n} = x ∑_{k} \left⟨{n \atop k}\right⟩\binom{x + k}{n}

= ∑_{k}(k + 1)\left⟨{n \atop k}\right⟩\binom{x + k}{n + 1} + ∑_{k}(n − k)\left⟨{n \atop k}\right⟩\binom{x + k + 1}{n + 1}

= ∑_{k}(k + 1)\left⟨{n \atop k}\right⟩\binom{x + k}{n + 1} + ∑_{k}(n + 1 − k)\left⟨{n \atop k − 1}\right⟩\binom{x + k}{n + 1}

= ∑_{k} [(k + 1)\left⟨{n \atop k}\right⟩ + (n + 1 − k)\left⟨{n \atop k − 1}\right⟩]\binom{x + k}{n + 1}

= ∑_{k} \left⟨{n + 1 \atop k}\right⟩\binom{x + k}{n + 1},

as desired.

10. Classical proof of the Saalschütz identity

[This is a filler and might be left out.]

As a prototype of many formulæ involving binomial coefficients we provide a proof of Saalschütz’ identity (sometimes “Pfaff–Saalschütz”).

For m, n integers:

∑_{k} \binom{m − r + s}{k}\binom{n + r − s}{n − k}\binom{r + k}{m + n} = \binom{r}{m}\binom{s}{n}.

Proof:

S = ∑_{k} \binom{m − r + s}{k}\binom{n + r − s}{n − k}\binom{r + k}{m + n}

= ∑_{k} \binom{m − r + s}{k}\binom{n + r − s}{n − k} ∑_{j} \binom{r}{m + n − j}\binom{k}{j}

= ∑_{j} ∑_{k} \binom{n + r − s}{n − k}\binom{r}{m + n − j}\binom{m − r + s}{k}\binom{k}{j}

= ∑_{j} ∑_{k} \binom{n + r − s}{n − k}\binom{r}{m + n − j}\binom{m − r + s}{j}\binom{m − r + s − j}{k − j}

= ∑_{j} \binom{r}{m + n − j}\binom{m − r + s}{j} ∑_{k} \binom{n + r − s}{n − k}\binom{m − r + s − j}{k − j}

= ∑_{j} \binom{m − r + s}{j}\binom{r}{m + n − j}\binom{n + m − j}{n − j}

= \binom{r}{m} ∑_{j} \binom{m − r + s}{j}\binom{r − m}{n − j}

= \binom{r}{m}\binom{s}{n}.

11. Binomial Sequences

Definition. A polynomial sequence is a family {p_{n}(x) | n ∈ ℕ_{0}} of real polynomials such that deg(p_{n}(x)) = n for all n, with the convention that deg(a) = 0 for a constant a ≠ 0, but deg(0) = −1.

Such a polynomial sequence is a basis of the vector space ℝ[x].

Definition. A polynomial sequence p_{n}(x) is called binomial if

p_{0}(x) = 1, p_{n}(x + y) = ∑_{k=0}^{n} \binom{n}{k}p_{k}(x)p_{n−k}(y)

for all x, y ∈ ℝ. Examples are the ordinary polynomials x^{n}, but also x\underline{n}, since

(x + y)\underline{n} = ∑_{k=0}^{n} \binom{n}{k}x\underline{k}y\underline{n−k}

is equivalent to

\binom{x + y}{n} = ∑_{k=0}^{n} \binom{x}{k}\binom{y}{n − k},

which is the traditional Vandermonde convolution. We want to decide easily whether a given sequence is binomial. For that we need more definitions. Definition. A polynomial sequence p_{n}(x) is called normalized if

p_{0}(x) = 1, p_{n}(0) = 0 (n ≥ 1).

A binomial sequence is normalized; the converse is false. A counterexample is {1, x, 2x^{2}, x^{3}, x^{4}, … }, since

p_{2}(x + y) = 2(x + y)^{2} = 2(x^{2} + 2xy + 2y^{2})

but

p_{0}(x)p_{2}(y) + 2p_{1}(x)p_{1}(y) + p_{2}(x)p_{0}(y) = 2y^{2} + 2xy + 2x^{2}.

For the easy proof, plug in x = y = 0:

p_{n}(0) = ∑_{k=0}^{n} \binom{n}{k}p_{k}(0)p_{n−k}(0).

For instance,

p_{1}(0) = p_{1}(0) + p_{1}(0),

and we have the result for n = 1. Assume that we know it for all values < n, then

p_{n}(0) = p_{n}(0) + p_{n}(0),

and we have it for n.

A linear transformation of the vector space ℝ[x] into itself is called a polynomial operator. Such an operator P is called of differential type is

deg(P p(x)) = deg(p(x)) − 1 ∀p(x) ∈ ℝ[x].

(All constant polynomials are mapped to 0.)

To every polynomial sequence there exists a unique polynomial operator such that

P p_{0}(x) = 0 P p_{n}(x) = np_{n−1}(x) for n ≥ 1.  (2)

(A linear operator is uniquely defined when we give its values at a basis.) The operator P is called the basis operator of {p_{n}(x)}.

Conversely, if an operator P is given and (2) is satisfied, the sequence is called a basis sequence of P.

Theorem 1. • Any polynomial sequence possesses a unique basis operator; this op-

erator is of differential type.

• Any differential operator possesses a unique normalized basis sequence.

• The correspondence basis operator ⟷ basis sequence is a bijection between the set of differential operators and the set of normalized sequences.

Proof. Most statements are clear. Let us construct a normalized basis sequence p_{n}(x) provided the differential operator P is given: Set p_{0}(x) = 1 and

p_{1}(x) = \frac{x}{P x}.

Then

P p_{1}(x) = \frac{1}{P x}P x = 1.

Now assume that the polynomials p_{0}(x), …, p_{n−1}(x) have already been defined. Note that P x^{k} is a linear combination of p_{0}(x), …, p_{k−1}(x). Setting

P (x) = ∑_{k=1}^{n} a_{k}x^{k}

and noting that

P p_{n}(x) = ∑_{k=1}^{n} a_{k}P x^{k} = np_{n−1}(x)

we can thus compute the coefficients a_{k} by comparing coefficients. The basis operator to x^{n} is D (ordinary differentiation). Let us compute the basis operator related to x\underline{n}:

(x + 1)\underline{n} − x\underline{n} = x\underline{n−1} [x + 1 − (x − n + 1)] = nx\underline{n−1},

and so we found it; we denote it as

Δ = E − I,

where E is the shift (translation) operator, defined by Ef(x) = f(x + 1). More generally, E^{a}f(x) = f(x + a) and I = E^{0}. Similarly, ▽ = I − E^{−1} is the basis operator related to x\overline{n} (check!). They are called (forward, backward) difference operators. Theorem 2. Let p_{n}(x) be a normalized sequence with basis operator P. The (unique) representation of a general polynomial q(x) is obtained via

q(x) = ∑_{k≥0} \frac{[P^{k}q(x)]_{x=0}}{k!} p_{k}(x).

Proof. By linearity, it is sufficient to show the theorem for a basis of polynomials, say for the p_{n}(x)’s: We see that

P^{k}p_{n}(x) = n\underline{k}p_{n−k}(x)

and therefore

[P^{p}k_{n}(x)]_{x=0} = n\underline{k}[p_{n−k}(x)]_{x=0} = δ_{nk} · n!.

Hence

p_{n}(x) = ∑_{k≥0} \frac{[P^{k}p_{n}(x)]_{x=0}}{k!} p_{k}(x).

Example.

q(x) = ∑_{k≥0} \frac{q^{(k)}(0)}{k!}x^{k},

which is the usual Taylor expansion. Now compute

Δ^{k} = (E − I)^{k} = ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}E^{i}

and so

q(x) = ∑_{k≥0} \frac{∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}q(i)}{k!}x\underline{k}.

The special instance q(x) = x^{n} is nice: We know already

x^{n} = ∑_{k≥0} \left\{{n \atop k}\right\}x\underline{k}.

Therefore

\left\{{n \atop k}\right\} = \frac{1}{k!} ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}i^{n}.

The other formula is

q(x) = ∑_{k≥0} \frac{∑_{i=0}^{k}(−1)^{i}\binom{k}{i}q(−i)}{k!}x\overline{k}.

We need the linear functional L^{a}p(x) := p(a) (evaluation at x = a). In particular L := L^{0}. The expansion

q(x) = ∑_{k≥0} \frac{LP^{k}q(x)}{k!}p_{k}(x)

is in operator notation

I = ∑_{k≥0} \frac{p_{k}(x)}{k!}LP^{k}.

There are no convergence problems, since we apply it only to polynomials, and thus almost all the terms are zero. A polynomial operator P is called shift invariant if for all real a we have P E^{a} = E^{a}P. If in addition we have P x = c ≠ 0, it is called a Delta operator.

The main theorem is this:

Theorem 3. A polynomial sequence is binomial iff its basis operator is a Delta operator.

Proof. Let p_{n}(x) be a binomial sequence with basis operator P. Since P is of differential type we have P x = c ≠ 0. To verify the shift invariance of P we need only consider the basis polynomials p_{n}(x). For n = 0 there is nothing to prove, so assume n ≥ 1.

We have

E^{y}p_{n}(x) = p_{n}(x + y)

= ∑_{k≥0} \binom{n}{k}p_{n−k}(y)p_{k}(x)

= ∑_{k≥0} \frac{L^{y}P^{k}p_{n}(x)}{k!}p_{k}(x)

= ∑_{k≥0} \frac{LE^{y}P^{k}p_{n}(x)}{k!}p_{k}(x).

Therefore

E^{y}P p_{n}(x) = E^{y}np_{n−1}(x)

= ∑_{k≥0} \frac{LE^{y}P^{k}np_{n−1}(x)}{k!}p_{k}(x)

= ∑_{k≥0} \frac{LE^{y}P^{k+1}p_{n}(x)}{k!}p_{k}(x)

= ∑_{k≥1} \frac{LE^{y}P^{k}p_{n}(x)}{k!}kp_{k−1}(x)

= P ( ∑_{k≥1} \frac{LE^{y}P^{k}p_{n}(x)}{k!}p_{k}(x))

= P E^{y}p_{n}(x).

Now let P be a Delta operator. It is easily verified that P is of differential type. Apply the expansion formula to p_{n}(x + y) (as a polynomial in x):

p_{n}(x + y) = ∑_{k=0}^{n} \frac{LP^{k}p_{n}(x + y)}{k!}p_{k}(x)

= ∑_{k=0}^{n} \frac{LP^{k}E^{y}p_{n}(x)}{k!}p_{k}(x)

= ∑_{k=0}^{n} \frac{LE^{y}P^{k}p_{n}(x)}{k!}p_{k}(x)

= ∑_{k=0}^{n} \frac{LE^{y}n\underline{k}p_{n−k}(x)}{k!}p_{k}(x)

= ∑_{k=0}^{n} \binom{n}{k}p_{n−k}(y)p_{k}(x).

Examples. The operators D, Δ, ▽ are all shift invariant. Hence they are all Delta operators, and we get

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k},

(x + y)\underline{n} = ∑_{k=0}^{n} \binom{n}{k}x\underline{k}y\underline{n−k},

(x + y)\overline{n} = ∑_{k=0}^{n} \binom{n}{k}x\overline{k}y\overline{n−k}.

A less well known example are operators E^{a}D (Abel operators). The associated sequence is x(x − an)^{n−1}. Let us quickly check that.

E^{a}Dx(x − an)^{n−1} = E^{a}((x − an)^{n−1} + (n − 1)x(x − an)^{n−2})
= E^{a}(x − an)^{n−2}((x − an) + (n − 1)x)
= E^{a}(x − an)^{n−2}n(x − a)
= (x + a − an)^{n−2}nx
= np_{n−1}(x).

Hence

(x + y)(x + y − an)^{n−1} = ∑_{k=0}^{n} \binom{n}{k}x(x − ak)^{k−1}y(y − a(n − k))^{n−k−1}.

We know that

(f(x)g(x))^{(n)} = ∑_{k=0}^{n} \binom{n}{k}f^{(k)}(x)g^{(n−k)}(x).

For the difference operator Δ it looks like

Δ^{n}(f(x)g(x)) = ∑_{k=0}^{n} \binom{n}{k}(Δ^{k}f(x))(Δ^{n−k}g(x + k)).

We prove that by induction. The instance n = 0 is clear, and for n = 1 we have

f(x + 1)g(x + 1) − f(x)g(x) = f(x)(g(x + 1) − g(x)) + (f(x + 1) − f(x))g(x + 1),

which is obviously correct. And now

Δ^{n+1}(f(x)g(x)) = ΔΔ^{n}(f(x)g(x))

= Δ ∑_{k=0}^{n} \binom{n}{k}(Δ^{k}f(x))(Δ^{n−k}g(x + k))

= ∑_{k=0}^{n} \binom{n}{k} [(Δ^{k}f(x))(Δ^{n+1−k}g(x + k)) + (Δ^{k+1}f(x))(Δ^{n−k}g(x + k + 1))]

= ∑_{k=0}^{n} \binom{n}{k}(Δ^{k}f(x))(Δ^{n+1−k}g(x + k)) + ∑_{k=0}^{n} \binom{n}{k}(Δ^{k+1}f(x))(Δ^{n−k}g(x + k + 1))

= ∑_{k=0}^{n} \binom{n}{k}(Δ^{k}f(x))(Δ^{n+1−k}g(x + k)) + ∑_{k=1}^{n+1} \binom{n}{k − 1}(Δ^{k}f(x))(Δ^{n+1−k}g(x + k))

= ∑_{k=0}^{n+1} \binom{n + 1}{k}(Δ^{k}f(x))(Δ^{n+1−k}g(x + k)).

Let us consider the family S of shift invariant operators in more detail. Claim: Let P_{1}, P_{2} ∈ S, then P_{1} = P_{2} iff LP_{1} = LP_{2}. (Two operators are equal if they act identically on all polynomials.) Proof: One direction is trivial, and for the other we do this for all y ∈ ℝ.

LP_{1} = LP_{2} ⟹ LP_{1}E^{y} = LP_{2}E^{y} ⟹ LE^{y}P_{1} = LE^{y}P_{2} ⟹ L^{y}P_{1} = L^{y}P_{2} ⟹ P_{1} = P_{2}.

The following expansion theorem is very impressive: Let p ∈ S, then

P = ∑_{k≥0} \frac{a_{k}}{k!} D^{k},

with a_{k} = [P x^{k}]_{x=0} for all k. (And each operator ∑_{k≥0} \frac{a_{k}}{k!} D^{k} is of course in S.) Note first that convergence is never an issue, since operators act on polynomials, and so almost all terms are always zero. It is sufficient to show that operators LP and L ∑_{k≥0} \frac{a_{k}}{k!} D^{k} yield the same result, applied to x^{n} for all n (basis!). Note that LP x^{n} = a_{n}, and

L ∑_{k≥0} \frac{a_{k}}{k!} D^{k}x^{n} = L ∑_{k=0}^{n} \frac{a_{k}}{k!} D^{k}x^{n} = \frac{a_{n}}{n!} n! = a_{n}.

It is also easy to see that two different series are different as operators (find a suitable polynomial such that they differ). So we associate to each operator P = p(D) ∈ S the power series p(t) and call it the indicator of P. The following statements are clear:

deg(P q(x)) ≤ deg(q(x))∀q(x) ∈ ℝ[x],
P is invertible ⟺ a_{0} ≠ 0 ⟺ deg(P q(x)) = deg(q(x)) ∀q(x) ∈ ℝ[x],

P is a Delta operator ⟺ a_{0} = 0, a_{1} ≠ 0 ⟺ P = DT where T ∈ S and T is invertible.

It is perhaps worthwhile to repeat from a calculus course that

y = ∑_{k≥0} a_{k}x^{k}

is invertible iff a_{0} ≠ 0; if

p(t) = a_{0} + a_{1}t + a_{2}t^{2} + …,

then

\frac{1}{p(t)} = \frac{1}{a_{0}} − \frac{a_{1}}{a_{0}^{2}} t + \frac{−a_{2}a_{0} + a_{1}^{2}}{a_{0}^{3}} t^{2} + ….

The operator with indicator p′(t) is called the derivative of P. Standard formulæ for differentiation translate to this instance.

The operator \underline{x} is defined by

\underline{x} : p(x) → xp(x).

Proposition: For P ∈ S, we have P′ = P \underline{x} − \underline{x}P. Proof: Note that \underline{x}E^{a} = E^{a}\underline{(x − a)}; with that it is easy to check that P \underline{x} − \underline{x}P ∈ S. Now

P = ∑_{k≥0} \frac{a_{k}}{k!} D^{k} with a_{k} = LP x^{k}.

Hence

P′ = ∑_{k≥1} \frac{LP x^{k}}{(k − 1)!}D^{k−1}.

Note that L\underline{x}P = 0. Hence

P \underline{x} − \underline{x}P = ∑_{k≥0} \frac{L(P \underline{x} − \underline{x}P)x^{k}}{k!} D^{k} = ∑_{k≥0} \frac{LP \underline{x}x^{k}}{k!} D^{k} = ∑_{k≥1} \frac{LP x^{k}}{(k − 1)!}D^{k−1} = P′.

Example. For the shift operator E^{a} we have

E^{a} = ∑_{k≥0} \frac{LE^{a}x^{k}}{k!} D^{k} = ∑_{k≥0} \frac{a^{k}}{k!} D^{k} = e^{aD}.

(This produces the Taylor expansion of p(x + a). Therefore

Δ = e^{D} − I, ▽ = I − e^{−D}, (E^{a})′ = aE^{a}, Δ′ = E, ▽′ = E^{−1}.

Rodrigues’ formula: (P = DT is a Delta operator.)

p_{n}(x) = x(P′)^{−1}p_{n−1}(x), n ≥ 1, p_{0}(x) = 1.

For the proof note that P′ is an invertible shift invariant operator; thus the polynomials as defined above form a normalized sequence. We prove by induction that P p_{n}(x) = np_{n−1}(x). Notice first that

P \underline{x}(P′)^{−1} = (\underline{x}P + P′)(P′)^{−1} = \underline{x}P (P′)^{−1} + I.

Recall that shift invariant operators commute.

P p_{n}(x) = P x(P′)^{−1}p_{n−1}(x)
= (\underline{x}P (P′)^{−1} + I)p_{n−1}(x)
= \underline{x}P (P′)^{−1}p_{n−1}(x) + p_{n−1}(x)
= \underline{x}(P′)^{−1}P p_{n−1}(x) + p_{n−1}(x)
= \underline{x}(P′)^{−1}(n − 1)p_{n−2}(x) + p_{n−1}(x)
= (n − 1)p_{n−1}(x) + p_{n−1}(x)
= np_{n−1}(x).

Steffensen’s formula: (P = DT is a Delta operator.)

p_{n}(x) = xT^{−n}x^{n−1}, n ≥ 1, p_{0}(x) = 1.

Proof.

\underline{x}T^{−n+1} = T^{−n+1}\underline{x} − (T^{−n+1})′
= T^{−n+1}\underline{x} + (n − 1)T^{−n}T′
= T^{−n}(T \underline{x} + (n − 1)T′).

We use Rodrigues’ formula and induction:

p_{n}(x) = \underline{x}(P′)^{−1}p_{n−1}(x)
= \underline{x}(P′)^{−1}xT^{−n+1}x^{n−2}
= \underline{x}(P′)^{−1}T^{−n}(T \underline{x} + (n − 1)T′)x^{n−2}
= \underline{x}(P′)^{−1}T^{−n}(T + T′D)x^{n−1}
= \underline{x}(P′)^{−1}T^{−n}P′x^{n−1}
= \underline{x}(P′)^{−1}P′T^{−n}x^{n−1}
= \underline{x}T^{−n}x^{n−1}.

Wow! Example. Consider the Abel operator P = DE^{a}. Thus T = E^{a}, and

p_{n}(x) = xE^{−an}x^{n−1} = x(x − an)^{n−1}.

For P = Δ we know already that Δ′ = E. Hence p_{n}(x) = xE^{−1}p_{n−1}(x) = xp_{n−1}(x − 1) = ⋯ = x\underline{n}.

If you want to know more about that, consult the book by Aigner, Combinatorial Theory (Classics in Mathematics, Springer).

12. The Prüfer code

We consider n vertices (points, nodes), and label them, most conveniently by the numbers 1, 2, …, n. Edges (a, b) connect (some) nodes a ≠ b. If one can reach each node from each node by walking along edges in a unique way, we speak about a tree. (Often people say: connected and without circles. We want, however, keep the graph theoretic terminology to a minimum.) Here are all trees (in the above sense) with 3 nodes:

[figure: 1; 2; 3; 1; 2; 3; 1; 2; 3]

We ask the (natural) question about the number of such trees, when we have n nodes. A few experiments display the numbers 1, 1, 2, 16, 125, …, so that we are tempted to believe in the formula n^{n−2}. We additionally mark one node (a “root”), and should then prove the formula n^{n−1} for these rooted labelled trees. Sometimes they are called oriented trees, since one can orient all edges away from the root.

The elegant and simple method of proof is due to Prüfer.

There are obviously n^{n−1} sequences a_{1} … a_{n−1} where a_{i} ∈ {1, 2, …, n}.

We are constructing a bijection between trees and sequences.

“Endnodes” have degree 1 (the root is never an endnode). Choose the endnode with smallest number, write its adjacent node, erase it. Do this again.

10 3  4  9 1  2  5  8 6  7 root →

So the first endnode is 1, and we write 3, and erase 1. Then the endnode is 2, and we write 3, and erase 2. Then the endnode is 2, and we write 10, and erase 3, etc.

In this way, we get the sequence 3, 3, 10, 10, 9, 8, 8, 9, 10.

From this sequence the rooted tree can be reconstructed, by constructing another sequence b_{1} … b_{n−1}. Let b_{1} be the smallest number not in {a_{1}, …, a_{n−1}}, then b_{2} different from b_{1} the smallest number not in {a_{2}, …, a_{n−1}}, then b_{3} different from b_{1} and b_{2} not in {a_{3}, …, a_{n−1}}, etc. The edges are then (a_{1}, b_{1}), …, (a_{n}, b_{n}).

13. The matrix tree theorem

There is a more general “method” to get the previous formula and more.

We have nodes v_{1}, …, v_{n}, and some edges (v_{i}, v_{j}) for i ≠ j. Such an object is called a labelled graph G .

A tree on the nodes v_{1}, …, v_{n} having some of the edges of G is called a spanning tree. We ask for the number of spanning trees. If G is the complete graph, having all \binom{n}{2} edges, then we should get n^{n−2} spanning trees. The matrix tree theorem allows us to do this computation.

Consider the following (connected) graph. (For a not connected graph the quest for spanning trees is somewhat useless.)

v_{1}  v_{2} v_{4}  v_{3}

The adjacency matrix A is labelled by the vertices v_{1}, …, v_{n} and has a 1 in position (i, j) iff there is an edge (v_{i}, v_{j}).

In our instance

A = [\begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}] .

The degree matrix D has only nonzero entries in the main diagonal, and d_{i} is the degree of node v_{i} (number of edges having v_{i} as one point). Here

D = [\begin{matrix}3 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 2 \end{matrix}] .

Finally one defines the matrix M := D − A.

Now Kirchhoff’s^{1} matrix tree theorem produces the number of spanning trees as follows: Erase one row and one column from M (ad libidum!), compute the determinant, and that’s it!

I don’t prove it in this course. I did it in 1998/1999, but it was not a great success. If you are interested, every better book has such a proof.

Our example:

1In South Africa, this name is more familar as a producer of grass seeds and the like.

M = [\begin{matrix}3 & −1 & −1 & −1 \\ −1 & 2 & −1 & 0 \\ −1 & −1 & 3 & −1 \\ −1 & 0 & −1 & 2 \end{matrix}] .

Erase the first row and column (try to make your life as easy as possible):

[\begin{matrix}2 & −1 & 0 \\ −1 & 3 & −1 \\ 0 & −1 & 2 \end{matrix}] .

The determinant is 8. Exercise: Draw all 8 spanning trees. Now let us prove the formula n^{n−2} again (often it is attributed to Cayley^{2}). The matrix M is now

M = [\begin{matrix}n − 1 & −1 & … & −1 \\ −1 & n − 1 & … & −1 \\ ⋮ & ⋮ & ... & ⋮ \\ −1 & −1 & … & n − 1 \end{matrix}] .

After erasing, say, the first row and column, it still looks like

[\begin{matrix}n − 1 & −1 & … & −1 \\ −1 & n − 1 & … & −1 \\ ⋮ & ⋮ & ... & ⋮ \\ −1 & −1 & … & n − 1 \end{matrix}] ,

but it is only an (n − 1) × (n − 1) matrix. Subtract the first row from each other row:

[\begin{matrix}n − 1 & −1 & −1 & … & −1 \\ −n & n & 0 & … & 0 \\ −n & 0 & n & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ −n & 0 & 0 & … & n \end{matrix}] ,

2Although Cayley wrote close to 1000 research papers, he worked for about 12 years as a lawyer, but at least not in mathematics of finance!

and now add all the other columns to the first column:

[\begin{matrix}1 & −1 & −1 & … & −1 \\ 0 & n & 0 & … & 0 \\ 0 & 0 & n & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & … & n \end{matrix}];

the result is a triangular matrix with determinant n^{n−2}.

Exercise. Consider two sets A, B of vertices, of m resp. n vertices. Each vertex from A is connected with each vertex from B. There are no other edges. What is the number of spanning trees?

14. Joyal’s proof

If we mark one vertex and call it left end, and another vertex and call it right end, (they might coincide) then we must show that there are n^{n} labelled trees with left and right end marked.

There are n^{n} mappings from the set {1, 2, …, n} into itself. We want to establish a bijection.

We start from a map, e.g.,

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

which is represented as a directed graph. We might write it also as

f = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 7 & 5 & 5 & 9 & 1 & 2 & 5 & 8 & 4 & 7 \end{matrix}) .

Each component has exactly one directed cycle. Let M be the union of the vertex sets of these cycles. In the example, M = {1, 7, 5, 4, 9, 8}. If we restrict f on this set M, it acts as a bijection, and M is the largest set such that this is true. We write this bijection as

f|_{M} = (\begin{matrix}a & b & … & z \\ f(a) & f(b) & … & f(z) \end{matrix}) ,

where M = {a < b < ⋯ < z}. In the example,

f|_{M} = (\begin{matrix}1 & 4 & 5 & 7 & 8 & 9 \\ 7 & 9 & 1 & 5 & 8 & 4 \end{matrix}) .

Now construct a tree from that as follows:

Draw f(a), …, f(z) in this order as a path. f(a) will be the left end, and f(z) will be the right end.

[figure: 7; 9; 1; 5; 8; 4; ← right end; left end →]

Finally, add the remaining edges (deleting the arrows):

[figure: 7; 9; 1; 5; 8; 4; ← right end; left end →; 10; 2; 6; 3]

This is the tree. It is immediate to reverse this correspondence: Given a tree t, we look at the unique path P from the left end to the right end. This gives us the set M and the mapping f|_{M}. The remaining correspondences i → f(i) are then filled in according to the unique paths from i to P.

15. Lagrange inversion formula

Let y = xΦ(y), where Φ(y) is a power series such that Φ(0) ≠ 0. It is obvious to expand x as a power series in y, but we want just the opposite. This is the celebrated inversion formula of Lagrange. There are 3 versions of it.

[x^{n}]y = \frac{1}{n}[y^{n−1}](Φ(y))^{n} (n ≥ 1).

Slightly more general:

[x^{n}]y^{p} = \frac{p}{n}[y^{n−p}](Φ(y))^{n}.

Even more general:

[x^{n}]g(y) = \frac{1}{n}[y^{n−1}]g′(y)(Φ(y))^{n}.

Sketch of proof (no convergence considered). We use Cauchy’s integral formula. Observe that

dx = dy \frac{Φ(y) − yΦ′(y)}{Φ^{2}(y)}.

Now

[x^{n}]y = \frac{1}{2πi} ∮ \frac{dx}{x^{n+1}} y

= \frac{1}{2πi} ∮ dy \frac{Φ(y) − yΦ′(y)}{Φ^{2}(y)} \frac{Φ^{n+1}(y)}{y^{n+1}}y

= \frac{1}{2πi} ∮ dy(Φ(y) − yΦ′(y))\frac{Φ^{n−1}(y)}{y^{n}}

= [y^{n−1}](Φ(y) − yΦ′(y))Φ^{n−1}(y)

= [y^{n−1}]Φ^{n}(y) − [y^{n−2}]Φ′(y)Φ^{n−1}(y)

= [y^{n−1}]Φ^{n}(y) − \frac{1}{n}[y^{n−2}](Φ^{n}(y))′

= [y^{n−1}]Φ^{n}(y) − \frac{n − 1}{n}[y^{n−1}](Φ^{n}(y))

= \frac{1}{n}[y^{n−1}](Φ^{n}(y)).

Tutorial. Do the analogous computation for y^{p}.

Applications: Binary trees B = 1 + xB^{2}. Set B = 1 + y, then y = x(1 + y)^{2}. So Φ(y) = (1 + y)^{2}, and thus

b_{n} = [x^{n}]B(x) = [x^{n}]y(x) = \frac{1}{n}[y^{n−1}](1 + y)^{2n} = \frac{1}{n}\binom{2n}{n − 1} = \frac{1}{n + 1}\binom{2n}{n}.

t–ary trees B = 1 + xB^{t}. Set B = 1 + y, then y = x(1 + y)^{t}. So Φ(y) = (1 + y)^{t}, and thus

b_{n} = [x^{n}]B(x) = [x^{n}]y(x) = \frac{1}{n}[y^{n−1}](1 + y)^{tn} = \frac{1}{n}\binom{tn}{n − 1}.

As an exercise, you might like to consider powers of y. They enumerate “ordered forests.” Example from Flajolet and Noy T^{3} − zT + z^{2} = 0. Set T = z + zy, then

z = \frac{y}{(1 + y)^{3}} ,

or y = z(1 + y)^{3}. Thus (n ≥ 2)

[z^{n}]T = [z^{n−1}](1 + y) = [z^{n−1}]y = \frac{1}{n − 1}[y^{n−2}](1 + y)^{3(n−1)} = \frac{1}{n − 1}\binom{3n − 3}{n − 2}.

Example from Goulden and Jackson Given

x = y(1 + x)^{4}
yb(y) = \frac{x(1 − x)}{(1 + x)^{2}},

and [y^{n}]b(y) is desired. Note that the roles of x and y are now changed.

[y^{n}]b(y) = [y^{n+1}]yb(y)

= [y^{n+1}]\frac{x(1 − x)}{(1 + x)^{2}}

= \frac{1}{n + 1}[x^{n}]\frac{d}{dx} \frac{x(1 − x)}{(1 + x)^{2}}(1 + x)^{4(n+1)}

= \frac{1}{n + 1}[x^{n}]\frac{1 − 3x}{(1 + x)^{3}} (1 + x)^{4(n+1)}

= \frac{1}{n + 1}[x^{n}](1 − 3x)(1 + x)^{4n+1}

= \frac{1}{n + 1}[\binom{4n + 1}{n} − 3\binom{4n + 1}{n − 1}]

= \frac{2(4n + 1)!}{(n + 1)!(3n + 2)!}

Another example from Goulden and Jackson

θ = \frac{x}{(1 − θ)^{2}}
P = (1 − θ)(1 + 3θ)

So P is really a function of x, and we want [x^{n}]P (x). By Lagrange,

[x^{n}]P (x) = \frac{1}{n}[θ^{n−1}](\frac{d}{dθ}(1 − θ)(1 + 3θ))(1 − θ)^{−2n}

= \frac{1}{n}[θ^{n−1}](2 − 6θ)(1 − θ)^{−2n}

= \frac{2(3n − 3)!}{n!(2n − 1)!}.

(Here, θ = y, P = g(y).) Lagrange-Bürmann formula. Again, y = xΦ(y) and c_{n} = [y^{n}]F (y)Φ^{n}(y), with a power series F (y). Then

∑_{n≥0} c_{n}x^{n} = \frac{F (y)}{1 − xΦ′(y)}.

Proof: Start from

f(y) = f(0) + ∑_{n≥1} \frac{1}{n}x^{n}[y^{n−1}]Φ^{n}(y)f′(y).

Differentiate this w.r.t. x, to obtain

f′(y)\frac{dy}{dx} = ∑_{n≥0} x^{n}[y^{n}]Φ^{n+1}(y)f′(y).

But from x = \frac{y}{Φ(y)}

\frac{dx}{dy} = \frac{1}{Φ(y)} − \frac{yΦ′(y)}{Φ^{2}(y)} = \frac{1}{Φ(y)}[1 − xΦ′(y)]

and so

f′(y)\frac{Φ(y)}{1 − xΦ′(y)} = ∑_{n≥0} x^{n}[y^{n}]Φ^{n+1}(y)f′(y).

Now set F (y) = f′(y)Φ(y) and we have

\frac{F (y)}{1 − xΦ′(y)} = ∑_{n≥0} x^{n}[y^{n}]Φ^{n}(y)F (y).

Application: Middle trinomial coefficients: c_{n} = [y^{n}](1+y+y^{2})^{n}. That means F (y) = 1, Φ(y) = (1 + y + y^{2}), and thus

∑_{n≥0} c_{n}x^{n} = \frac{1}{1 − x(1 + 2y)},

where y = x(1 + y + y^{2}). Therefore

y = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x}

and

x(1 + 2y) = x + 1 − x − \sqrt{1 − 2x − 3x^{2}}

and so

∑_{n≥0} c_{n}x^{n} = \frac{1}{\sqrt{1 − 2x − 3x^{2}}} .

Example. Compute

H(x) = ∑_{n≥0} \binom{an}{n}x^{n}.

Since \binom{an}{n} = [y^{n}](1 + y)^{an}, we have Φ(y) = (1 + y)^{a}, and F (y) = 1. Thus

\frac{F (y)}{1 − xΦ′(y)} = \frac{1}{1 − ax(1 + y)^{a−1}} .

In the instance a = 2 we can make this explicit, since we can solve y = x(1+y)^{2}, giving

y = −1 + \frac{1 − \sqrt{1 − 4x}}{2x}

Further

1 − xΦ′(y) = 1 − 2x(1 + y) = 1 − 2x\frac{1 − \sqrt{1 − 4x}}{2x} = \sqrt{1 − 4x},

and so

∑_{n≥0} \binom{2n}{n}x^{n} = \frac{1}{\sqrt{1 − 4x}}.

Abel-like. y = xe^{y}, so Φ(y) = e^{y}, and F (y) = e^{ay}. Then

\frac{e^{ay}}{1 − xe^{y}} = \frac{e^{ay}}{1 − y} = ∑_{n≥0} x^{n}[y^{n}]e^{ay}e^{ny} = ∑_{n≥0} x^{n} \frac{(a + n)^{n}}{n!}

or even

\frac{e^{ay}}{1 − y} = ∑_{n≥0}(ye^{−y})^{n} \frac{(a + n)^{n}}{n!}

Note the instance a = 0.

\frac{1}{1 − y} = ∑_{n≥0}(ye^{−y})^{n} \frac{n^{n}}{n!} .

Another example. Now let F (y) = (1 + y)^{a}, Φ(y) = (1 + y)^{−b}.

(1 + y)^{a} = 1 + ∑_{n≥1} \frac{1}{n}x^{n}[y^{n−1}](1 + y)^{−bn}a(1 + y)^{a−1}

= 1 + ∑_{n≥1} \frac{1}{n}x^{n}a\binom{a − 1 − bn}{n − 1}

= 1 + ∑_{n≥1} \frac{a}{a − bn}x^{n}\binom{a − bn}{n}

= ∑_{n≥0} x^{n} \frac{a}{a − bn}\binom{a − bn}{n}

Call that G_{n}(a, b) = \frac{a}{a−bn} \binom{a−bn}{n}.

(1 + y)^{a} = ∑_{n≥0} G_{n}(a, b)x^{n}

From (1 + y)^{a+c} = (1 + y)^{a}(1 + y)^{c} we see

∑_{n≥0} G_{n}(a + c, b)x^{n} = ∑_{n≥0} G_{n}(a, b)x^{n} ∑_{n≥0} G_{n}(c, b)x^{n}

and, upon comparing coefficients,

G_{n}(a + c, b) = ∑_{k=0}^{n} G_{k}(a, b)G_{n−k}(c, b)

Note that (for b = 0) this is a generalization of the Vandermonde formula. We could have had this formula from the theory of polynomials of binomial type.

Number of leaves (Narayana).

G(z, u) = zu + \frac{zG(z, u)}{1 − G(z, u)}

u counts leaves, z nodes (in planted plane trees).

G_{n,k} = [u^{k}][z^{n}]G(z, u) = [u^{k}]\frac{1}{n}[y^{n−1}](u + \frac{y}{1 − y} )^{n}

= \frac{1}{n}[y^{n−1}]\binom{n}{k}\frac{y^{n−k}}{(1 − y)^{n−k}}

= \frac{1}{n}\binom{n}{k}[y^{k−1}]\frac{1}{(1 − y)^{n−k}}

= \frac{1}{n}\binom{n}{k}\binom{n − 2}{k − 1}.

These numbers are sometimes called Narayana numbers. Abel. Set F (y) = e^{ay}, Φ(y) = e^{−yz}, then

e^{ay} = 1 + ∑_{n≥1} \frac{1}{n}x^{n}[y^{n−1}]ae^{ay}e^{−yzn}

= 1 + ∑_{n≥1} \frac{1}{n}x^{n} \frac{a(a − zn)^{n−1}}{(n − 1)!}

= ∑_{n≥0} x^{n} \frac{a(a − zn)^{n−1}}{n!}

= ∑_{n≥0} y^{n}e^{yzn} \frac{a(a − zn)^{n−1}}{n!} .

Now multiply this by e^{by}:

e^{(a+b)y} = ∑_{k≥0} y^{k}e^{y(b+zk)} \frac{a(a − zk)^{k−1}}{k!} .

Read off the coefficient of y^{n}:

\frac{(a + b)^{n}}{n!} = ∑_{k≥0}[y^{n−k}]e^{y(b+zk)} \frac{a(a − zk)^{k−1}}{k!}

or

\frac{(a + b)^{n}}{n!} = ∑_{k≥0} \frac{(b + zk)^{n−k}}{(n − k)!} \frac{a(a − zk)^{k−1}}{k!}

or

(a + b)^{n} = ∑_{k=0}^{n} \binom{n}{k}a(a − zk)^{k−1}(b + zk)^{n−k}.

This form is the most popular of the many forms of Abel’s identities. It is a generalization of the binomial theorem (set z = 0).

Tree function y = xe^{y}. If we write

y(x) = ∑_{n≥1} a_{n} \frac{x^{n}}{n!} ,

what is a_{n}?

Well, Φ(y) = e^{y}, and

[x^{n}]y = \frac{1}{n}[y^{n−1}]e^{yn} = \frac{1}{n} \frac{n^{n−1}}{(n − 1)!},

thus a_{n} = n^{n−1}.

There should be a reason why this exponential generating function enumerates labelled rooted trees, and, yes, there is one:

Products of egf’s take care of the relabelling, and a tree is a root and a multiset of subtrees. However, if there are k subtrees, it leads to a term T^{k}(x)/k!, since the relative order is unimportant!

T (x) = x ∑_{k≥0} \frac{T^{k}(x)}{k!} = x exp(T (x)).

16. Multiset construction

Not discussed in 2000

This multiset idea can also be used e.g. in permutations: permutations are a multiset of cycles. Let us find the exponential generating function of cycles: How many cycles of length n are there? Answer: (n − 1)!, and thus

∑_{n≥1} \frac{(n − 1)!x^{n}}{n!} = log \frac{1}{1 − x}

Thus the egf of permutations is

exp log \frac{1}{1 − x} = \frac{1}{1 − x}

which is not very surprising. However, we can now deal with restricted permutations. Permutations without fixpoints:

∑_{n≥2} \frac{(n − 1)!x^{n}}{n!} = log \frac{1}{1 − x} − x

exp(log \frac{1}{1 − x} − x) = \frac{1}{1 − x}e^{−x}

Hence the number of permutations without fixpoints is

n![x^{n}]\frac{1}{1 − x}e^{−x} = n! ∑_{k=0}^{n}[x^{k}]e^{−x} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} .

Only even cycle length allowed:

∑_{n≥1} \frac{x^{2n}}{2n} = \frac{1}{2} log \frac{1}{1 − x^{2}}

and finally

exp \frac{1}{2} log \frac{1}{1 − x^{2}} = \frac{1}{\sqrt{1 − x^{2}}}

The desired number is (length 2n)

(2n)!4^{−n}\binom{2n}{n} = \frac{(2n)!^{2}}{n!^{2}4^{n}} .

Involutions: Only cycles of length 1 or 2, thus

exp(x + \frac{x^{2}}{2} ),

whence the formula for the number of involutions:

∑_{0≤k≤n/2} \frac{n!}{(n − 2k)!2^{k}k!}

17. Pólya’s enumeration theory (Sketch)

A typical question is this: Consider a figure like

We want to colour two faces red, two faces blue, but identify the coloured objects if they can be obtained from each other by a rotation in the plane. There are 2 solutions:

R B B R  R B R B

There is a permutation group 𝔊 involved, acting (in the example) on the faces of the figure. Apparently there are 4 rotations, and, denoting the faces by numbers 1, 2, 3, 4,

1 23 4

they are id, (1234), (13)(24), (1432).

We need the cycle type of a permutation π: If it has i_{1} cycles of length 1, i_{2} cycles of length 2, etc. then it is

cycle-type(π) := x_{1}^{i_{1}}x_{2}^{i_{2}} ….

We need the cycle indicator of the permutation group 𝔊. It is

P_{𝔊} = \frac{1}{|𝔊|} ∑_{π∈𝔊}cycle-type(π).

In our example it is

\frac{1}{4} (x_{1}^{4} + 2x_{4} + x_{2}^{2})

Polya says: Replace variable x_{i} by R^{i} + B^{i}:

\frac{1}{4} ((R + B)^{4} + 2(R^{4} + B^{4}) + (R^{2} + B^{2})^{2})

and compute the coefficient of R^{2}B^{2} in it, which is

\frac{1}{4} (\binom{4}{2} + \binom{2}{1}) = \frac{1}{4} (6 + 2) = 2.

Amazing!

If we would be interested in colourings with 3 red, one blue, look at the coefficient of R^{3}B, which is

\frac{1}{4}\binom{4}{3} = 1.

If you want to colour it with 3 colours, R, B, G, replace variables x_{i} by R^{i} + B^{i} + G^{i}. If you are interested in colourings with 2 red and 2 non-red, then consider

\frac{1}{4} ((R + B + G)^{4} + 2(R^{4} + B^{4} + G^{4}) + (R^{2} + B^{2} + G^{2})^{2}) ,

replace B and G both by 1:

\frac{1}{4} ((R + 2)^{4} + 2(R^{4} + 2) + (R^{2} + 2)^{2}) ,

and compute the coefficient of R^{2}:

\frac{1}{4} (\binom{4}{2}2^{2} + \binom{2}{1}2) = \frac{1}{4} (24 + 4) = 7.

If you are interested in the number of colourings with 3 colours, then replace all the variables R, B, G by 1, which amounts to replace all variables x_{i} by 3:

P_{𝔊}(3, 3, …).

Here, it is

\frac{1}{4} (3^{4} + 2 · 3 + 3^{2}) = \frac{81 + 6 + 9}{4} = 24.

If you are interested in colouring with 2 colours where all 2 colours really appear, consider

P_{𝔊}(2, 2, …) − 2 · P_{𝔊}(1, 1, …).

Consider a tetrahedron, with action on the vertices. We allow rotations in ℝ^{3}.

We have an axis through a vertex and a face (8 rotations), through 2 edges (3 rotations) and the identity. Altogether

P_{𝔊} = \frac{1}{12} (x_{1}^{4} + 8x_{1}x_{3} + 3x_{2}^{2}) .

Colour each vertex with one colour of A, B, C, D and ask for the number of essentially different configurations. It is

[ABCD]\frac{1}{12}((A+B+C+D)^{4}+8(A+B+C+D)(A^{3}+B^{3}+C^{3}+D^{3})+3(A^{2}+B^{2}+C^{2}+D^{2})^{2}),

which is

\frac{1}{12} \frac{4!}{1!1!1!1!} = 2.

As you might guess, it is important to know several cycle indicators. We consider a few now:

Rotations of the cube (action on the vertices)

The identity contributes x_{1}^{8}.

Here, we have 3 possible axes, and 90 or 270 degrees, resulting in 6x_{4}^{2}; 180 degrees results in 3x_{2}^{4}.

[figure]

[figure]

Here, we have 6 possible axes, and 180 degrees, resulting in 6x_{2}^{4}.

[figure]

Here, we have 4 possible axes, and 120 or 240 degrees, resulting in 8x_{1}^{2}x_{3}^{2}. Collecting,

P_{𝔊} = \frac{1}{24} (x_{1}^{8} + 9x_{2}^{4} + 6x_{4}^{2} + 8x_{1}^{2}x_{3}^{2}) .

Exercise: Consider action on the 6 faces. Symmetric group (all n permutations)

Assume that a certain cycle type is given:

(.)(.) … (.) (..)(..) … (..) …,

with λ_{1} cycles of length 1, λ_{2} cycles of length 2, etc. Of course, n = λ_{1} + 2λ_{2} + . . ..

If we fill in our n numbers in all possible ways, we get the same permutation several times. We can correct that by an appropriate division. The factor is 1^{λ_{1}}λ_{1}!2^{λ_{2}}λ_{2}! . . .. The reason is that cycles of the same length can be permuted, and in a particular cycle, each element can stand in the first position (compare our discussion about the canonical representation as a product of cycles). Eventually,

P_{𝔖_{n}} = \frac{1}{n!} ∑_{n=λ_{1}+2λ_{2}+...} \frac{n!}{1^{λ_{1}}λ_{1}!2^{λ_{2}}λ_{2}! …}x_{1}^{λ_{1}}x_{2}^{λ_{2}} ….

Cyclic group of order n.

Well, there are n such permutations, and they are generated by (12 … n). Let us do the example n = 6.

π = (123456)
π^{2} = (135)(246)
π^{3} = (14)(25)(36)
π^{4} = (153)(264)
π^{5} = (165432)
π^{6} = Id

Yeah, but what are the cycle types? It has something to do with divisors of 6, that seems to be clear. A little reflection shows that

ord(π^{k}) = \frac{n}{gcd(n, k)}.

P_{ℨ_{n}} = \frac{1}{n} ∑_{1≤k≤n} x_{n/ gcd(n,k)}^{k}

= \frac{1}{n} ∑_{j|n} |\{k | gcd(n, k) = j\}| x_{n/j}^{j}

= \frac{1}{n} ∑_{j|n} |\{\frac{k}{j} | gcd(\frac{n}{j}, \frac{k}{j}) = 1\} x_{n/j}^{j}

= \frac{1}{n} ∑_{j|n} φ(\frac{n}{j})x_{n/j}^{j}

= \frac{1}{n} ∑_{l|n} φ(l)x_{l}^{n/l}.

Rotations and reflections. Now allow additionally the n reflections. If n is odd, there are n contributions of type x_{1}x_{2}^{(n−1)/2} (action on the vertices of the regular n–gon, say).

\frac{1}{2n} (∑_{l|n} φ(l)x_{l}^{n/l} + nx_{1}x_{2}^{(n−1)/2}) .

If n is even, there are n/2 of type x_{2}^{n/2} and n/2 of type x_{1}^{2}x_{2}^{(n−2)/2}.

\frac{1}{2n} (∑_{l|n} φ(l)x_{l}^{n/l} + \frac{n}{2}x_{2}^{n/2} + \frac{n}{2}x_{1}^{2}x_{2}^{(n−2)/2}) .

∗ ∗ ∗ ∗ ∗ The End ∗ ∗ ∗ ∗ ∗