# Why by my method i am counting more than the given in each case of more than 3 tiles

A $$7 \times 1$$ board is completely covered by $$m \times 1$$ tiles without overlap.

Each tile may cover any number of consecutive squares, and each tile lies completely on the board.

Each tile is either red, blue, or green.

Let $$N$$ be the number of tilings of the $$7 \times 1$$ board in which all three colors are used at least once.

For example, a $$1 \times 1$$ red tile followed by a $$2 \times 1$$ green tile, a $$1 \times 1$$ green tile, a $$2 \times 1$$ blue tile, and a $$1 \times 1$$ green tile is a valid tiling.

Note that if the $$2 \times 1$$ blue tile is replaced by two $$1 \times 1$$ blue tiles, this results in a different tiling.

What i did was cases made for total number of tiles:

like for 3 tiles by doing $$x_1$$+ $$x_2$$+$$x_3$$= 7 , where $$x_1$$,$$x_2$$,$$x_3$$ represents lengths of each tile , which should some up to 7 and then multiply by 3! For 3 colours from this method for cases more than 3 tiles ,

i seems like counting wrong always, like for example for 5 tiles i did first $$x_1$$+...$$x_5$$ = 7 this tells the number of tiles combinations possible to be 6C4 , and now the tiles can be of two types (1,1,3) ,(1,2,2) , where each represents the colour combinations from three colours .

Now for first type its like choosing 1 , then another 1 ,then 3 so its this: 5C1 * 4C1 * 3C3 and then 3! Mulitpilcation For three colours , similairy next type it would be 5C1 * 4C2 * 2C2 * 3! .

But ik i am making some couting mistake like i need to do some number division or multiplicatiom here which leads to correct answer for every case. Can anyone tell whats wrong in this case of 5 tiles ?

• To get subscripts, use an underscore. $x_1$ gives $x_1$. – saulspatz Mar 18 at 13:32
• Yeah i have done the editing Sir – user900638 Mar 18 at 13:38

You've over-counted by a factor of $$2$$ at the end. You shouldn't be multiplying by $$3!$$ but by $$3$$. When you assign colors in the pattern $$(1,1,3)$$, for example, you only need to decide which color occurs $$3$$ times; after that there's no choice. In the pattern $$(2,2,1)$$, you only need to decide which color occurs once.
Another way to do this part of the problem is inclusion-exclusion. There are $$3^5$$ ways to color $$5$$ tiles with $$3$$ colors. We must subtract the ways that only use $$2$$ colors, so we have $$3^5-3\cdot2^5$$. Now what about a coloring with one color? It's been counted once originally, and subtracted twice, since one of the two-colorings doesn't include it, so we need to add it back in. This gives a final answer of $$3^5-2\cdot2^5+3=150$$ Note that this is the same as $$\binom51\binom41\cdot3+\binom51\binom42\cdot3=150$$
• Yes, those colorings are different, but you've taken care of that in the first part of the calculation. Suppose we have $1$ red, $1$ blue, $3$ green. When you calculate $\binom51\binom41\binom33$, you're saying, "Choose a tile to color red, then a tile to color blue, then color the others green." We don't want to also say, "Choose a tile to color blue, then a tile to color red, etc." Personally, I find inclusion-exclusion much less error-prone for problems like this. – saulspatz Mar 18 at 14:46
• Yes, that's right. I can't be very specific about when I like PIE, but I guess it's in problems like this where we have multiple stages of counting, and it's easy to make mistakes in how they interrelate. When I find myself getting confused, I try to fall back on PIE. In this case, I immediately thought you were overcounting by a factor of $2$, but I wasn't really sure till I confirmed it with PIE. Full disclosure: even then, I checked it again with a python script that constructed all colorings of five tiles. – saulspatz Mar 18 at 15:03