# Combinatorics arrangement on chessboard

How many ways can we fill $$n\times n$$ chessboard (with any number of pawns), so that, out of every two pawns, one of them was to the left , and down from the second?

My ideas:

I think that this task can be solved, by finding a recursive formula, and then using annihilators method (or any other), to make it iterative. Only if I could find it out...

I imagine descending sequence of chessboards, such that $$n+1$$-th chessboard is $$n$$-th one with no rightmost column and topmost verse. Imagine $$4 \times 4$$ chessboard and consider its rightmost column and topmost verse:

| x | a | a | y |
|   |   |   | a |
|   |   |   | a |
|   |   |   | x |

• If we place our pawn on $$x$$ points, we end our recurrence (there are no more option to place another pawn).
• If we place pawn on $$y$$ points, we run recurrence another time for $$3\times 3$$ chessboard.
• If we place it on $$a$$ points, then... i don't know. We have more options than recurrence would give us on $$3\times 3$$ chessboard. Of course, we can run recurrence with 2 arguments, but I can't solve it with any known method.

Whereas the above considerations we can find out that the formula is something like $$T(n)=T(n-1)+\underset{something}{\underbrace{\qquad\ldots\qquad}}+2$$

I can, of course be completely wrong.

Let the top right coordinate of the board be $(1,1)$ and the bottom left coordinate be $(n,n)$. Let $k$ pawns be placed (notice that $k \leq n$) and let their coordinates be $(x_i, y_i)$ for $1\leq i \leq k$.

Your condition says that if $i\neq j$, then either $x_i < x_j$ and $y_i < y_j$ or $x_i > x_j$ and $y_i > y_j$.

So, suppose that we have $k$ points with all $x$ coordinates different and all $y$ coordinates different. Sort these points in increasing order of their $x$-coordinates. Then the arrangement is a good one if and only if they are also sorted in increasing order of their $y$-coordinates.

It follows that the number of such points is the square (because there are two of them, one for $x$ and one for $y$ coordinates) of the number of (strictly) increasing sequences of length $k$ coming from $\{1,\ldots, n\}$.

So let's count these. For any subset of the integers $\{1, \ldots, n\}$, there is exactly one way of ordering it in strictly increasing order, so there are $\displaystyle \binom{n}{k}$ such sequences of length $k$, and thus $\displaystyle \binom{n}{k}^2$ such placements of $k$ pawns. Summing up, we get a total of $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$ placements of any number of pawns by Vandermonde's identity.

Another Solution (sketch):

For any of the $\displaystyle \binom{2n}{n}$ paths from $(0,1)$ to $(n,n+1)$ (these are points just off the board) with moves that only go left and down (i.e., only increasing coordinates), leave a pawn on a square if you came into the square by increasing the $x$ coordinate and left it by increasing the $y$ coordinate. Show that each such path leaves a different placement of pawns and that each legal placement of pawns is achieved by such a path.

Let $T(p,q)$ be the number of ways you can do it with the top, right-most pawn on square $(p,q)$. As you have found, with your $x$ points, $T(1,4) = T(4,1)=1$.
With your $y$ point, there are either no more pawns, or the top, right-most next pawn is on one of the nine squares in the $3\times3$ square. So $T(4,4)=1+T(3,3)+T(3,2)+...+T(1,1)$.
Lastly, you have to add up $T(i,j)$, (plus 1 for the no-pawn solution).