Number of possible patterns?

Question

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?

Answer 1

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)

Answer 2

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$.