7
$\begingroup$

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$.

$\endgroup$
7
  • 2
    $\begingroup$ The answer is always 42 $\endgroup$
    – xhienne
    Sep 2, 2018 at 11:57
  • $\begingroup$ 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 :-) $\endgroup$
    – puck
    Sep 2, 2018 at 13:49
  • $\begingroup$ @puck he is making a joke :) $\endgroup$
    – Oray
    Sep 2, 2018 at 13:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mr Pie
    Sep 2, 2018 at 16:38
  • 1
    $\begingroup$ @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 ;) $\endgroup$
    – Oray
    Sep 2, 2018 at 16:45

1 Answer 1

6
$\begingroup$

The answer is

$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

$\endgroup$
1
  • 1
    $\begingroup$ very good explanation! u even explained th general formula thanks. $\endgroup$
    – Oray
    Sep 2, 2018 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.