# Class Seating Arrangement

There are $25$ students with distinct heights in a class. The seats are arranged in the class like a square array ($5$x$5$) and students are seated such a way that each person will be taller than both the student in front of and left to her/him.

In how many different ways can this operation be done?

Hint: If this question was asked for $9$ students with $3$x$3$ square array matrix, then the answer would be $42$.

• The answer is always 42 Commented Sep 2, 2018 at 11:57
• I don't think so. Do that in a 2x2 matrix. Then there are only 24 ways to seat the students and these still include combinations that conflict the given requirement. (Edit: oh i saw the link only now... sorry :-)
– puck
Commented Sep 2, 2018 at 13:49
• @puck he is making a joke :)
– Oray
Commented Sep 2, 2018 at 13:50
• Hey, you seem to love these kinds of math puzzles. I think you might like this site proposal (not accessible via Google Chrome, but Safari works). And if you want, you can join the related chatroom. Commented Sep 2, 2018 at 16:38
• @user477343 this kind of puzzle is like finding the way how to do it, not actually solve it manually in my opinion, and learn as well while searching ;)
– Oray
Commented Sep 2, 2018 at 16:45

$701149020$

Because

We may rank the students by height $\{1,2,3,\cdots,25\}$.
Since each student must be taller than any to their left (in their row) and any in front of ("above") them (in their column) then any such square is a standard Young tableau of shape $(5,5,5,5,5)$ (by definition).
The number of standard Young tableau of shape $\lambda$, $d_\lambda$, is given by the hook-length formula, $d_\lambda = \frac{n!}{\prod h_\lambda (i,j)}$
...where the hook length, $h_\lambda (i,j)$, is the number of cells which are either in row $i$ but not to the left of $j$ or in column $j$ but not above $i$.

As such

$d_{(5,5,5,5,5)} = \frac{25\cdot 24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}$

$d_{(5,5,5,5,5)} = \frac{25\cdot 24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(5\cdot 5)\cdot (8\cdot 6\cdot 7\cdot 6\cdot 5)\cdot (6\cdot 3)\cdot (4\cdot 4)\cdot (5\cdot 3)\cdot (7\cdot 2)\cdot (4\cdot 3)\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 2\cdot 1}$

$d_{(5,5,5,5,5)} = \frac{25\cdot 24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{25\cdot (8\cdot 6\cdot 7\cdot 6\cdot 5)\cdot 18\cdot 16\cdot 15\cdot 14\cdot 12\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 2\cdot 1}$

$d_{(5,5,5,5,5)} = \frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 17\cdot 13\cdot 11\cdot 10\cdot 3}{8\cdot 6\cdot 7\cdot 6\cdot 5}$

$d_{(5,5,5,5,5)} = \frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 17\cdot 13\cdot 11\cdot 10\cdot 3}{(8\cdot \frac{6}{2})\cdot (7\cdot \frac{6}{2})\cdot (5\cdot 2\cdot 2)}$

$d_{(5,5,5,5,5)} = \frac{24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19\cdot 17\cdot 13\cdot 11\cdot 10\cdot 3}{24\cdot 21\cdot 20}$

$d_{(5,5,5,5,5)} = 23\cdot 22\cdot 19\cdot 17\cdot 13\cdot 11\cdot 10\cdot 3$

$d_{(5,5,5,5,5)} = 701149020$

Note that with $9$ students this would be:

$d_{(3,3,3)} = \frac{9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{5\cdot 4\cdot 3\cdot 4\cdot 3\cdot 2\cdot 3\cdot 2\cdot 1}$

$d_{(3,3,3)} = \frac{9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 3)\cdot (4\cdot 2)\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}$

$d_{(3,3,3)} = \frac{9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{9\cdot 8\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}$

$d_{(3,3,3)} = 7\cdot 6 = 42$

In general for squares of side $n$ these are the

$n$th $n$-dimensional Catalan numbers
with an entry at OEIS A039622

...and for rectangles of sides $m,n$ the result has

an entry at OEIS A060854

• very good explanation! u even explained th general formula thanks.
– Oray
Commented Sep 2, 2018 at 16:46