1
$\begingroup$

I tried each possibility and add them together, which was very time consuming. What is the easiest way to solve this problem? Thank you very much in advance!

How many ways are there to arrange the digits $1$ through $9$ in this $3 \times 3$ grid, such that the numbers are increasing from left to right in each row and increasing from top to bottom in each column?

enter image description here

$\endgroup$
4
$\begingroup$

Putting numbers into such an arrangement of boxes so that they are increasing along rows and increasing down columns is a classic problem, and these objects are called standard Young tableaux.

If there are $\lambda_i$ boxes in the $i$th row, then the quantity you want is usually denoted $f^\lambda$ with $\lambda=(\lambda_1,\lambda_2,...)$. It turns out that $f^\lambda$ is the dimension of the irreducible representation of the permutation group associated with the integer partition $\lambda$ (outside of scope to define all this here).

There is a formula for $f^\lambda$ for all $\lambda$ which you can find here: https://en.wikipedia.org/wiki/Hook_length_formula

The particular case of $n\times n$ grids has the solution $ (n^2)! \prod_{k=0}^{n-1}\frac{k!}{(n+k)!}$ and for $n=3$ this is $42$.

$\endgroup$
2
$\begingroup$

Some things we know: - The first item in the first row must be $1$ and the last item in the third row must be $9$. - Whatever works horizontally will work vertically.

Let’s start with $1 ,2 ,.$ for the first row.
$1 2 3$ $1 2 3$ $1 2 3$ $1 2 3$ $ 1 2 3$
$4 5 6$ $4 5 7$ $4 5 8$ $4 6 7$ $ 4 6 8$
$7 8 9$ $6 8 9$ $6 7 9$ $5 8 9$ $ 5 7 9$
That’s $5$.

$1 2 4$ $1 2 4$ $1 2 4$ $1 2 4$ $ 1 2 4$
$3 5 6$ $3 5 7$ $3 5 8$ $3 6 7$ $ 3 6 8$
$7 8 9$ $6 8 9$ $6 7 9$ $5 8 9$ $ 5 7 9$
That’s $5$.

$1 2 5$ $1 2 5$ $1 2 5$ $1 2 5$ $ 1 2 5$
$3 4 6$ $3 4 7$ $3 4 8$ $3 6 7$ $ 3 6 8$
$7 8 9$ $6 8 9$ $6 7 9$ $4 8 9$ $ 4 7 9$
That’s $5$.

$1 2 6$ $1 2 6$ $1 2 6$ $1 2 6$
$3 4 7$ $3 4 8$ $3 5 7$ $3 5 8$
$5 8 9$ $5 7 9$ $4 8 9$ $4 7 9$
That’s $4$.

$1 2 7$ $ 1 2 7$
$3 4 8$ $ 3 5 8$
$5 6 9$ $ 4 6 9$
That’s $2$. That’s a total of $21$.

$21 × 2 = 42$ is the answer

$\endgroup$
  • $\begingroup$ How do we find out the answer without doing this ... This is way too long $\endgroup$ – Tejus Mar 11 '16 at 17:32
  • $\begingroup$ I agree. There should be a simple way. $\endgroup$ – user321645 Mar 11 '16 at 22:20
  • $\begingroup$ @teamember That's the only way. You can only shorten it by imagining the permutations instead of putting them down.(In fact I solved this in around 2 minutes without writing anything down) $\endgroup$ – Win Vineeth Mar 11 '16 at 23:45
0
$\begingroup$

The $1$ has to be upper left and the $9$ has to be lower right. The $2$ can be upper center or middle left. By symmetry, we might as well put the $2$ in upper center and double the count for the middle left. The $8$ has two choices. For each of them, there will be two choices for $3$ and two for $7$. That gives eight grids, each of which will have constraints on $4,5,6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy