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.
 A: 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.
A: 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).
