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.