TAOCP 5.2.1 Exercise 25

A permutation \(K_1K_2\ldots K_N\) of \(\{1,2,\ldots,N\}\) is *2-ordered* if \(K_i < K_{i+2}\) for \(1\le i\le N-2\), and *3-ordered* if \(K_i < K_{i+3}\) for \(1\le i\le N-3\).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.1: Sorting by Insertion

Exercise 25. ▶ [M22] How many permutations of ${1, 2, \ldots, N}$ are both 3-ordered and 2-ordered? What is the maximum number of inversions in such a permutation? What is the total number of inversions among all such permutations?

Verified: no
Solve time: 14m14s

Solution

A permutation (K_1K_2\ldots K_N) of ({1,2,\ldots,N}) is 2-ordered if (K_i < K_{i+2}) for (1\le i\le N-2), and 3-ordered if (K_i < K_{i+3}) for (1\le i\le N-3). These conditions define a partial order (P_N) on the positions ({1,\ldots,N}) with cover relations (i \prec i+2) and (i \prec i+3). The desired permutations are exactly the linear extensions of (P_N).

1. Number of permutations

Let (a_N) be the number of linear extensions of (P_N). The maximal elements of (P_N) are (N) and (N-1) (since any (i\le N-2) has (i+2\le N) or (i+3\le N)). Hence the largest value (N) must appear at position (N) or (N-1).

Case 1: (N) is at position (N). Removing it leaves a valid permutation of size (N-1). This contributes (a_{N-1}) permutations.

Case 2: (N) is at position (N-1). We claim that then (N-1) must be at position (N).
Suppose (\pi(N)=x < N-1). Then (N-1) lies at some position (p\le N-2). The three residue classes modulo (3) have last positions (N, N-1, N-2). The class containing (N-1) ends at (N-1) with value (N); the class containing (N) ends at (N) with value (x); the third ends at (N-2) with value (\le N-2). The element (N-1) cannot belong to the latter two classes because they are strictly increasing and end with a value (< N-1). Thus (N-1) belongs to the class of (N-1), so (p \equiv N-1 \pmod 3).

Now consider the two parity chains (odd/even positions). Positions (N-1) and (N) have opposite parity. If (p) has the same parity as (N-1), then (p) and (N-1) lie on the same parity chain, which is strictly increasing. We would have (\pi(p)=N-1 < \pi(N-3) < \pi(N-1)=N), forcing (\pi(N-3)) strictly between (N-1) and (N) - impossible. If (p) has opposite parity to (N-1), then (p) lies on the other parity chain, which ends at (N) with value (x). Then (\pi(p)=N-1 < \ldots < x), contradicting (x\le N-2). Hence (x=N-1), i.e. (N-1) is at position (N).

Removing the pair ((N-1,N)) from positions (N-1) and (N) leaves a permutation of ({1,\ldots,N-2}) on positions (1,\ldots,N-2). The remaining inequalities are exactly those of (P_{N-2}); the extra constraints (K_{N-2}<N-1) and (K_{N-3}<N-1) are automatically satisfied because all remaining values are (\le N-2). This contributes (a_{N-2}) permutations.

Thus (a_N = a_{N-1} + a_{N-2}) with (a_0=1,; a_1=1). This is the Fibonacci sequence shifted:
[ a_N = F_{N+1}, ] where (F_0=0,; F_1=1,; F_2=1,; F_3=2,\ldots)

2. Maximum number of inversions

In (P_N), any two positions (i<j) with (j-i\ge 2) are comparable because every integer (\ge 2) is a sum of (2)'s and (3)'s, yielding a directed path (i \to i+2 \to \cdots \to j) or (i \to i+3 \to \cdots \to j). Consequently (\pi(i) < \pi(j)) for all such pairs in any linear extension. The only pairs that can be inverted are adjacent positions ((i,i+1)).

If both ((i,i+1)) and ((i+1,i+2)) were inverted, we would have (\pi(i)>\pi(i+1)>\pi(i+2)), implying (\pi(i)>\pi(i+2)), which contradicts the required relation (i \prec i+2). Hence no two adjacent inversions can occur consecutively. The number of inverted adjacent pairs is therefore at most the size of an independent set in a path of (N) vertices, i.e. (\lfloor N/2\rfloor).

The permutation defined by [ \pi(2k-1)=2k,\quad \pi(2k)=2k-1 \quad (k=1,\ldots,\lfloor N/2\rfloor),\quad \text{and } \pi(N)=N \text{ if } N \text{ is odd} ] has exactly (\lfloor N/2\rfloor) inversions (the pairs ((2k-1,2k))) and satisfies all constraints:

  • odd positions (2,4,6,\ldots) increase;
  • even positions (1,3,5,\ldots) increase;
  • for any (i), (\pi(i)<\pi(i+3)) because (i) and (i+3) have opposite parity and (\pi(i)=i\pm1,;\pi(i+3)=i+3\mp1).

Hence the maximum number of inversions is (\lfloor N/2\rfloor).

3. Total number of inversions

Let (S_N) be the sum of inversions over all (a_N) permutations. Using the same decomposition:

  • Type A ((N) at position (N)): inversions = those of the ((N-1))-permutation. Contribution: (S_{N-1}).
  • Type B ((N) at (N-1), (N-1) at (N)): the base ((N-2))-permutation contributes its inversions; additionally the pair ((N-1,N)) is an inversion (since (N > N-1) and (N-1) precedes (N)); no other new inversions occur because all other elements are (\le N-2). Contribution: (S_{N-2} + a_{N-2}).

Thus for (N\ge 2) [ S_N = S_{N-1} + S_{N-2} + a_{N-2}, \qquad S_0=S_1=0. ] Since (a_{N-2}=F_{N-1}), the generating function (G(x)=\sum_{N\ge0} S_N x^N) satisfies [ G(x) = xG(x) + x^2G(x) + \frac{x^2}{1-x-x^2}, ] so [ G(x) = \frac{x^2}{(1-x-x^2)^2} = F(x)^2, ] where (F(x)=\sum_{n\ge0}F_n x^n = \frac{x}{1-x-x^2}). Therefore [ S_N = \sum_{k=0}^N F_k F_{N-k}. ] Using the well‑known identity [ \sum_{k=0}^N F_k F_{N-k} = \frac{N L_N - F_N}{5}, ] where (L_N) are the Lucas numbers ((L_0=2,; L_1=1,; L_{n}=L_{n-1}+L_{n-2})), we obtain the closed form.

[ \boxed{\text{Number of permutations} = F_{N+1}} ] [ \boxed{\text{Maximum inversions} = \left\lfloor \frac{N}{2} \right\rfloor} ] [ \boxed{\text{Total inversions} = \sum_{k=0}^{N} F_k F_{N-k} = \frac{N L_N - F_N}{5}} ]

∎