1
$\begingroup$

Let me start off by saying that I'm not a mathematician, so this is probably an easy problem to solve, but I haven't been able to yet..

The problem is that I want to place $n$ objects on a grid with $N$ grid points, and I want to count the number of different permutations this is possible, or at the least an approximate number. However, I am not allowed to place my objects just next to others, and therefore the number of possible places to place them, decreases by a number $s$ after having placed an object.

You can see here, how the situation works for a 4x4 grid with $n=1$ (gives $\binom{4\times 4}{1}=16$ possibilities since no grid points are masked out) and for $n=2$ where one grid point is occupied - removing the option to use its neighboring grid points.

Having placed a single object, the number of grid points available are not $16-1=15$, but rather $16-9=7$. Therefore, the total number of permutations goes from $\binom{16}{2}=16\times 15 / 2 = 120$ to $16\times 7/2=56$. Here I showed it with periodic boundaries as this is preferred, but it is not necessary.

I guess the binomial coefficient $\binom{N}{n}$ is a good starting place, as this can give the number of permutations for a static size grid, however, I haven't been able to figure out how to find it for a non-static $N$.

I thought I could get an approximate answer by just calculating $$ \prod_{i=0}^n N-i\cdot s $$ but this obviously double counts a lot of the same configurations.

$\endgroup$
8
  • $\begingroup$ Welcome to stackexchange. If you edit the question to show us a few complete worked out examples for some small but typical values of $N$, $n$ and $s$ it will be easier for us to understand just what you want. Then we may be able to help. $\endgroup$
    – Ethan Bolker
    Jun 1, 2020 at 15:06
  • $\begingroup$ Just edited it for you, hopefully it clears things up. $\endgroup$
    – Anders BB
    Jun 1, 2020 at 16:04
  • $\begingroup$ I am still confused about the constraints. Please edit the question to show us all the possible configurations you want to count for $s = 3$ on (say) a $6 \times 6$ grid first for for $n=1$, then $n=2$, then $n=3$. I suspect that your counting problem does not have an easy exact answer. Estimates might be possible. If you tell us where the problem comes from and what you need the answer for we may be able to help more. $\endgroup$
    – Ethan Bolker
    Jun 1, 2020 at 16:13
  • $\begingroup$ Is it clearer now? The number of configurations increase rapidly, so creating it for a $6\times 6$ grid with $n=3$ would be a rather daunting task. Estimates would be more than welcome $\endgroup$
    – Anders BB
    Jun 2, 2020 at 7:49
  • $\begingroup$ Why don't you divide $112/2 = 56$ in your example as you did with $16 x 15$? Also, if the first point is on the boundary there aren't $8$ adjacent squares eliminated. Or do the boundaries wrap, (i.e. upper left is adjacent to upper right and lower lower left, etc) -- is that what you meant by periodic boundaries? $\endgroup$
    – Ned
    Jun 2, 2020 at 12:52

1 Answer 1

Reset to default
0
$\begingroup$

Some thoughts toward an answer.

I think you are closer to an estimate than you think you are - your original idea is on the right track.

The problem with periodic boundary conditions (so placing your points on a torus) is in fact easier.

In your example you work with the requirement that points can't be immediate neighbors - they can share neither an edge nor a corner. Suppose too that $n << N$ and that the points are placed more or less at random, subject to the neighbor restriction. Then it's unlikely that the restricted areas from two points will overlap. That means that each point placed rules out $25$ vertices on the grid - the spot the point is on, its $8$ neighbors, and their neighbors too. So when $k$ points have been placed the next point can go in any of the remaining $N-25k$ places. That leads to the product in your question: $$ N(N-25)(N-50) \cdots (N- 25(n-1)). $$ But the order in which you placed the points doesn't matter, so to find the number of arrangements just divide that product by $n!$. That deals with what you call the double counting - you take care of it at the end all at once rather than by using binomial coefficients along the way.

There will be legal placements that aren't counted here, because two points could be two steps apart without conflict. That will matter more the closer $n$ is to the maximum number that will fit. If your application sprinkles fewer points in a larger grid this will give you a reasonable lower bound for the number of configurations.

$\endgroup$
4
  • $\begingroup$ Wow, I was much closer than I thought.. Have you decided that points are not allowed to be placed in a $5\times 5$ square on the grid instead of the $3\times 3$ I used in my example, or is there another reason for subtracting $25$ each time? Such that I can use the more general $1/n! \prod_{i=0}^{n-1} N - i\cdot s$ for $n\cdot s << N$? $\endgroup$
    – Anders BB
    Jun 3, 2020 at 7:08
  • $\begingroup$ Yes, subtracting $25$ for the $5 \times 5$ square because that approximation makes the counting easier, without changing the order of magnitude of the answer for sparse points. Your formula probably wants something involving $s^2$ instead of $s$. The $25$ is the case when the restriction is no direct touch. $\endgroup$
    – Ethan Bolker
    Jun 3, 2020 at 14:11
  • $\begingroup$ Well, $s$ can either be the number of grid points not allowed, so $s=25$ in this case, of the width of the mask, so $s^2=25$, but for the slightly more general case where the mask is not square, I think the first definition works better. Nevertheless, this works nicely, so thanks :) $\endgroup$
    – Anders BB
    Jun 3, 2020 at 16:11
  • $\begingroup$ OK I understand. For any restriction you need to make sure the restricted shapes don't overlap - so $5 \times 5$ squares when you don't want neighbors, even though a horizontal distance of $2$ would suffice. $\endgroup$
    – Ethan Bolker
    Jun 3, 2020 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .