In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard? 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$
It is possible to solve this using graph theory. However, I am (more) interested in a combinatorial approach (A closed form solution). 
Similar problem
 A: 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.
A: 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.
