TAOCP 5.1.4 Exercise 4

Let a permutation $\pi = a_1 a_2 \cdots a_{n^2}$ of $\{1,2,\dots,n^2\}$.

taocpmathematicsalgorithmsvolume-3

Section 5.1.4: Tableaux and Involutions

Exercise 4. [**] [M24] Continuing exercise 8, find a “simple” formula for the exact number of permutations of ${1,2,\dots,n^2}$ that have no monotonic subsequences of length greater than $n$.

Verified: yes
Solve time: 2m42s

Let a permutation $\pi = a_1 a_2 \cdots a_{n^2}$ of ${1,2,\dots,n^2}$. Apply the Robinson–Schensted correspondence to $\pi$, producing a pair $(P,Q)$ of standard Young tableaux of the same shape $\lambda \vdash n^2$.

A fundamental property of RSK is the precise identification of the longest monotone subsequences in terms of $\lambda$:

  • The length of the longest increasing subsequence of $\pi$ equals $\lambda_1$, the length of the first row of $\lambda$.
  • The length of the longest decreasing subsequence of $\pi$ equals $\lambda'_1$, the length of the first column of $\lambda$.

This is the correct translation of Schensted’s theorem.

The condition in the problem is that $\pi$ has no monotonic subsequence of length greater than $n$. This means simultaneously:

$$ \lambda_1 \le n, \quad \lambda'_1 \le n. $$

These two inequalities describe exactly the partitions whose Ferrers diagram fits inside an $n \times n$ square. Indeed, $\lambda_1 \le n$ bounds the number of cells in each row, and $\lambda'_1 \le n$ bounds the number of cells in each column, so every row and every column has length at most $n$.

Hence the shape $\lambda$ must satisfy:

$$ \lambda \subseteq n \times n. $$

By the RSK correspondence, permutations of ${1,\dots,n^2}$ are in bijection with pairs $(P,Q)$ of standard Young tableaux of the same shape $\lambda \vdash n^2$. Therefore, the permutations satisfying the condition are in bijection with all pairs $(P,Q)$ where $\lambda \subseteq n \times n$.

For a fixed shape $\lambda$, the number of standard Young tableaux of shape $\lambda$ is $f^\lambda$, so the number of pairs $(P,Q)$ of that shape is $(f^\lambda)^2$.

Summing over all admissible shapes gives the total number of permutations:

$$ \boxed{\sum_{\lambda \subseteq n \times n} (f^\lambda)^2}. $$

Here $f^\lambda$ may be computed via the hook-length formula:

$$ f^\lambda = \frac{(n^2)!}{\prod_{u \in \lambda} h(u)}. $$

This completes the corrected argument. ∎