Project Euler Problem 916

Solution

Answer: 877789135

Using the Robinson–Schensted–Knuth correspondence:

The length of the longest increasing subsequence equals the first row length of the Young diagram.
The length of the longest decreasing subsequence equals the number of rows.

For permutations of ${1,\dots,2n}$:

“No decreasing subsequence longer than 2” means the Young diagram has at most 2 rows.
“No increasing subsequence longer than $n+1$” means the first row has length at most $n+1$.

A partition of $2n$ with at most two rows has shape $(a,2n-a)$ with $a\ge n$.

The constraint $a\le n+1$ leaves only:

$$(n,n), \qquad (n+1,n-1).$$

If $f^\lambda$ is the number of standard Young tableaux of shape $\lambda$, then the number of permutations with shape $\lambda$ is $(f^\lambda)^2$.

For a two-row shape $(a,b)$,

$$f^{(a,b)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$

Hence

$$f^{(n,n)}=\frac1{n+1}\binom{2n}{n}=C_n$$

(the Catalan number), and

$$f^{(n+1,n-1)} =\frac3{n+2}\binom{2n}{n-1} = C_n\cdot \frac{3n}{n+2}.$$

Therefore

$$P(n) = C_n^2\left(1+\left(\frac{3n}{n+2}\right)^2\right).$$

Computing this modulo $10^9+7$ for $n=10^8$ gives:

$$P(10^8)\equiv 877789135 \pmod{10^9+7}.$$

Answer: 877789135