Manuel Kauers Hagenberg, April 19, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 5

Exercise 1 Find an elimination rule for Ω_{≥} \frac{λ^{−s}}{(1 − Aλ)(1 − B/λ)}.

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

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

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

Exercise 2 Let p_{2}(n, k) be the number of partitions of n into k parts with

difference at least two. Prove: ∑_{n=0}^{∞} p_{2}(n, k)q^{n} = \frac{q^{k^{2}}}{(1−q)(1−q^{2})...(1−q^{k})}.

∑_{{n_{1},...,n_{k}≥1 \atop n_{i+1}−n_{i}≥2}} q^{n_{1}+···+n_{k}} = q^{k} ∑_{{n_{1},...,n_{k}≥0 \atop n_{i+1}−n_{i}≥2}} q^{n_{1}+···+n_{k}}

= q^{k} Ω_{≥} ∑_{n_{1},...,n_{k}≥0} λ_{1}^{n_{2}−n_{1}−2}λ_{2}^{n_{3}−n_{2}−2} ⋯ λ_{k−1}^{n_{k}−n_{k−1}−2}q^{n_{1}+···+n_{k}}

= q^{k} Ω_{≥} \frac{λ_{1}^{−2}λ_{2}^{−2} ⋯ λ_{k−1}^{−2}}{(1 − q \frac{1}{λ_{1}} )(1 − q \frac{λ_{1}}{λ_{2}} ) ⋯ (1 − q \frac{λ_{k−2}}{λ_{k−1}} )(1 − qλ_{k−1})}

=_{B=qλ_{k−2}}^{A=q} q^{k} \frac{q^{2}}{(1 − q)} Ω_{≥} \frac{λ_{1}^{−2} ⋯ λ_{k−2}^{−2}}{(1 − q \frac{1}{λ_{1}} )(1 − q \frac{λ_{1}}{λ_{2}} ) ⋯ (1 − q \frac{λ_{k−3}}{λ_{k−2}} )(1 − q^{2}λ_{k−2})}

= ⋯ = q^{k} \frac{q^{2}}{(1 − q)} \frac{(q^{2})^{2}}{(1 − q^{2})} … \frac{(q^{k−2})^{2}}{(1 − q^{k−2})} Ω_{≥} \frac{λ_{1}^{−2}}{(1 − q \frac{1}{λ_{1}} )(1 − q^{k−1}λ_{1})}

= q^{k} \frac{q^{2}}{(1 − q)} \frac{(q^{2})^{2}}{(1 − q^{2})} … \frac{(q^{k−2})^{2}}{(1 − q^{k−2})} \frac{(q^{k−1})^{2}}{(1 − q^{k−1})(1 − q^{k})}
= \frac{q^{k}q^{2+4+6+···+2(k−1)}}{(1 − q) ⋯ (1 − q^{k})} = \frac{q^{k}q^{k(k−1)}}{(1 − q) ⋯ (1 − q^{k})} = \frac{q^{k^{2}}}{(1 − q) ⋯ (1 − q^{k})}

Exercise 3 For n ∈ ℕ, let p_{odd}(n) be the number of partitions of n into odd parts and p_{dist}(n) be the number of partitions of n into distinct parts. Give a combinatorial proof that p_{odd}(n) = p_{dist}(n) for all n ∈ ℕ.

Given a partition n = n_{1} + n_{2} + ⋯ + n_{k} into odd parts, keep on replacing two equal parts n_{i} = n_{j} by one part n_{i} + n_{j}. When this is no longer possible, the parts of the resulting partition are distinct. Conversely, given a partition n = n_{1} + n_{2} + ⋯ + n_{k} into distinct parts, write n_{i} = odd_{i} · 2^{m_{i}} and replace n_{i} by 2^{m_{i}} parts of size odd_{i}. The resulting partition consists of odd parts only.

[figure: ⇆; {; {]

Exercise 4 Find a recurrence for p(n) and compute p(721).

We are given

∑_{n=1}^{∞} p(n)q^{n} = ∏_{n=1}^{∞} \frac{1}{1 − q^{n}} .

By Euler’s pentagonal number theorem, it follows that

1 = ∑_{n=1}^{∞} p(n)q^{n} · ∑_{n=−∞}^{∞}(−1)^{n}q^{r(3r−1)/2}

= 1 + ∑_{n=1}^{∞}(−1)^{r}q^{r(3r−1)/2}(1 + q^{r}).

Defining (a_{n})_{n=0}^{∞} by

∑_{n=0}^{∞} a_{n}q^{n} = 1 + ∑_{n=1}^{∞}(−1)^{r}q^{r(3r−1)/2}(1 + q^{r})

= 1 + ∑_{n=1}^{∞}((−1)^{r}q^{r(3r−1)/2} + (−1)^{r}q^{r(3r+1)/2})  (1)

we get

1 = ∑_{n=0}^{∞} p(n)q^{n} ∑_{n=0}^{∞} a_{n}q^{n} = ∑_{n=0}^{∞} ∑_{k=0}^{n} p(k)a_{n−k} q^{n}.

Extracting the nth coefficient (n > 0) and observing a_{0} = 1 gives the desired recurrence:

p(n) = ∑_{k=0}^{n−1} p(k)a_{n−k}.

As for the a_{n}, comparing coefficients in (1) gives the following “closed form”:

a_{n} = \{ \begin{matrix}1 & n = 0 \\ −1 & if (1 + \sqrt{1 + 24n}) or (−1 + \sqrt{1 + 24n}) is an odd integer \\ 1 & if (1 + \sqrt{1 + 24n}) or (−1 + \sqrt{1 + 24n}) is an even integer \\ 0 & otherwise \end{matrix}

Observe that no natural number n can be written both as n = r_{1}(3r_{1} − 1)/2 and n = r_{2}(3r_{2} + 1)/2 for natural numbers r_{1}, r_{2}.

In addition, we need the starting value p(1) = 1. Computing p(721) with Mathematica takes 1.3s (on my machine) and gives the result

p(721) = 161 061 755 750 279 477 635 534 762.

Exercise 5 Find at least four group actions which have not been mentioned in the lecture.

a) Let G be the set of rotations around the origin in ℝ^{2} and M be a circle around the origin. (obvious.)

b) Let G = (ℝ, ·), M = {−1, 0, 1} and define gm = sgn(g · m) for g ∈ G, m ∈ M. Then 1m = m (m ∈ M) and

g_{1}(g_{2}m) = g_{1} sgn(g_{2} · m) = sgn(g_{1} · sgn(g_{2} · m)) = sgn(g_{1}g_{2} · m) = (g_{1}g_{2})m.

c) Let G = (ℤ, +) and M = C^{∞}([0, 1])/ℝ[x]. For g ∈ G, m ∈ M define

gm = \{ \begin{matrix}\frac{∂^{g}}{∂x^{g}} m & if g < 0 \\ m & if g = 0 \\ \underbrace{∫ ∫ … ∫}_{g times} m & if g > 0 \end{matrix}

d) Let M be any algebraic structure (semigroup, monoid, group, ring, …) and G be the set of isomorphisms on M.

e) Let G = (C([0, 1]), +), M = ℝ and define gm = g(1) + m. Then 1m = 0(1) + m = m and

g_{1}(g_{2}m) = g_{1}(g_{2}(1) + m) = g_{1}(1) + g_{2}(1) + m = (g_{1}g_{2})m