Manuel Kauers Hagenberg, March 19, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 3

Exercise 1 Find nice recurrences for s(n, k) and c(n, k).

In order to enumerate all permutations π of {1, …, n}, we proceed recursively. The first bunch of permutations leaves n fixed. Then (n) is one cycle of its own, and there are k − 1 further cycles left for permuting the remaining n − 1 elements. These gives c(n − 1, k − 1) permutations. Next we consider a permutation π of {1, …, n−1} with k cycles. There are c(n−1, k) permutations of this type. Let

π = (p_{1} p_{2} … p_{c_{1}})(p_{c_{1}+1} … p_{c_{2}}) . . . . . . (p_{c_{k−1}+1} … p_{c_{k}})

be a representation of the permutation π. Note that c_{k} = n − 1. Any extension of π to a permutation of {1, …, n} also having exactly k cycles must have the form

π = (p_{1} …) … (… p_{i} n p_{i+1} …) … (… p_{n−1})

for some i = 1, …, n − 1. If p_{i} and p_{i+1} belong to different cycles, we may put n always to the cycle of p_{i}. This is without loss of generality because (a_{1} a_{2} … a_{ℓ}) = (a_{ℓ} a_{1} a_{2} … a_{ℓ−1}). We have found that there are exactly n − 1 ways to extend π to a permutation of {1, …, n} leaving the number of cycles fixed. Putting things together we obtain

c(n, k) = (n − 1)c(n − 1, k) + c(n − 1, k − 1) (n, k ≥ 1)

as a recurrence for c(n, k). Applying the definition s(n, k) = (−1)^{n}c(n, k) directly gives the recurrence for s(n, k):

s(n, k) = (1 − n)s(n − 1, k) + s(n − 1, k − 1) (n, k ≥ 1).

Exercise 2 Prove: ∑_{k=0}^{n} s(n, k)x^{k} = x\underline{n}.

Note that s(n, k) = 0 for k > n, so it suffices to show the claim for the generating function G_{n}(x) of s(n, k) in place of the finite sum. For n = 0 we have G_{0}(x) = 1. For n > 0 we have

G_{n}(x) = ∑_{k=0}^{∞} s(n, k)x^{k} = (1 − n) ∑_{k=0}^{∞} s(n − 1, k)x^{k} + ∑_{k=0}^{∞} s(n − 1, k − 1)x^{k}

= (1 − n)G_{n−1}(x) + ∑_{k=1}^{∞} s(n − 1, k − 1)x^{k} = (1 − n)G_{n−1}(x) + x ∑_{k=0}^{∞} s(n − 1, k)x^{k}
= (x − n + 1)G_{n−1}(x).

This recurrence for G_{n}(x) has the solution G_{n}(x) = x\underline{n}.

Exercise 3 For n, k ∈ ℕ define

J_{n}(k) := {(a_{1}, …, a_{n}) ∈ ℕ^{n} : 0 ≤ a_{i} ≤ n − i and

exactly k values of the a_{i} are equal to 0 }.

Prove |J_{n}(k)| = c(n, k).

It suffices to show that |J_{n}(k)| and c(n, k) satisfy the same recurrence and the same initial conditions. As for the initial conditions, we find immediately

|J_{0}(0)| = c(0, 0) = 1,
|J_{n}(0)| = c(n, 0) = 0 (n > 1),
|J_{0}(k)| = c(0, k) = 0 (k > 1).

Now consider J_{n}(k). Let a = (a_{1}, …, a_{n}) ∈ J_{n}(k). If a_{1} = 0 then there have to be k − 1 further zeroes in the tail, and therefore J_{n}(k) contains |J_{n−1}(k − 1)| tuples with a_{1} = 0. Otherwise, if a_{1} ≠ 0, then there are n − 1 possible values for a_{1}, and for each of these possibilities there are |J_{n−1}(k)| tails. It follows that

|J_{n}(k)| = |J_{n−1}(k − 1)| + (n − 1)|J_{n−1}(k)| (n, k ≥ 1),

which literally agrees with the recurrence for c(n, k).

Exercise 4 Find a closed form expression for ∑_{π∈S_{n}} q^{inv(π)}.

We have

∑_{π∈S_{n}} q^{inv(π)} =^{(∗)} ∏_{k=1}^{n} ∑_{i=0}^{k−1} q^{i} = ∏_{k=1}^{n} \frac{q^{k} − 1}{q − 1} = \frac{1}{(q − 1)^{n}} ∏_{k=1}^{n}(q^{k} − 1).

Defining the q-analog of n ∈ ℕ as [n]_{q} := \frac{q^{n}−1}{q−1}, we can write the answer as [n]_{q}! (q-factorial). It remains to justify (∗). For n = 1 the assertion is evident (1 = 1). Assume it holds for n ∈ ℕ. The elements of S_{n+1} can be created from the elements π of S_{n} by inserting n+1 at all possible positions of the word representation of π. For example, (2 1 3) yields (4 2 1 3), (2 4 1 3), (2 1 4 3) and (2 1 3 4). If π ∈ S_{n} has i inversions and π′ ∈ S_{n+1} is obtained from π by inserting n + 1 at position j ∈ [n + 1], then π′ has i + (j − 1) inversions. It follows that

∑_{π∈S_{n+1}} q^{inv(π)} = ( ∑_{π∈S_{n}} q^{inv(π)}) + q( ∑_{π∈S_{n}} q^{inv(π)}) + ⋯ + q^{n}( ∑_{π∈S_{n}} q^{inv(π)})

= (∑_{k=0}^{n} q^{k}) ∑_{π∈S_{n}} q^{inv(π)} = (∑_{k=0}^{n} q^{k}) ∏_{k=1}^{n} ∑_{i=0}^{k−1} q^{i} = ∏_{k=1}^{n+1} ∑_{i=0}^{k−1} q^{i}.

This completes the proof.

Exercise 5 For each number k ∈ [0, n! − 1] (n ∈ ℕ) there exists a unique tuple (α_{1}, …, α_{n−1}) ∈ [0, 1] × [0, 2] × ⋯ × [0, n − 1] such that

k = ∑_{i=1}^{n−1} α_{i}i!.

The statement holds for n = 1. Suppose it holds for n ∈ ℕ. Observe the partition

[0, (n + 1)! − 1] = [0, n! − 1] ∪^{.} [n!, 2n! − 1] ∪^{.} … ∪^{.} [nn!, (n + 1)n! − 1].

For every k ∈ [0, (n + 1)! − 1] there is exactly one i ∈ [1, n + 1] such that k ∈ [(i − 1)n!, in! − 1]. By induction hypothesis, the claim holds for k − (i − 1)n! ∈ [0, n! − 1], giving the unique tuple (π_{1}, …, π_{n−1}). This extends to the unique tuple (π_{1}, …, π_{n−1}, i) for the original k.