About Warm-ups Problems News

Problem 19

Posted 11/04/2015 and updated 11/08/2015
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

This problem is inspired by cannons in Xiangqi, a.k.a. Chinese chess.

Suppose we put $k$ cannons in a $n\times n$ board. If there are three or more than three cannons in a row or column, they can attack each other. In other words, cannons are non-attacking if there are at most $2$ cannons in each row and column.

Clearly, for a $n\times n$ board, we can put at most $2n$ non-attacking cannons.

$a(n)$ is the number of ways to place $2n$ non-attacking cannons in a $n\times n$ board.

For example, $a(2)=1$, $a(3)=6$ and the following figure is an example of placing $8$ non-attacking cannons in a $4\times 4$ board.



An observation is that $a(n)\le \frac{(n!)(!n)}{2}$, where $!n$ is the number of derangments of $\{1,2,\cdots,n\}$.

Find $a(n)$.




----------------------

Updated 11/08/2015 and remarked by Dun Qiu


This problem has been already studied by R. Bricard in 1901, L. Erlebach and O. Ruehr in 1990, D. E. Knuth in 1990, and H. Anand, V. C. Dumir and H. Gupta in 1996.

The recursive formula of $a(n)$ is $a(n) = \frac{1}{2}n(n-1)^2((2n-3)a(n-2) + (n-2)^2a(n-3))$.

More information can be found on OEIS (A001499).






Back to top