# How to speed up the calculation of the number of $4 \times 4$ Young tableaux

I find the problem of calculating $$n \times n$$ Young tableaux from here. I can get the number of $$3\times 3$$ Young tableaux by violent enumeration is $$42$$

Partition[#, 3] & /@
Select[Permutations[
Range[9]], ((#[[2]] > #[[1]]) && (#[[3]] > #[[2]]) && (#[[5]] > \
#[[4]]) && (#[[6]] > #[[5]]) && (#[[8]] > #[[7]]) && (#[[9]] > \
#[[8]]) && (#[[1]] < #[[4]]) && (#[[4]] < \
#[[7]]) && (#[[2]] < #[[5]]) && (#[[5]] < #[[8]]) && (#[[3]] < \
#[[6]]) && (#[[6]] < #[[9]])) &] // Length


But in the case of $$4\times 4$$, the calculation speed of my algorithm below is very slow. How can I modify it to improve the calculation speed?

Needs["Combinatorica"]
s = {};
k = 0;
rule = ((#[[1]] < #[[2]]) && (#[[2]] < #[[3]]) && (#[[3]] < #[[4]]) \
&& (#[[5]] < #[[6]]) && (#[[6]] < #[[7]]) && (#[[7]] < #[[8]]) && \
(#[[9]] < #[[10]]) && (#[[10]] < #[[11]]) && (#[[11]] < #[[12]]) && \
(#[[13]] < #[[14]]) && (#[[14]] < #[[15]]) && (#[[15]] < #[[16]]) && \
(#[[1]] < #[[5]]) && (#[[5]] < #[[9]]) && (#[[9]] < #[[13]]) && \
(#[[2]] < #[[6]]) && (#[[6]] < #[[10]]) && (#[[10]] < #[[14]]) && \
(#[[3]] < #[[7]]) && (#[[7]] < #[[11]]) && (#[[11]] < #[[15]]) && \
(#[[4]] < #[[8]]) && (#[[8]] < #[[12]]) && (#[[12]] < #[[16]])) &;

For[i = 1, i <= 16! - 1, i++,
If[MatchQ[CombinatoricaNthPermutation[i, Range[16]], _?(rule)],
k++;]]
k

• @Bill Thank you for pointing out the typo. I wrote (#[[1]]<#[[4]]) again in that place. And I have updated my question. Commented Mar 1, 2020 at 5:29

## 1 Answer

Here is a recursive code that constructs the Young tableaux directly:

fill[L_, x_] := If[x == Length[L]^2 + 1, Sow[L],
fill[#, x + 1] & /@ Reap[Do[If[Length[L[[i]]] < Length[L] &&
(i == 1 || Length[L[[i]]] < Length[L[[i - 1]]]),
Sow[ReplacePart[L, i -> Append[L[[i]], x]]]],
{i, Length[L]}]][[2, 1]]]
YT[n_] := Reap[fill[ConstantArray[{}, n], 1]][[2, 1]]


You get the 24'024 Young tableaux $$4\times4$$ in about two seconds:

YT[4]
(*    {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 13}, {12, 14, 15, 16}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 14}, {12, 13, 15, 16}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 15}, {12, 13, 14, 16}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 12, 13}, {11, 14, 15, 16}},
...
{{1, 5, 9, 11}, {2, 6, 10, 14}, {3, 7, 12, 15}, {4, 8, 13, 16}},
{{1, 5, 9, 12}, {2, 6, 10, 13}, {3, 7, 11, 14}, {4, 8, 15, 16}},
{{1, 5, 9, 12}, {2, 6, 10, 13}, {3, 7, 11, 15}, {4, 8, 14, 16}},
{{1, 5, 9, 12}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 13, 16}},
{{1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12, 16}}}    *)


As for the 701'149'020 Young tableaux $$5\times5$$, further optimizations may be necessary.