3
$\begingroup$

I'm trying to solve a problem by using combinatorics. The problem goes like this:

I want to place $m$ balls in a $n\times n\times n$ chessboard. No two balls should be adjacent. Thus, no two of them should be the nearest neighbor (each location in the chessboard has six nearest neighbors).

For example: if a ball is placed at (1,1,1), there must be no ball at (0,1,1), (1,0,1), (1,2,1), (2,1,1), (1,1,0), (1,1,2).

For the ball at the corner location, like (0,0,0), there must be no ball at (0,0,1), (0,1,0) and (1,0,0).

How many different ways to put these $m$ balls? Is this problem solvable in general? Is it possible to write down a generating series for such problem?

$\endgroup$
  • $\begingroup$ If two rooks are at (0,0,0) and (0,1,1) are they attacking? Or do they need to differ by 1 in only one coordinate to attack? [Also suggest not calling them rooks] $\endgroup$ – coffeemath May 7 '18 at 2:22
  • $\begingroup$ No, they are not, if a rook is placed at (0,0,0), only rooks on (0,1,0), (1,0,0),(0,0,1) can attack it. $\endgroup$ – Lonitch May 7 '18 at 2:25
  • $\begingroup$ Sorry for the confusion, I have changed them to "balls" and added an example @coffeemath $\endgroup$ – Lonitch May 7 '18 at 2:49
  • $\begingroup$ The problem is rephrased, sorry for the confusion @darij grinberg $\endgroup$ – Lonitch May 7 '18 at 2:51
  • $\begingroup$ Now that it's been clarified, I think it's a good question (will upvote) Note that positions on a side or at a corner have less than 6 nearest neighbors. $\endgroup$ – coffeemath May 7 '18 at 9:53
2
$\begingroup$

Quick answer is there isn't a formula and there is unlikely to be one in the future.

In terms of graph theory, the request is for the number of independent vertex sets of size m in the n X n X n grid graph. A search of Oeis for 'independent sets' gives hundreds of results and a search for 'nonattacking' gives even more - so efforts have been made on many graphs. In general, counting independent sets on a random given graph is NP complete, but the grid graph isn't random so that doesn't apply here.

It is easiest to start by looking at the n X n grid or even k X n grid for some fixed k. In Oeis a lot of these will be found under 'nonattacking wazir'. The main sequence counting all independent sets on the n X n grid is A006506 (37 terms are known) and that for the n X n X n grid is A292702 (just 4 terms known). [that last one could probably be raised to 5 or 6 - since 36(6^2) is no more than 37]. For an n X k grid there is A089934 and that is probably the easiest place to begin. Each column (fixed k) is a linear recurrence. The best known method for enumeration is to construct a state machine that processes the grid row by row - after each row is added what is behind the final row is no longer relevant (except the count of the number of balls that have been added). The number of states required is the number of ways of placing balls in that final row which is given by the Fibonacci numbers. Using symmetry it is possible to reduce the number of states by approximately two and it turns out that this number of states almost always exactly matches the order of the linear recurrences, suggesting that there is a level of complexity that cannot be easily removed. For the n X n X n grid the frontier consists of a n X n slice through the grid.

Your question is actually asking for more detail - not just the total number of independent sets, but only those of a specific size. For small m these will be polynomials. (most obviously for m=1). For the n X n grid there are sequences in Oeis that cover small m (A172225, A172226, A172227, A172228, A178409, A201507, A201508, A201510) but I am not sure anybody has bothered to create them for the n X n X n grid.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your reply, I'm actually thinking about building a state machine like the one you suggested above. $\endgroup$ – Lonitch May 8 '18 at 4:06

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.