1
$\begingroup$

How many ways are there to color in each unit square of a $2\times5$ grid red or blue so that no $2\times2$ square is allowed to be the same color?

So I thought about doing an inclusion-exclusion method to approach this problem, but my main issue with this approach was that it was too hard to bash out all the cases involved with such an approach (that is, considering the cases where there exist $2\times2$ squares which are the same color). Any thoughts on a better approach I could take?

$\endgroup$
2
  • 1
    $\begingroup$ You could try to find a recurrence relation for the number of good colorings of a $2\times n$ grid. $\endgroup$
    – RobPratt
    Apr 11 '20 at 2:25
  • $\begingroup$ How would I go about trying to do this? Sorry, but I don't really see how a recurrence relation would apply here.... $\endgroup$
    – jmf203
    Apr 11 '20 at 2:26
4
$\begingroup$

Let $a_n$ denote the number of good colorings of a $2\times n$ grid. You want to compute $a_5$. The initial conditions are $a_0 = 1$ and $a_1 = 4$. To derive a recurrence relation for $a_n$, consider the four possibilities for the two cells in the leftmost column. You will find that $a_n = 3 a_{n-1} + 2 a_{n-2}$, yielding: \begin{align} a_2 &= 3 a_1 + 2 a_0 = 3\cdot4 +2\cdot 1 = 14 \\ a_3 &= 3 a_2 + 2 a_1 = 3\cdot14 +2\cdot 4 = 50 \\ a_4 &= 3 a_3 + 2 a_2 = 3\cdot50 +2\cdot 14 = 178 \\ a_5 &= 3 a_4 + 2 a_3 = 3\cdot178 +2\cdot 50 = \color{red}{634} \end{align}


Alternatively, if you just care about $n=5$, the inclusion-exclusion approach yields \begin{align} a_5 &= 2^{10} - 2(5-1)2^6 + (2(5-2)2^4 + 2^2\cdot 3\cdot 2^2) - (2(5-3)2^2 + 2^3\cdot 2^0) + 2(5-4)2^0 \\ &= 1024 - 512 + (96 + 48) - (16 + 8) + 2 \\ &= \color{red}{634} \end{align}

$\endgroup$
4
  • $\begingroup$ Thanks! Did you get the respective values of a by just testing(bashing) them out, or is there a better way that I'm not seeing? $\endgroup$
    – jmf203
    Apr 11 '20 at 3:32
  • $\begingroup$ Not sure what you mean test/bash. I used the recurrence relation. $\endgroup$
    – RobPratt
    Apr 11 '20 at 3:41
  • $\begingroup$ I agree with this answer (which is A055099), but I'm trying to understand the recurrence relation from the coloring application (which is not in the OEIS entry). If the last column is ${b \atop b}$, then it can be legally followed by ${b \atop r}$, ${r \atop b}$, or ${r \atop r}$, but not ${b \atop b}$. Similarly, ${r \atop r}$ has three legal successors. A last column ${b \atop r}$ or ${r \atop b}$ can be followed by any of the four possibilities. What's the clear way to describe three successors for any $2\times(n-1)$ grid and pick up the $2a_{n-2}$ term? $\endgroup$ Apr 11 '20 at 20:13
  • $\begingroup$ @BrianHopkins, I split $a_n$ into four sequences according to the leftmost column, came up with four linear recurrence relations, and eliminated everything but $a_n$. $\endgroup$
    – RobPratt
    Apr 11 '20 at 21:06
2
$\begingroup$

Thanks for explaining how you came to the recurrence relation $a_n = 3a_{n-1}+2a_{n-2}$, Rob. Here's a potentially more direct way.

We want to build all the allowed $2 \times n$ grids from shorter grids. For each allowed $2 \times (n-1)$ grid, suppose the rightmost column is $x \atop z$ where $x, z \in \{b,r\}$ could be the same or different. Let $y \ne x$, i.e., $y$ and $x$ are different colors. We can make an allowed $2 \times n$ grid by appending each of the three columns $x \atop y$, $y \atop x$, and $y \atop y$, which gives the $3a_{n-1}$ term in the recurrence.

What $2 \times n$ grids are missing from that construction? The ones whose last two columns have the form ${x \, x} \atop {z \,x}$ with $x \ne z$, that is, ${b \, b} \atop {r \, b}$ or ${r \, r} \atop {b \, r}$. Append each of those $2 \times 2$ blocks to each allowed $2 \times (n-2)$ grid. These complete the $2 \times n$ grids, do not overlap with the ones built from $2 \times (n-1)$ grids, and account for the $2a_{n-2}$ term in the recurrence.

$\endgroup$
1
  • $\begingroup$ Looks good. +1 from me $\endgroup$
    – RobPratt
    Apr 12 '20 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.