Finding unique patter of $M$ $1$s in an $N \times N$ matrix, the rest occupied by $0$s

Question

I am looking for a solution for a biological problem. I have a $10 \times 10$ matrix that I need to fill with $10$ molecules. They can occupy any cell in the matrix (they don't need to be next to each other) but the resulting pattern has to be unique, i.e. cannot be simply rotated or translated into the same pattern. Mirror symmetry is not allowed. You can consider it a binary problem where the ten molecules are represented by ten $1$s and the rest of the $90$ spaces in the matrix are $0$s. As far as I can tell after searching on this site, the answer is a variation of the Polya enumeration but none of the answers give the exact result to my particular problem. I started out thinking about this as a simple combinatorial problem of $C(100,10).$ However, that does not take into account the rotational and translational symmetry needed to reduce the number to only the unique patterns the ten molecules/digits can create. In more general terms, I am interested in expanding this problem with $M$ molecules within a $N \times N$ matrix.

Answer 1

I'll do this specifically for $M=10$ molecules in an $N\times N$ matrix. Some details depend on the residue of $M\bmod4$, so you'll need to make some small adjustments if you want to use an $M$ with a different residue, but I hope to explain the reasoning sufficiently for you to be able to make those adjustments on your own.

We can deal with translations by counting the number of configurations that fill certain bounding boxes. We can deal with rotations by accounting for rotational symmetry by dividing the counts by appropriate factors.

So let's count the patterns that fill a bounding box of width $w$ and height $h$. There are $wh$ cells in the bounding box, so the basic count of patterns is $\binom{wh}M$. But we mustn't count patterns that don't actually fill the bounding box. That yields $4$ conditions, which we can enforce by inclusion–exclusion.

There are $\binom{w(h-1)}M$ patterns that don't use the top row of the bounding box, another $\binom{w(h-1)}M$ for the bottom row, and then $2\binom{(w-1)h}M$ for the left and right column. There are $4$ pairs of a row and a column, and for each pair there are $\binom{(w-1)(h-1)}M$ patterns that don't use it. There are $\binom{w(h-2)}M$ patterns that use neither the top nor the bottom row, and $\binom{(w-2)h}M$ that use neither the left nor the right column. For three conditions violated simultaneously, the total count is $2\binom{(w-1)(h-2)}+2\binom{(w-2)(h-1)}M$, and for all four conditions simultaneously $\binom{(w-2)(h-2)}M$. (If one of the dimensions is $1$, the corresponding contributions with $-2$ shouldn't be included.) Thus, in total, the number of patterns that fill the entire bounding box is

$$ \binom{wh}M-2\binom{w(h-1)}M-2\binom{(w-1)h}M+4\binom{(w-1)(h-1)}M+\binom{w(h-2)}M+\binom{(w-2)h}M-2\binom{(w-1)(h-2)}M-2\binom{(w-2)(h-1)}M+\binom{(w-2)(h-2)}M\;. $$

Each of these can be translated to $(N-w+1)(N-h+1)$ different positions. We should only count one quarter of them, since the rest can be generated by rotations through multiples of $\frac\pi2$.

A pattern can only be rotated into itself through $\pi$. (For rectangular bounding boxes, this is true for general $M$, since rotating through $\frac\pi2$ would swap the dimensions of the bounding box. For square bounding boxes this is only true because $M\not\equiv0,1\bmod4$, so there's no way to have $4$-fold symmetry with $M$ molecules.)

To count the patterns that are invariant under a rotation through $\pi$ about the centre of the bounding box, form pairs of cells in the bounding box that are rotated into each other and hence must have the same fill status for the pattern to be invariant. If $w$ and $h$ are both odd, there's one cell in the middle that doesn't get paired. Since $M=10$ is even, this can't be filled in a rotationally invariant pattern. Thus, there are $\binom{\left\lfloor wh/2\right\rfloor}{M/2}$ rotationally invariant patterns. Of these we should count $\frac12$ instead of $\frac14$. But now we also have to figure out how many of these don't actually fill the entire bounding box. An inclusion–exclusion count similar to the one above (but now with only two conditions, due to the rotational symmetry) shows that there are

$$ \binom{\left\lfloor wh/2\right\rfloor}{M/2}-\binom{\left\lfloor w(h-2)/2\right\rfloor}{M/2}-\binom{\left\lfloor(w-2)h/2\right\rfloor}{M/2}+\binom{\left\lfloor (w-2)(h-2)/2\right\rfloor}{M/2} $$

rotationally invariant patterns that fill the entire bounding box.

Thus, in total we have

$$ \frac14\sum_{w=1}^N\sum_{h=1}^N\left( \binom{wh}M-2\binom{w(h-1)}M-2\binom{(w-1)h}M+4\binom{(w-1)(h-1)}M+\binom{w(h-2)}M+\binom{(w-2)h}M-2\binom{(w-1)(h-2)}M-2\binom{(w-2)(h-1)}M+\binom{(w-2)(h-2)}M+\binom{\left\lfloor wh/2\right\rfloor}{M/2}-\binom{\left\lfloor w(h-2)/2\right\rfloor}{M/2}-\binom{\left\lfloor(w-2)h/2\right\rfloor}{M/2}+\binom{\left\lfloor (w-2)(h-2)/2\right\rfloor}{M/2}\right) $$

equivalence classes of patterns under translational and rotational symmetry.

Let's check this for the case $N=2$, which we can easily count by hand. (The next case where it's applicable without adjustment, $N=6$, is already difficult to count by hand.) There's no contribution from $w=h=1$. The remaining terms yield

$$ \frac14\left(2\left(\binom22+\binom11\right)+\binom42-4\binom22+\binom21\right)=2\;, $$

in agreement with a count by hand.