Manuel Kauers Hagenberg, March 7, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 1

Exercise 1 Find a rank function for Lists(n, k), i.e., a bijection r: Lists(n, k) → [n\underline{k}] such that r and r^{−1} are easy to compute.

For simplicity, our bijection will be between Lists(n, k) and \{0, 1, …, n\underline{k} − 1\}. It can be brought to the desired form by a few additional lines of code. We propose the following algorithm for converting lists to numbers and vice versa. In our notation, l_{i} refers to the ith element of the list l.

1 \underline{function} list2number(n, k, l) 2 \underline{if} k = 1 \underline{then} 3 \underline{return} l_{1} − 1

4  \underline{else}

5 l′ := [l_{2}, l_{3}, …, l_{k}] 6 \underline{for} i \underline{from} 2 \underline{to} k \underline{do} 7 \underline{if} l′_{i} > l_{1} \underline{then} l′_{i} := l′_{i} − 1 8 \underline{return} (l_{1} − 1) · # Lists(n − 1, k − 1) + list2number(n − 1, k − 1, l′)

The idea is to use a digit system whose base varies with the position of the digit. The first element of the list gives the highest “digit,” and the tail has to be brought back into a form which allows recursion. The inverse is easily obtained as follows.

1 \underline{function} number2list(n, k, index) 2 \underline{if} k = 1 \underline{then} 3 \underline{return} [index + 1]

4  \underline{else}

5 subindex = index \underline{mod} # Lists(n − 1, k − 1) 6 l_{1} := 1 + (index \underline{quo} # Lists(n − 1, k − 1)) 7 l′ := number2list(n − 1, k − 1, subindex) 8 \underline{for} i \underline{from} 1 \underline{to} k − 1 \underline{do} 9 \underline{if} l′_{i} ≥ l_{1} \underline{then} l′_{i} := l′_{i} + 1 10 \underline{return} [l_{1}, l′_{1}, l′_{2}, …, l′_{k−1}]

Remark: An implementation of these algorithms in Maple is available at http://www.risc.uni-linz.ac.at/mkauers/exercises/ .

Exercise 2 Give a combinatorial proof for the identity

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

where n ∈ ℕ and x is an indeterminate.

We have to argue that [x^{k}](1 + x)^{n} = \binom{n}{k}. Indeed,

(1 + x)^{n} = \underbrace{(1 + x) · (1 + x) · · · · · (1 + x)}_{n factors},

and on multiplying this out, we obtain 2^{n} terms from the 2^{n} path through this product (each factor admits a choice between 1 and x). A walk through the product gives x^{k} for exactly those paths which contain k x’s and n − k 1’s. There are | Sets(n, k)| = \binom{n}{k} such paths.

Exercise 3 Show that the Printer procedure from the lecture defines a bijection between LabTrees(n) and [n]^{[n−2]}.

We have to show that for every π ∈ [n]^{[n−2]} there exists exactly one tree T such that Printer(T) = π. We do so by giving an algorithm which computes this T from a given π. The following algorithm does that job.

1 \underline{function} UnPrinter(n, π) 2 // Assume π = (π_{1}, …, π_{n−2}) with π_{i} ∈ [n]. 3 E := {(n, π_{n−2})} // first edge 4 found := { } 5 \underline{for} i \underline{from} 1 \underline{to} n − 2 \underline{do} 6 // create a new edge 7 e_{1} := π_{i} 8 e_{2} := min(\overline{\{π_{i}, …, π_{n−2}\} ∪ found}) // complement wrt. [n] 9 found := found ∪ {e_{2}} 10 E := E ∪ {(e_{1}, e_{2})} 11 \underline{return} ([n], E)

Example: The tree from the lecture has given π = (6 7 2 7 1). From this information the above algorithm reconstructs the tree defined by the edge (7, 1) and the edges (6, a), (7, b), (2, c), (7, d), (1, e), where

a = min{ k ∈ [7] : k ∉ {6, 7, 2, 7, 1} and k ∉ {} }  = 3
b = min{ k ∈ [7] : k ∉ {7, 2, 7, 1} and k ∉ {3} }  = 4
c = min{ k ∈ [7] : k ∉ {2, 7, 1} and k ∉ {3, 4} } = 5
d = min{ k ∈ [7] : k ∉ {7, 1}  and k ∉ {3, 4, 5} } = 2
e = min{ k ∈ [7] : k ∉ {1}  and k ∉ {3, 4, 5, 2} } = 6.

This gives the tree

7 _{{2 \atop 5} 1 {6 \atop 3} 4}

known from the lecture.