Manuel Kauers Hagenberg, March 24, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 4

Exercise 1 Give a combinatorial proof for the identity ∑_{k=1}^{x} p(n, k) = p(n + x, x).

Obviously p^{−}(n, x) = ∑_{k=1}^{x} p(n, k). We prove p^{−}(n, x) = p(n + x, x).

Take x extra balls (black) in the Ferrers diagram and put one of them into each row. Then every partition (white) of n with into at most k parts gives rise to a partition of n + x into exactly x parts and vice versa.

x [figure: {]

Exercise 2 Give a combinatorial proof for the identity p(n, k) = p(n−1, k −1)+ p(n − k, k).

Consider the last row in a partition of n into k parts. This row contains either one ball or more. There are p(n − 1, k − 1) partitions with one ball in the last row (remove the ball and consider the remainder). If there are more balls in the last row, then we can remove the first column (consisting of k balls) and the remainder is a partition of n − k into exactly k parts.

k [figure: {] k [figure: {]

Exercise 3 Switch from the Fibonacci sequence F_{n} to its generating function and back.

Let f(x) := ∑_{n=0}^{∞} F_{n}x^{n}. Then

f(x) = ∑_{n=0}^{∞} F_{n}x^{n} = 1 + x + ∑_{n=2}^{∞} F_{n}x^{n}

= 1 + x + ∑_{n=2}^{∞}(F_{n−1} + F_{n−2})x^{n} = 1 + x + x ∑_{n=1}^{∞} F_{n}x^{n} + x^{2} ∑_{n=0}^{∞} F_{n}x^{n}

= 1 + x ∑_{n=0}^{∞} F_{n}x^{n} + x^{2}f(x) = 1 + xf(x) + x^{2}f(x)

and therefore

f(x) = \frac{1}{1 − x − x^{2}} .

On the other hand, for f(x) we have

f(x) − xf(x) − x^{2}f(x) = 1.

Writing f(x) = ∑_{n=0}^{∞} F_{n}x^{n} and extracting the nth coefficient from the above (n ≥ 2),

we obtain

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

Together with the initial conditions F_{0} = f(0) = 1 and F_{1} = f′(0) = 1, this gives indeed back the Fibonacci numbers.

Exercise 4 Prove the elimination rule

Ω_{≥} \frac{1}{(1 − Aλ)(1 − B/λ)} = \frac{1}{(1 − A)(1 − AB)}.

We have

Ω_{≥} \frac{1}{(1 − Aλ)(1 − B/λ)} = Ω_{≥} ∑_{n=0}^{∞}(Aλ)^{n} · ∑_{k=0}^{∞}(B/λ)^{k} = Ω_{≥} ∑_{k=0}^{∞} ∑_{n=0}^{∞} A^{n}B^{k}λ^{n−k}

= Ω_{≥} ∑_{k=0}^{∞} ∑_{n=k}^{∞} A^{n}B^{k}λ^{n−k} = Ω_{≥} ∑_{k=0}^{∞} ∑_{n=0}^{∞} A^{n+k}B^{k}λ^{n}

= ∑_{k=0}^{∞}(AB)^{k} ∑_{n=0}^{∞} A^{n} = \frac{1}{1 − AB} \frac{1}{1 − A}.

Remark: A counterargument:

Let f(λ) = \frac{1}{(1−Aλ)(1−B/λ)} = ∑_{n=−∞}^{∞} a_{n}λ^{n}, then f(λ) = \frac{λ}{−Aλ^{2}+(1+AB)λ−B} and

−Af(λ)λ^{2} + (1 + AB)f(λ)λ − Bf(λ) = λ.

Taking the nth coefficient (n ≥ 2) gives

− Aa_{n−2} + (1 + AB)a_{n−1} − Ba_{n} = 0

a_{n} = \frac{(1 + AB)}{B}a_{n−1} − \frac{A}{B} a_{n−2}.

In addition, we have the starting points a_{0} = 0 and a_{1} = −1/B. (Note that we are only interested in a_{n} for n ≥ 0, the others are eaten by Ω.) It follows that

a_{n} = \frac{A^{n} − (1/B)^{n}}{1 − AB}

and hence

Ω_{≥}f(λ) = ∑_{n=0}^{∞} \frac{A^{n} − (1/B)^{n}}{1 − AB} = \frac{1}{1 − AB} (\frac{1}{1 − A} + \frac{B}{1 − B} ) .

Ooups!