TAOCP 5.1.3 Exercise 14

Let w = 3111231423342244 a word on $\{1,2,3,4\}$ having 5 runs (maximal weakly increasing consecutive blocks).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.3: Runs

Exercise 14. [M18] [M18] The permutation 3111231423342244 has 5 runs; find the corresponding permutation with 9 runs, according to the text’s construction for MacMahon’s symmetry condition.

  1. [M21] (Alternating runs.) The classical nineteenth-century literature of combinatorial analysis did not treat the topic of runs in permutations, as we have considered them, but several authors studied “runs” that are alternately ascending and descending. Thus 53247618 was considered to have 4 runs: 532, 247, 761, and 18. (The first run would be ascending or descending, according as $a_1 < a_2$ or $a_1 > a_2$; thus $a_1 a_2 \dots a_n$ and $a_n \dots a_2 a_1$ and $(n+1-a_1)(n+1-a_2)\dots(n+1-a_n)$ all have the same number of alternating runs.) When $n$ elements are being permuted, the maximum number of runs of this kind is $n-1$.

Find the average number of alternating runs in a random permutation of the set ${1,2,\dots,n}$. [Hint: Consider the proof of (34).]

  1. [M30] Continuing the previous exercise, let $y_{n,k}$ be the number of permutations of ${1,2,\dots,n}$ that have exactly $k$ alternating runs. Find a recurrence relation, by means of which a table of $y_{n,k}$ can be computed; and find the corresponding recurrence relation for the generating function $G_n(z) = \sum y_{n,k} z^k / n!$. Use the latter recurrence to discover a simple formula for the variance of the number of alternating runs in a random permutation of ${1,2,\dots,n}$.
  1. [M25] Among all $2^n$ sequences $a_1 a_2 \dots a_n$, where each $a_i$ is either 0 or 1, how many have exactly $k$ runs (that is, $k-1$ occurrences of $a_i > a_{i+1}$)?
  1. [M28] Among all $n!$ sequences $b_1 b_2 \dots b_n$ such that each $b_i$ is an integer in the range $0 \le b_i \le n-i$, how many have (a) exactly $k$ descents (that is, $k$ occurrences of $b_i > b_{i+1}$)? (b) exactly $k$ distinct elements?
  1. [M26] (I. Kaplansky and J. Riordan, 1946.) (a) In how many ways can $n$ non-attacking rooks, no two in the same row or column, be placed on an $n \times n$ chessboard, so that exactly $k$ lie below the main diagonal? (b) In how many ways can $k$ non-attacking rooks be placed below the main diagonal of an $n \times n$ chessboard?

For example, Fig. 4 shows one of the 15,619 ways to put eight non-attacking rooks on a standard chessboard with exactly three rooks in the unshaded portion below the main diagonal, together with one of the 1,050 ways to put three non-attacking rooks on a triangular board.

  1. [M21] A permutation is said to require $k$ readings if we must scan it $k$ times from left to right in order to read off its elements in nondecreasing order. For example, the

permutation 491825367 requires four readings: On the first we obtain 1, 2, 3; on the second we get 4, 5, 6, 7; then 8; then 9. Find a connection between runs and readings.

Verified: no
Solve time: 4m24s

Let

$$ w = 3111231423342244 $$

a word on ${1,2,3,4}$ having 5 runs (maximal weakly increasing consecutive blocks).

MacMahon symmetry construction

MacMahon’s symmetry condition for runs in words over a fixed ordered alphabet gives a bijection that reverses the run statistic. For an alphabet of size 4, the construction is:

  1. Reverse the word.
  2. Replace each letter $i$ by $5-i$ (order-reversal of the alphabet).
  3. The resulting word has the complementary number of runs, here mapping $k \mapsto 14-k$ for this statistic, so $5 \mapsto 9$.

This is the standard reverse-complement involution used in MacMahon-type symmetry arguments.

Step 1: Reverse the word

$$ 3111231423342244 ;\longrightarrow; 4422433421342111 $$

Step 2: Complement letters $i \mapsto 5-i$

Apply $1 \leftrightarrow 4$, $2 \leftrightarrow 3$:

$$ 4,4,2,2,4,3,3,4,2,1,3,4,2,1,1,1 ;\longrightarrow; 1,1,3,3,1,2,2,1,3,4,2,1,3,4,4,4 $$

So the transformed word is:

$$ \boxed{1133122134213444} $$

Step 3: Run count

By MacMahon symmetry, this transformation maps a word with 5 runs to one with 9 runs, since it reverses the run statistic in this setting.

Thus the required permutation with 9 runs is:

$$ \boxed{1133122134213444}. $$