a fun grid combinatorics puzzle that has been bothering me Suppose that we fill out the grid with numbers given only three rules:

*

*each box gets its own distinct number

*the numbers that we are allowed to use are $1-8$

*a box that contains a smaller number points to a box that contains a larger number

How many ways can we fill out our grid?
And if that question is solved, can we solve the same problem for a $10$-box grid? What about a $n$-box grid?
 A: I claim that this is the same as the number of ways to write a string of $5=\frac82+1$ pairs of balanced brackets (such as ()()()()() or ((((())))) etc.), which is known to be the fifth Catalan number $\frac1{5+1}\binom{2\cdot 5}5=42$.
Take your array of boxes, and add the two missing corner pieces to make a rectangle (and add the obvious arrows). Add the numbers $0$ and $9$ to your list of numbers to write. Clearly $0$ and $9$ have to go into the two boxes we just added, so we haven't really changed the problem.
We will place numbers into the grid one by one in ascending order. Note that this way we only have to specify which column we want to place them in, as we clearly have to place the next number in the topmost vacant spot in one of the columns. This means that any legal placement of the numbers is uniquely given by some order of 5 "left"s and 5 "rights"s. This takes care of all the downward pointing arrows.
The rightward pointing arrows mean exactly that we can never, at any stage in this process, have placed more numbers in the right-hand column than in the left-hand column, as this would force us to place a larger number to the left of a smaller number at a later stage. And this is exactly the same requirement that a balanced string of brackets has.
It is not difficult to see how this generalises to other sizes, as long as the arrows all point to the right and down, and the grid is a $2\times k$ rectangle, possibly missing the top left or the bottom right square (or both). Anything else, and more thinking will be required.
A: In your diagram, there are two missing corners, but you get an equivalent problem if you fill those corners to make a $5\times 2 $ grid, add in the corresponding arrows, and ask the number of ways to fill the boxes with the numbers $1$ to $10$. 
But this corresponds exactly to a standard Young tableaux, or SYT, where the underlying Young diagram is a $5\times 2$ grid. The number of SYT's is given by the hook length formula, which in this case amounts to
$$
\frac{10!}{1\cdot 2^2\cdot 3^3\cdot 4^4\cdot 5^2\cdot 6}=\frac{1}6\binom{10}{5}=C_5
$$
The same argument generalizes to arbitrary $n\times 2$ grids with two corners missing, and arrows pointing right and down from every box. In general, the number of ways to fill the grid is $\frac1{n+1}\binom{2n}n=C_n$, the $n^\text{th}$ Catalan number.
