April | 2018 | Chaitanya's Random Pages

April 1, 2018

A collection of binary grid counting problems

Filed under: mathematics — ckrao @ 3:52 am

The number of ways of colouring an m by n grid one of two colours without restriction is $2^{mn}$ . The following examples show what happens when varying restrictions are placed on the colouring.

Example 1: The number of ways of colouring an m by n grid black or white so that there is an even number of 1s in each row and column is

$\displaystyle 2^{(m-1)(n-1)}.$

Proof: The first $m-1$ rows and $n-1$ columns may be coloured arbitarily. This then uniquely determines how the bottom row and rightmost column are coloured (restoring even parity). The bottom right square will be black if and only if the number of black squares in the remainder of the grid is odd, hence this is also uniquely determined by the first $m-1$ rows and $n-1$ columns. Details are also given here.

Example 2: The number of ways of colouring an m by n grid black or white so that every 2 by 2 square has an odd number (1 or 3) of black squares is

$\displaystyle 2^{m+n-1}.$

Proof: First colour the first row and first column arbitarily (there are $m+n-1$ such squares each with 2 possibilities). This uniquely determines how the rest of the grid must be coloured by considering the colouring of adjacent squares above and to the left.

By the same argument, the above is the same as the number of colouring an m by n grid black or white so that every 2 by 2 square has an even number (0, 2 or 4) of black squares.

Example 3: The number of ways of colouring an m by n grid black or white so that every 2 by 2 square has two of each type is

$\displaystyle 2^m + 2^n - 2.$

Proof: If there are two adjacent squares of the same colour with one above the other, the remaining squares of the corresponding two rows are uniquely determined as being the same alternating between black and white. The remainder of the grid is then determined by the colouring of first column ( $2^m - 2$ possibilities where we omit the two cases of alternating colours down the first column). Such a grid cannot have two horizontally adjacent squares of the same colour. By a similar argument a colouring that has two adjacent colours with one left of the other can be done in $2^n-2$ ways. Finally we have the two additional configurations where there are no adjacent squares of the same colour, which is uniquely determined by the colour of the top left square. Hence in total we have $(2^m-2) + (2^n-2) + 2 = 2^m + 2^n - 2$ possible colourings.

This question for $m = n = 8$ was in the 2017 Australian Mathematics Competition and the general solution is also discussed here.

Example 4: The number of ways of colouring an m by n grid black or white so that each row and each column contain at least one black square is (OEIS A183109)

$\displaystyle \sum_{j=0}^m (-1)^j \binom{m}{j} (2^{m-j}-1)^n.$

Proof: First we count the number of colourings where a fixed subset of $j$ columns is entirely white and each row has at least one black square. The remaining $m-j$ columns and $n$ rows can be coloured in $(2^{m-j}-1)^n$ ways. To count colourings where each column has at least one black square we apply the principle of inclusion-exclusion and arrive at the above result.

Another inclusion-exclusion example shown here counts the number of 3 by 3 black/white grids in which there is no 2 by 2 black square. The answer is 417 with more terms for n by n grids in OEIS A139810.

Example 5: Suppose we wish to count the number of colourings of an m by n grid in which row i has $k_i$ black squares and column j has $l_j$ black squares ( $i = 1, 2, \ldots m$ , $j = 1, 2, \ldots, n$ ). Following [1], the number of ways this can be done is the coefficient of $x_1^{k_1}x_2^{k_2} \ldots x_m^{k_m}y_1^{l_1}y_2^{l_2}\ldots y_n^{l_n}$ in the polynomial

$\displaystyle \prod_{i=1}^m \prod_{j=1}^n (1 + x_i y_j).$

To see this note that expanding the product gives products of terms of the form $(x_i y_j)$ where such a term included corresponds to the $i$ ‘th row and $j$ th column being coloured black. Hence the coefficient of $x_1^{k_1}x_2^{k_2} \ldots x_m^{k_m}y_1^{l_1}y_2^{l_2}\ldots y_n^{l_n}$ is the number of ways in which the system $\sum_{j=1}^n a_{ij} = k_i, \sum_{i=1}^m a_{ij} = l_j$ has a solution ( $i = 1, 2, \ldots m$ , $j = 1, 2, \ldots, n$ ) for $a_{ij}$ equal to 1 if and only if row $i$ and column $j$ are coloured black and 0 otherwise.

