2

I am aware this combinatoric problem (which I got from Discrete Mathematics Elementary and Beyond) has been answered on here before, but from what I can tell the solution I have come up with is different than the answers on other posts but I am not sure so I would like to see where my thought process is wrong.

My solution was originally:

$$3!\cdot3^{n-3}$$

My rationale was:

The first one has the option of 3 colors. Second, two, and the third, one. Each one after that can have any 3 colors since we've met our initial requirements. The below 'diagram' shows how many options each object has for colors.

-----  -----  -----  -----  -----  -----
| 3 |  | 2 |  | 1 |  | 3 |  | 3 |  | 3 |
-----  -----  -----  -----  -----  -----  ....

To me this makes sense for the answer, similarly to string combination problems. However it appears that my answer yields numbers different to the correct answer people arrive at using the Inclusion-Exclusion principal formula. Could someone explain how this is yields the wrong answer? I am assuming I am not accounting for all cases in some way.

I am seeing the following as a correct answer in the case of distinctly labeled answers

$$3^n - (2^n)\cdot{{3}\choose{2}} + 1^n\cdot{{3}\choose{1}}$$

Which for this specific problem reduces to:

$$3^n - 2^n\cdot3 + 3$$

Community
  • 1
Dominic Farolino
  • 501

2 Answers2

2

The number of ways to color $n$ objects with 3 colors is $3^n$. Now we need to subtract those colorings which did not use one of the three colors. The number of ways to color with just 2 colors is $2^n$ and since there are three colors that can be omitted we have $3^n-3\cdot 2^n$ but now we have removed all colorings with an given color twice so we need to add those back again and we get a final answer: $$3^n-3\cdot 2^n +3$$ This is an example of the inclusion-exclusion principle.

Rene Schipperus
  • 39,526
  • Ok this makes sense...How would this apply for the problem of coloring 5 objects with 4 different colors where all 4 need to be used? Would the number be $4^5-{{4}\choose{3}}\cdot3^n+{{4}\choose{2}}\cdot2^n$ – Dominic Farolino Dec 28 '15 at 04:10
1

Your solution relies on the assumption that the first three objects must be different colors, which is not the case. It becomes combinatorially cumbersome to account for all the different possibilities for which objects are differently colored, which is why the principle of inclusion/exclusion is so useful here.

kccu
  • 20,808
  • 1
  • 22
  • 41