# Number of possible patterns?

Using the following rule: Each column and each row must contain at least one point, how many patterns can a 4x4 grid (thus with 16 possible point positions) generate? (this rule would thus make the answer different than the traditional one given by combinations) More specifically, how many patterns can be made with 8 points on this 4x4 grid?

• Please share your thoughts so far :) – Shaun Jul 27 '14 at 20:59
• well, I've been working on this for a while... It's a simple set up, but that can become quite complicated, quickly. I'm predicting that the total sum of all the patterns for a 4x4 gris is something in the range of 2^15 - 1... – Casio-warrior Jul 27 '14 at 21:06
• If you place the first four points in a way that satisfies the constraints, there are 4.3.2.1 patterns. And you can freely place the 4 remaining points in 12 empty squares. So (4.3.2.1).(12.11.10.9)/(4.3.2.1). Unfortunately, while doing so, some configurations do repeat. – Yves Daoust Jul 27 '14 at 21:08
• Seems like a natural setting for inclusion-exclusion... – Gina Jul 27 '14 at 21:13
• I like that way of thinking about the initial four that complete the constraints, the problem is indeed double counting configurations... Then again, considering that without these constraints there would be 16C8=12870, the number given by 4!.12C4 seems oddly big. – Casio-warrior Jul 27 '14 at 21:17

This Python script performs exhaustive enumeration

import itertools

# Possible grid points, (column, row) bits
p= [0x11, 0x12, 0x14, 0x18, 0x21, 0x22, 0x24, 0x28, 0x41, 0x42, 0x44, 0x48, 0x81, 0x82, 0x84, 0x88]

# Try for all numbers of points
for n in range(1, 17):
# Solutions counter
s= 0

# Try all combinations of n points
for c in itertools.combinations(p, n):
# Bitwise OR to detect empty rows/columns
m= 0
for e in c:
m|= e
if m == 0xFF:
# Accept this configuration
s+= 1
print n, "point(s),", s, "pattern(s)"


giving

1 point(s), 0 pattern(s)
2 point(s), 0 pattern(s)
3 point(s), 0 pattern(s)
4 point(s), 24 pattern(s)
5 point(s), 432 pattern(s)
6 point(s), 2248 pattern(s)
7 point(s), 5776 pattern(s)
8 point(s), 9066 pattern(s)
9 point(s), 9696 pattern(s)
10 point(s), 7480 pattern(s)
11 point(s), 4272 pattern(s)
12 point(s), 1812 pattern(s)
13 point(s), 560 pattern(s)
14 point(s), 120 pattern(s)
15 point(s), 16 pattern(s)
16 point(s), 1 pattern(s)

• what version of Python are you running this on? I tried on 3.4.1, and it didn't give me anything... – Casio-warrior Jul 28 '14 at 14:10
• 2.6.6, add parenthesis to the print. – Yves Daoust Jul 28 '14 at 14:22
• what would the possible grid points look like in a 3x3? – Casio-warrior Jul 28 '14 at 14:57
• My comments should make it obvious. Drop the constants having a 8 and test equality with 0x77. – Yves Daoust Jul 28 '14 at 18:23

There are no positions such that the total number of row and column that does not contains any point is at least $3$ (we will say that those row and column are "avoided").

Number of position that avoid at least $1$ row or column is $8\times\begin{pmatrix}12\\8\end{pmatrix}$. This is because there are $8$ choice of which column or row to avoid, and once that is chosen, there are $12$ position left to put $8$ points.

Intersection of a set of position that avoid a particular row or column and another of such set is always a set of position that avoid at least 2 row and column.

Number of position that avoid at least $2$ row and column is $2\times\begin{pmatrix}4\\2\end{pmatrix}\begin{pmatrix}8\\8\end{pmatrix}+4\times 4\times\begin{pmatrix}9\\8\end{pmatrix}$. The first term is for when we avoid 2 row or avoid both column. Since the situation is the same for the case of both row and the case of both column, there is a factor of 2, and we only need to consider the case of both row: in that case, we have 2 among the 4 rows we can choose to avoid, which leave us with $8$ position left to put $8$ points. The second term is for when we pick 1 row and 1 column to avoid, then there are 4 choice of column and 4 choice of row, and after that is picked, we are left with $9$ position to put $8$ points.

Now use inclusion-exclusion to get number of position that avoid at least 1 row or column to be $8\times\begin{pmatrix}12\\8\end{pmatrix}-2\times\begin{pmatrix}4\\2\end{pmatrix}\begin{pmatrix}8\\8\end{pmatrix}-4\times 4\times\begin{pmatrix}9\\8\end{pmatrix}$.

Number of position ignoring the restriction is $\begin{pmatrix}16\\8\end{pmatrix}$.

Hence total number of allowed position is $\begin{pmatrix}16\\8\end{pmatrix}-8\times\begin{pmatrix}12\\8\end{pmatrix}+2\times\begin{pmatrix}4\\2\end{pmatrix}\begin{pmatrix}8\\8\end{pmatrix}+4\times 4\times\begin{pmatrix}9\\8\end{pmatrix}=\frac{16!}{8!8!}-\frac{12!}{4!7!}+12+144=9066$.

• Confirmed by exhaustive search! – Yves Daoust Jul 27 '14 at 21:31
• How did you do the exhaustive search ? – Casio-warrior Jul 27 '14 at 21:32
• Python script (sorry can't format): g= [17, 33, 65, 129, 18, 34, 66, 130, 20, 36, 68, 132, 24, 40, 72, 136] m= 255 n= 0 for i in itertools.combinations(g, 8): c= i[0] | i[1] | i[2] | i[3] | i[4] | i[5] | i[6] | i[7] if c == m: n+= 1 print n; trying all 16C8 combinations and discarding those that do not fulfill the constrains. Every point is encoded with two bits, one among four for row, one among four for column – Yves Daoust Jul 27 '14 at 21:36
• @YvesDaoust: I have no clues how that code work.... :( – Gina Jul 27 '14 at 21:37
• @Gina The good news is that two independent methods converge :) – Yves Daoust Jul 27 '14 at 21:41