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?
6
- $\begingroup$ Please share your thoughts so far :) $\endgroup$Shaun– Shaun ♦2014-07-27 20:59:58 +00:00Commented Jul 27, 2014 at 20:59
- $\begingroup$ 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... $\endgroup$Casio-warrior– Casio-warrior2014-07-27 21:06:25 +00:00Commented Jul 27, 2014 at 21:06
- $\begingroup$ 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. $\endgroup$user65203– user652032014-07-27 21:08:14 +00:00Commented Jul 27, 2014 at 21:08
- $\begingroup$ Seems like a natural setting for inclusion-exclusion... $\endgroup$Gina– Gina2014-07-27 21:13:24 +00:00Commented Jul 27, 2014 at 21:13
- $\begingroup$ 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. $\endgroup$Casio-warrior– Casio-warrior2014-07-27 21:17:42 +00:00Commented Jul 27, 2014 at 21:17
| Show 1 more comment
2 Answers
$\begingroup$ $\endgroup$
13 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$.
- $\begingroup$ Confirmed by exhaustive search! $\endgroup$user65203– user652032014-07-27 21:31:35 +00:00Commented Jul 27, 2014 at 21:31
- $\begingroup$ How did you do the exhaustive search ? $\endgroup$Casio-warrior– Casio-warrior2014-07-27 21:32:44 +00:00Commented Jul 27, 2014 at 21:32
- $\begingroup$ 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 $\endgroup$user65203– user652032014-07-27 21:36:20 +00:00Commented Jul 27, 2014 at 21:36
- $\begingroup$ @YvesDaoust: I have no clues how that code work.... :( $\endgroup$Gina– Gina2014-07-27 21:37:49 +00:00Commented Jul 27, 2014 at 21:37
- $\begingroup$ @Gina The good news is that two independent methods converge :) $\endgroup$user65203– user652032014-07-27 21:41:39 +00:00Commented Jul 27, 2014 at 21:41
$\begingroup$ $\endgroup$
4 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) - $\begingroup$ what version of Python are you running this on? I tried on 3.4.1, and it didn't give me anything... $\endgroup$Casio-warrior– Casio-warrior2014-07-28 14:10:17 +00:00Commented Jul 28, 2014 at 14:10
- $\begingroup$ 2.6.6, add parenthesis to the print. $\endgroup$user65203– user652032014-07-28 14:22:18 +00:00Commented Jul 28, 2014 at 14:22
- $\begingroup$ what would the possible grid points look like in a 3x3? $\endgroup$Casio-warrior– Casio-warrior2014-07-28 14:57:47 +00:00Commented Jul 28, 2014 at 14:57
- $\begingroup$ My comments should make it obvious. Drop the constants having a 8 and test equality with 0x77. $\endgroup$user65203– user652032014-07-28 18:23:23 +00:00Commented Jul 28, 2014 at 18:23