1
$\begingroup$

I am trying to calculate how many ways there are two colour a $4\times4$ grid with $2$ colours, where adjacent tiles are permitted to have the same colour.

Now, each square in the grid has $2$ options for colouring and there are 16 squares so I believe the answer must be $2^{16}$. However, I tried calculating in a different way (for use in a group theory problem) and I'm not getting the same answer. Here's what I did:

1. Number of ways to colour the grid such that all quadrants are different:
Each quadrant has $2^4 = 16$ colourings and, so, we have that there must be $16 \times 15 \times 14 \times 13$ ways to colour the grid this way.

2. Number of ways to colour the grid such that one pair (and only one pair) of adjacent quadrants are the same:
There are $4$ ways to choose adjacent pairs, and, once we have chosen them, we have $16 \times 15 \times 14$ ways to colour them in. So I get $4(16 \times 15 \times 14)$

3. Number of ways to colour the grid such that two pairs of adjacent quadrants are the same:
There are $4$ ways to choose adjacent pairs (once we choose a pair, the other two are automatically adjacent), and, once we have chosen them, we have $16 \times 15$ ways to colour them in. So I get $4(16 \times 15)$

4. Number of ways to colour the grid such that one pair (and only one pair) of diagonal quadrants are the same:
There are $2$ ways to choose diagonal pairs, and, once we have chosen them, we have $16 \times 15 \times 14$ ways to colour them in. So I get $2(16 \times 15 \times 14)$

5. Number of ways to colour the grid such that two pairs of diagonal quadrants are the same:
There are $2$ ways to choose diagonal pairs (once we choose a pair, the other two are automatically diagonal), and, once we have chosen them, we have $16 \times 15$ ways to colour them in. So I get $2(16 \times 15)$

6. Finally, there's $16$ colourings such that all four quadrants are the same.

However, adding all these up, I don't get $2^{16}$. In fact, I'm off by just $240 = 16 \times 15$. It seems that I am mis-counting either the number of ways to choose two adjacent quadrants or two diagonal quadrants ($4$ and $5$ above).

What gives? What am I missing here? Thank you for reading my long post.

$\endgroup$
1
$\begingroup$

You counted those cases in which there are two pairs of quadrants that are the same twice. Let's say you choose to color the upper left and bottom right quadrants solid blue and the bottom left and upper right quadrants solid green. You count this case twice, once when you designate the upper left and bottom right quadrants as the ones you will paint blue and the other two quadrants as the ones you will paint green and once when you designate the bottom left and upper right quadrants as the ones you will paint green and the other two as the quadrants you will paint blue.

You also failed to take into account the cases in which three quadrants are the same.

Cases:

  1. All quadrants are different: As you found, this can be done in $$16 \cdot 15 \cdot 14 \cdot 13$$ different ways.
  2. Exactly one pair of identical quadrants: We can choose the pair in $\binom{4}{2}$ ways and choose the color for those quadrants in $16$ ways. If we list the quadrants in the order upper left, upper right, bottom left, bottom right, there are $15$ ways to paint the first unpainted quadrant in a way that is different from the pair and $14$ ways to paint the remaining quadrant in a way that is different from both pairs. Therefore, there are $$\binom{4}{2} \cdot 16 \cdot 15 \cdot 14$$ such cases.
  3. Two different pairs of identical quadrants: There are three ways to choose which of the other quadrants will be painted in the same way as the upper left quadrant, $16$ ways to choose how to paint those two quadrants, and $15$ ways to choose the pattern for the other two quadrants. Hence, there are $$3 \cdot 16 \cdot 15$$ such cases.
  4. Three identical quadrants: There are $\binom{4}{3}$ ways to choose which three of the quadrants, $16$ ways to choose how to paint those three quadrants, and $15$ ways to choose how to paint the remaining quadrant. Hence, there are $$\binom{4}{3} \cdot 16 \cdot 15$$ such cases.
  5. Four identical quadrants: As you observed, there are $16$ options for painting all four quadrants in the same way.

Observe that $$16 \cdot 15 \cdot 14 \cdot 13 + \binom{4}{2} \cdot 16 \cdot 15 \cdot 14 + 3 \cdot 16 \cdot 15 + \binom{4}{3} \cdot 16 \cdot 15 + 16 = 2^{16}$$

$\endgroup$
1
$\begingroup$

Though I did not added and calculated it all, here are dew flaws that I saw:-

First of all 240 = 16*15

Second, you did not include case where 3 of them are same

$\endgroup$

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.