Ascending and Descending

We can solve this problem by applying some fairly advanced (but well-established) results in combinatorics.

First, we'll introduce the Young diagram (also known as a Ferrers diagram). Here is an example of a Young diagram:

http://upload.wikimedia.org/wikipedia/commons/f/f2/Young diagram for 541 partition.svg

A Young diagram consists of a number of rows of squares, where the rows are left-justified, and the number of squares in each row is less than or equal to the number of squares in the row above it. When we fill in the squares with numbers (from 1 to $n$ , where $n$ is the number of squares) a certain way, we get a Young tableau:

http://upload.wikimedia.org/wikipedia/commons/4/40/Young tableaux for 541 partition.svg

We fill in the squares so that the numbers are increasing in each row from left to right, and increasing in each column from top to bottom.

We are interested in Young tableau because of the Robinson-Schensted correspondence . Part of the RS correspondence is an algorithm that takes a permutation and generates an ordered pair of Young tableau which have the same shape. (Also, the number of squares in the Young tableau is equal to the number of elements in the permutation.)

For example, the permutation 3, 8, 1, 2, 4, 7, 5, 6 of the numbers from 1 to 8 produces the Young tableau

$\begin{array}{ccccccccccc} 1 & 2 & 4 & 5 & 6 & & 1 & 2 & 5 & 6 & 8 \\ 3 & 7 & & & & \text{and} & 3 & 4 & & & \\ 8 & & & & & & 7 & & & & \end{array}$

As the name suggests, this gives us a bijection, i.e. given an ordered pair of Young tableau that have the same shape, we can recover the original permutation.

Here are the key properties of the RS correspondence which are relevant for this problem:

• The longest increasing subsequence in the permutation is equal to the length of the first row of the Young tableau

• The longest decreasing subsequence in the permutation is equal to the length of the first column of the Young tableau

In the permutation 3, 8, 1, 2, 4, 7, 5, 6, the longest increasing subsequence is 1, 2, 4, 5, 6, and the longest decreasing subsequence is 8, 7, 6, so the length of the first row is 5 and the length of the first column is 3, as expected.

Consider a permutation as described in the problem. Then the length of the first row will be at most 3, and the length of the first column will be at most 3. But there are a total of 9 elements, which means the shape of the Young tableau must be a $3 \times 3$ grid. Therefore, the number of permutations we seek is $k^2$ , where $k$ is the number of ways we can fill a $3 \times 3$ Young diagram.

So the problem reduces to finding the number of ways we can fill a $3 \times 3$ Young diagram. It turns out that there is a handy and simple formula for this, known as the hook length formula . By the hook length formula, $k = \frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1} = 42,$ so the answer is $k^2 = 42^2 = 1764$ .

[Notifying @starwar clone .]