# 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 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
Sep 2, 2018 at 13:49
• @puck he is making a joke :)
– Oray
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. 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
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
Sep 2, 2018 at 16:46