Problem
| 1 | 3 | 6 |
| 2 | 4 | 7 |
| 5 | 8 | 9 |
How many ways can you arrange the numbers 1 through 9 in a 3-by-3 grid such that the following conditions hold?1
- Every number is greater than the number directly above it.
- Every number is greater than the number immediately to the left of it.
Solution
Insert the numbers into the grid one at a time, in order from 1 to 9. Each number has to be placed in an upper-left corner (there may be more than one way to do this). Forgetting about which number is in which box, just look at the shape they make. You will get a diagram like the one below. The number of ways to arrange numbers for each shape is always equal to the sum of the shapes feeding into it. The solution, 42, appears at the bottom of the diagram.2
1. I originally saw this problem posted here.
2. Number-filled grids with these properties are known as standard Young tableaux. The diagram used in the solution appears to be a subset of Young's lattice. Another way to find the solution is by using the Hook length formula.
