2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.