Let us evaluate this in the special case of 2 black squares in every row and every column for an n by n square grid (i.e. $k_i = l_j = 2$ and $m = n$ ). Picking two squares in each column to colour black means viewing the expansion as a polynomial in $y_1, \ldots, y_n$ the coefficient of $y_1^2y_2^2\ldots y_n^2$ has sums of products of $n$ terms of the form $x_ix_j$ . Then using $[]$ notation to denote the coefficient of an expression, we have

$\begin{aligned} \left[x_1^2x_2^2 \ldots x_n^2y_1^2y_2^2\ldots y_n^2 \right] \prod_{i=1}^n \prod_{j=1}^n (1 + x_i y_j) &= \left[x_1^2x_2^2 \ldots x_n^2 \right] \left( \sum_{i=1}^n\sum_{j=i+1}^n x_i x_j \right)^n\\&= \left[x_1^2x_2^2 \ldots x_n^2 \right] 2^{-n} \left( \left( \sum_{i=1}^n x_i\right)^2 - \sum_{i=1}^n x_i^2 \right)^n\\ &= \left[x_1^2x_2^2 \ldots x_n^2 \right] 2^{-n} \sum_{k=0}^n (-1)^k \binom{n}{k} \left( \sum_{i=1}^n x_i^2 \right)^k\left(\sum_{i=1}^n x_i\right)^{2(n-k)}\\ &= 2^{-n} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{n!}{(n-k)!} \frac{(2n-2k)!}{2^{n-k}}\\ &= 4^{-n} \sum_{k=0}^n (-1)^k \binom{n}{k}^2 2^k (2n-2k)!. \end{aligned}$

Here the second last line follows from considering the number of ways that products of $k$ terms of the form $x_i^2$ arise in the product $\left( \sum_{i=1}^n x_i^2 \right)^k$ (which is $\frac{n!}{(n-k)!}$ ) and products of $(n-k)$ terms of the form $x_i^2$ can be formed in the product $\left(\sum_{i=1}^n x_i\right)^{2(n-k)}$ (which is $\frac{(2n-2k)!}{2^{n-k}}$ ).

For example, when $n=4$ this is equivalent to finding the coefficient of $a^2b^2c^2d^2$ in $(ab + bc + ac + bc + bd + cd)^4$ . Products are either paired up in complementary ways such as in $ab.ab.cd.cd$ ( $3 \times \binom{4}{2} = 18$ ways) or we have the three products $ab.bc.cd.ad, ab.bd.cd.ad, ac.bc.bd.ad$ ( $3 \times 4! = 72$ ways). This gives us a total of 90 (this question appeared in the 1992 Australian Mathematics Competition). More terms of the sequence are found in OEIS A001499 and the 6 by 4 case (colouring two shaded squares in each row and three in each column in 1860 ways) appeared in the 2007 AIME I (see Solution 7 here).

Example 6: If we wish to count the number of grid configurations in which reflections or rotations are considered equivalent, we may make use of Burnside’s lemma that the number of orbits of a group is the average number of points fixed by an element of the group. For example, to find the number of configurations of 2 by 2 grids up to rotational symmetry, we consider the cyclic group $C_4$ . For quarter turns there are $2^4$ configurations fixed (a quadrant determines the colouring of the remainder of the grid) while for half turns there are $2^8$ configurations as one half determines the colouring of the other half. This gives us an answer of

$\displaystyle \frac{2^{16} + 2.2^4 + 2^8}{4} = 16456,$

which is part of OEIS A047937. If reflections are also considered equivalent we need to consider the dihedral group $D_4$ and we arrive at the sequence in OEIS A054247.

If we want to count the number of 3 by 3 grids with four black squares up to equivalence, this is equivalent to the number of full noughts and crosses configurations. A nice video by James Grime explaining this is here (the answer is 23).

Example 7: The number of ways of colouring an m by n grid black or white so that the regions form 2 by 1 dominoes has the amazing form

$\displaystyle 2^{mn/2} \prod_{j=1}^{\lceil m/2 \rceil} \prod_{k=1}^{\lceil n/2 \rceil} \left(4 \cos^2 \frac{\pi j}{m+1} + 4 \cos^2 \frac{\pi k}{n+1}\right).$

For example, the 36 ways of tiling a 4 by 4 grid are given here. A proof of the above formula using the Pfaffian of the adjacency matrix of the corresponding grid graph is given in chapter 10 of [2].

References

[1] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions (pp 235-6), D. Reidel Publishing Company, 1974.

[2] M. Aigner, A Course in Enumeration, Springer, 2007.

Chaitanya's Random Pages

April 1, 2018

A collection of binary grid counting problems

References

Share this: