Number of ways to interleave identical ordered sequences How many ways to interleave three identical sequences (X,Y,Z) keeping the relative order? Possible ways are such as XYZXYZXYZ, XXXYYYZZZ and etc., as long as you can pick out 3 groups of XYZ with the order.
This question comes from my son's middle school math contest. For this particular problem, I was able to use back track and recursive approach to get the answer which is 42. But I feel there might be a more general and simple approach given the answer happens to be 7x6.
 A: Too long for a comment, but not a complete answer.
It looks like the general formula might be:
$$\frac{1}{\binom{n+1}{1}\binom{n+2}{2}\cdots\binom{n+m-1}{m-1}}\frac{(nm)!}{n!^m}$$
when interleaving $n$ identical sequences of length $m$.
Note that, by the Young Tableau argument in comments, this would have to be symmetric in $m,n$. Surprisingly, this formula is symmetric, since it can be rewritten as:
$$(nm!)\frac{1!2!3!...(m-1)!1!2!\dots (n-1)!}{1!2!\cdots(n+m-1)!}$$

How I came to this conjecture
In short: Brute force number crunching, with some hope that it was like Catalan numbers.
Working on the basis that this is "like" the Catalan numbers, I tried the case of $n$ sequence of three elements, $X,Y,Z$, and the theory that the value is of the form:
$$\frac{1}{f(n)}\frac{(3n)!}{n!^3}$$
As it turns  out, $f(n)$ is, for the first 21 values, at least, always an integer, and, according to OEIS, they match the "Pentagonal pyramidal numbers", so that we might conjecture that $f(n)=(n+1)^2(n+2)/2$.
$$\begin{matrix}
n&f(n)\\
0&1\\
1&6\\
2&18\\
3&40\\
4&75\\
5&126\\
6&196\\
7&288\\
8&405\\
9&550\\
10&726\\
11&936\\
12&1183\\
13&1470\\
14&1800\\
15&2176\\
16&2601\\
17&3078\\
18&3610\\
19&4200\\
20&4851
\end{matrix}$$
So it looks like you get the formula for $n$ sequences of $3$ elements is:
$$\frac{2}{(n+1)^2(n+2)}\binom{3n}{n,n,n}$$

For interleaving sequences of four elements, XYZW, you seem to get:
$$\frac{12}{(n+1)^3(n+2)^2(n+3)}\binom{4n}{n,n,n,n}$$

For sequences with five elements, the value seems to be:
$$\frac{288}{(n+1)^4(n+2)^3(n+3)^2(n+4)}\binom{5n}{n,n,n,n,n}$$
OEIS told me the sequence $1,2,12,288$ was the superfactorial sequence, which means:
$$1=1!, 2=2!1!, 12=3!2!1!, 288=4!3!2!1!$$
For that, I got my conjectured answer at the top.
