Intereting Posts

Calculate intersection of vector subspace by using gauss-algorithm
2D Coordinates of Projection of 3D Vector onto 2D Plane
Congruence question with divisibility
Solve this Recursive Integral
Proof If $AB-I$ Invertible then $BA-I$ invertible.
Property of Entire Functions
For primes $p≡3\pmod 4$, prove that $!≡±1\pmod p$.
Cube roots modulo $p$
Countability of disjoint intervals
Probability Density Function Validity
Evaluating $\lim\limits_{n\rightarrow \infty} \frac1{n^2}\ln \left( \frac{(n!)^n}{(0!1!2!…n!)^2} \right)$
mathematical difference between column vectors and row vectors
Give an example of a noncyclic Abelian group all of whose proper subgroups are cyclic.
What does “removing a point” have to do with homeomorphisms?
Vector Spaces and AC

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?

For example:

$M = 2, N = 2$, ans $= 6$

$M = 3, N = 2$, ans $ = 28$

$M = 6, N = 15$, ans $= 2560$

- Finding an MST among all spanning trees with maximum of white edges
- Split a set of numbers into 2 sets, where the sum of each set is as close to one another as possible
- Is factoring polynomials as hard as factoring integers?
- Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
- Sum of the series formula
- Detecting perfect squares faster than by extracting square root

It is possible to solve this using graph theory. However, I am (more) interested in a combinatorial approach (A closed form solution).

Similar problem

- Matching Hats AND Coats Problem
- Proof of $\sum_{0 \le k \le a} {a \choose k} {b \choose k} = {a+b \choose a}$
- Traveling salesman problem: a worst case scenario
- Can 12 teams in 6 disciplines play 6 rounds without repetition?
- Total number of unordered pairs of disjoint subsets of S
- Total number of solutions of an equation
- Probability of a substring occurring in a string
- How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?
- Asymptotics of binomial coefficients and the entropy function
- A tiling puzzle/question

The complete answer to this question is contained in the Knights

polynomials. By definition, the coefficient of $q^k$ in the $m\times n$

knights polynomial, $K_{m,n}(q)$, is the number

of ways that $k$ non-attacking knights can be placed on an $m\times n$

board. Of course, it’s a tautology to say that this solves the problem,

but there is an algorithm to compute them. Using this algorithm, the

first six $m\times n$ knights polynomials (per your request) are

\begin{align}

K_{1,1}(q) &= q+1 \\

K_{2,2}(q) &= q^4+4 q^3+6 q^2+4 q+1 \\

K_{3,3}(q) &= 2 q^5+18 q^4+36 q^3+28 q^2+9 q+1\\

K_{4,4}(q) &= 6 q^8+48 q^7+170 q^6+340 q^5+412 q^4+276 q^3+96 q^2+16 q+1\\

K_{5,5}(q) &= q^{13}+15 q^{12}+158 q^{11}+994 q^{10}+3679 q^9+8526 q^8+12996

q^7+13384 q^6 \\

&+ \; 9386 q^5+4436 q^4+1360 q^3+252 q^2+25 q+1\\

K_{6,6}(q) &= 2 q^{18}+40 q^{17}+393 q^{16}+2560 q^{15}+12488 q^{14}+47684

q^{13}+141969 q^{12} \\

&+ \; 323476 q^{11}+556274 q^{10}+716804 q^9+688946

q^8+491140 q^7+257318 q^6 \\

&+ \; 97580 q^5+26133 q^4+4752 q^3+550 q^2+36 q+1

\end{align}

Note that these polynomials agree with the results that you provide. For example, the coefficient of $q^{15}$ in $K_{6,6}$ is 2560, corresponding to your statement that $M=6,N=15 \Rightarrow \text{ans} =2560$. The coefficients of $q^2$ also agree with this OEIS sequence.

The algorithm to compute these is very similar to the obviously related Kings

problem. Neil Calkin and his REU students provide a very thorough analysis

of that problem in two papers in Congressus Numerantium. Shaina Race has a

publicly accessible presentation of their results here. I published a paper presenting

an implementation of the algorithm in Mathematica V5. The technique for counting

knights is a bit more complicated but uses very similar ideas. Unfortunately,

I’ve been able to compute the $7\times 7$ knights polynomial but my computer

chokes on $8\times 8$, the size of an actual chess board.

Firstly, see OEIS for a list of numbers. E.g. Sequence A172132 counts the number of ways to place 2 nonattacking knights on an $n\times n$ board. Note this site should be among the first ones (besides Google) which you should visit when you have a combinatorial problem (like counting).

Secondly, I don’t have a “closed formula” for this problem, but an algorithm which should work for the given input limits. Since the problem is of quite an ACM/ICPC nature, I would assume you’d be satisfied with an algorithm which (when implemented correctly) would give the answer in reasonable time.

My algorithm is dynamic programming (Some prefer “recursion” because no optimization is involved. I don’t distinguish them here.).

Let $f[i,j,v_{last},v_{second\_last}]$ denote the number of ways to place $j$ non-attacking knights in the first $i$ rows of the $n\times n$ board with the last and the second last rows having the states denoted by $v_{last}$ and $v_{second\_last}$. Those are two bit-vectors, with 1 being a knight. So a row with two knights in the 2nd and 5th cell when $n=5$ will be denoted as 01001.

So the most important part would be the equation (state transition equation)

$$

f[i,j,v_{last},v_{second\_last}] = \sum_{v_{third\_last}}f[i-1,j-\operatorname{popcount}(v_{last}),v_{second\_last},v_{third\_last}]

$$ where $\operatorname{popcount}(v)$ is the number of 1’s in bit-vector $v$.

Note the three vectors must be consistent (non-attacking).

There’re then $N M 2^{2M}$ states, and the transition takes another $2^M$ time, so the algorithm (if implemented properly) has a time complexity of $O(N M 2^{3M})$. The bound is not tight, since there’re many invalid combinations of vectors.

See http://oeis.org/A244081 and the crossreferences or my book http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf, page 283-285.

- Why do knowers of Bayes's Theorem still commit the Base Rate Fallacy?
- Let $V$ be a $K$-vector space, $f: V \rightarrow V$ a linear map. Under some condition, show that $v, f(v),…,f^n(v)$ are linearly independent.
- A maximal ideal is always a prime ideal?
- Is the orbit space of a Hausdorff space by a compact Hausdorff group Hausdorff?
- How can one prove $\lim \frac{1}{(n!)^{\frac 1 n}} = 0$?
- What's the relation between topology and graph theory
- Commutativity of “extension” and “taking the radical” of ideals
- if f(x) if differentiable and continuous, prove $\frac{af(a)-bf(b)}{a-b} = f(c) + cf'(c) $
- Playing the St. Petersburg Lottery until I lose everything
- Integer solutions of a cubic equation
- Prove $2^{1092}\equiv 1 \pmod {1093^2}$, and $3^{1092} \not \equiv 1 \pmod {1093^2}$
- Path connectedness is a topological invariant?
- Showing $(C, d_1)$ is not a complete metric space
- Why is $dy dx = r dr d \theta$
- Product of spaces is a manifold with boundary. What can be said about the spaces themselves?