This tiling problem may not be what you expect

Let $x_{i}$ denote the number of times that the color ${i}$ appears in the set of 12 tiles where $i$ is between $1$ and $6$ .

First, we will look for the total number of possibilities. We can easily observe that the total number of possibilities is the number of solutions of the equation: $\sum_{i=1}^6$ $x_{i}$ $=12$ and $x_{i}$ is between $0$ and $12$ . It turns out that the number of solutions that satisfy this eqution is: $\binom{17}{12}$ .

In case you are wondering where I got the $17$ choose $12$ from, It comes from the generalized form $\sum_{i=1}^n$ $x_{i}$ $=m$ having $\binom{n+m-1}{n}$ solutions. (You can prove this claim using strong induction on $m$ ).

Now since we want at most $3$ colors to show up, we can divide it to three cases where exactly $1$ , $2$ , then $3$ .

Case 1 : Exactly $1$ color appears. This obviously happens in $\boxed{6}$ ways.

Case 2 : Exactly $2$ colors appear. This is equivalent to $x_{i}+x_{j}=12$ . The number of solutions is $\binom{13}{2}$ . However this number includes the case where one of the colors is $0$ and the other is $12$ , which means that we are double counting some solutions in case 1. So the number of solutions for only 1 pair is $\binom{13}{12}-2$ and because we have 15 possible pairs, the total number of ways in which EXACTLY 2 colors show up is $15\binom{13}{12}-30$ $=$ $\boxed{165}$

Case 3 : Exactly 3 colors. Just like how we did for case 2, we look for the number f solutions of the equation $\sum_{i=1}^3$ $x_{i}$ $=12$ , which is $binom{14}{3}$ . Once again we do not want any $x_{i}'s$ to equal zero because that would double count the previous cases. Here I will do something something

First we note that the probability depends largely on the first three tiles. I will split the problem into 3:

1) The first three tiles are different colors

2) Two of the first three are the same color and

3) All three of the first are the same color.

For the first case, note that tiles 4 – 12 all must be colored with just the colors that showed up on the first 3 tiles. Since there are 6 possibilities, each tile has a 50% chance of being the correct color. So tiles 4 – 12 bring in a factor of $(\frac 12)^9$ . The probability that the first 3 tiles have distinct colorings is $1 * \frac56 * \frac46 = \frac59$ . So the probability for case 1 is $\frac59 *(\frac 12)^9$ .

For the second case, it is more complicated. The probability that the first 3 tiles have 2 distinct colorings is $\frac{5}{12}$ . Now I will define $P(2, n)$ as the probability that a set of tiles end up with no more than 3 colors on them. The parameter 2 indicates that we have found a total of 2 distinct colors in the tiles that we have examined, and the parameter n indicates the number of tiles we have left to examine. For case 2), we are after $P(2, 9)$ .

It turns out that $P(2, n)$ can best be defined iteratively. If we have n tiles left to examine, we know that $\frac 23$ of the time the tile will be a different color than the original two colors, and that $\frac 13$ of the time it will be the same. If it is different, then all three colors have been determined, and each of the later tiles must be one of those 3 colors. Like in part 1), this introduces a factor of $(\frac 12)^{n-1}$ . But the one third of the time that the tile happens to be the same color as one the two already defined colors, we are left with $n-1$ spots to check and still the same two colors, which we recognize as $P(2,n-1)$ . So the iterative equation is:

$P(2,n) = \frac23 * (\frac12)^{n-1} + \frac13*P(2,n-1)$ .

Since $P(2, 1) = 1$ , we can make a table of results. We have:

$\boxed{P(2, 1) = 1}$ $\boxed{P(2, 2) = \frac{2}{3}}$ $\boxed{P(2, 3) = \frac{7}{18}}$ $\boxed{P(2, 4) = \frac{23}{108}}$ $\boxed{P(2, 5) = \frac{73}{648}}$ $\boxed{P(2, 6) = \frac{227}{3888}}$ $\boxed{P(2, 7) = \frac{697}{23328}}$ $\boxed{P(2, 8) = \frac{2123}{139968}}$ , and $\boxed{P(2, 9) = \frac{6433}{839808}}$

So we have $P(2,9)$ , but in fact, we will need all of those other $P(2,n)$ as well.

For the last case, we can again define an iterative equation for $P(1,n)$ . The parameter 1 indicates that there has only been one color on the tiles we have examined. Here is the equation:

$P(1,n) = \frac56 * P(2,n-1) + \frac16*P(1,n-1)$ .

This states the probability for the two cases that the next tile is a different color ( $\frac56$ of the time), and the probability for the case that the tile is the same color. Again, we can make a table of values, after noticing that $P(1,2)$ is 1. I will just give $P(1,9) = \frac{15763}{5038848}$ for brevity.

After summing up $\frac59 *\frac 12^9 + \frac{5}{12}* P(2, 9) + \frac{1}{36}*P(1,9)$ , we get

$\boxed{P = \frac{145063}{30233088}}$

P.S. While writing the solution, I realized that $P(1,11)$ should be equal to the total probability, since it takes all of the cases into consideration. Sure enough, $\boxed{P(1,11) = \frac{145063}{30233088}}$