Suppose you want to color 5 cards. The rules are:

  • there are three distinct colors;
  • each card can't be colored with more than one color;
  • each card is colored;
  • the three given colors must be used in each coloring.

How many distinct coloring is there?

Failed attempt: In each configuration we must use the three given colors, so we could start painting three cards using those colors and then complete the rest. There are $5!/2!=60$ ways to color three out of five cards with the given colors. The remaining $2$ cards could be colored in any way you like, so for each configuration of three cards which were already colored, we have $3\cdot 3=9$ options. So the total ways to color the cards would be $60\cdot 9=540$.

I know this is wrong for I'm counting some repetitions and I don't know how to get rid of them.

  • $\begingroup$ There are two cases: two cards of each of two colors, and one of the third, or three cards of one color and one of each of the other two colors. $\endgroup$ – saulspatz Aug 1 at 17:21
  • $\begingroup$ Thanks, I'll give it a try! $\endgroup$ – PtF Aug 1 at 17:31

If we ignore the last rule, there are $3^5$ colourings using red, green, and blue. From this we have to subtract $2^5$ colourings using only red and green, $2^5$ colourings using only red and blue, and $2^5$ colourings using only green and blue. But wait, we subtracted the all-red colouring twice! As well as the all-green and the all-blue colouring. So the final result is $$ 3^5-3\cdot 2^5+3.$$


Imagine a tree in a mathematical or graph theoretical sense. Each node/vertex has three branches/edges, that represent the three possible colors and that lead to new three nodes at the next tree level. There are five tree levels, that represent the five cards. At the first level we have $3$ nodes. These are the possibilities to color the first card with one of the three colors. At the second level we have $3^2$ nodes, if from each node at the first level three new edges lead to three new nodes, or possibilities to color two cards with three colors. At the fifth level we have $\color{red}{3^5}$ possibilities or the total number of nodes at the last or fifth tree level. The number oft tree routes that lead from the tree root to a node at the fifth level is also $\color{red}{3^5}$. Take a tree route consisting of the tree root node, five edges and five nodes. Put the five nodes in a row, they represent the five cards. We need to drop out the possibilities for not using all the three colors in coloring the five cards. These are the possibilities, that use one or two colors. First drop out the possibilities for coloring with just one color. There must be a tree route with the same color for each node among all the possible coloring combinations. Since we have three colors, there are $\color{orange}{3}$ coloring possibilities out of the total $\color{red}{3^5}$ coloring possibilities, that have the same color for each node and we need to drop them out due to the coloring rules. Also we need to drop out all other coloring possibilities, that only contain two colors. These are $\color{magenta}{\binom{3}{2}}\cdot \color{green}{2^5}=\color{magenta}{3}\cdot \color{green}{2^5}$, because there are three possibilities to pick two colors out of the three given colors and because we color five cards with two colors. In counting the possibilities for coloring five cards with two colors, there are also $\color{blue}{2}$ possibilities of having a route with the same one color for each of the $\color{magenta}{3}$ possibilities. We have already subtracted three for having a route with the same color. For each of the three possibilities of coloring the five cards with two colors, we need to add back the two possibilities of having a route with the same color out of two colors, because we already have subtracted all the possibilities when every card/node has one color, we have already subtracted $\color{orange}3$ and we do not need to subtract these possibilities again, but we do and therefore we need to add back $\color{blue}{2}$ three times.

In total, we have

$$\color{red}{3^5}+\color{magenta}{3}\cdot(- \color{green}{2^5}+ \color{blue}{2})-\color{orange}{3} = 150$$



How much overcounting have we done? Any situation in which three cards share one color has been counted thrice -- once with each of the three in the first group of three. Any situation in which there are two same-color groups of two cards each has been counted four times -- once for each choice of one card from each group.

If you can count how many ways the former situation can arise (call it $m$) and the number of ways the latter situation can arise (call it $n$), you can take your answer and subtract $2m+3n$ to correct for overcounting.

Of course, $m+n$ should also give the answer directly -- and you can check whether you get the same answer.


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.