What is the number of ways to color n objects with 3 colors if every color must be used at least once?
Of course if n < 3 answer is 0.
I would do number of ways to color n objects with 3 colors without restriction, then subtract out those that don't use every color at least once. (Two cases: 2 colors are used, 1 color is used.)
Edit: Actually what I wrote in parentheses above is a bit misleading, you'd want to use inclusion-exclusion when counting ways with at most 2 colors (as opposed to exactly 2 colors) compared with 1 color.
This is a really vague question.
If the n objects are identical (tennis balls) then the answer is the number of ways to place n identical objects into three distinct cells with no cell empty.
$\displaystyle \displaystyle \binom{(n-3)+(3-1)}{n-3}=\binom{n-1}{n-3} $
On the other hand, if the objects being colored are themselves distinct then we count the number of surjections (onto maps) from a set of n to a set of three.
$\displaystyle \displaystyle \text{Surj}(n,3)= \sum\limits_{k = 0}^3 {(-1)^k\binom{3}{k}(3-k)^n } $.
Hm I assumed the objects are non-identical since the thread thread title has "subsets" in it and sets typically have no duplicates.
Here is my approach worked out then.
$\displaystyle 3^n$ is number of ways to color with at most 3 colors, no restrictions
$\displaystyle \binom{3}{2}\cdot2^n$ number of ways to color with at most 2 colors, but there are duplicates. Each way of coloring with exactly one color is counted twice.
So final answer would be $\displaystyle 3^n-3\cdot2^n+3$. (Which is in agreement with the formula given by Plato.)
Hello, taylor1234!
$\displaystyle \text{What is the number of ways to color }n\text{ objects with 3 colors}$
$\displaystyle \text{if every color must be used at least once?}$
I am assuming that the objects are indistinguishable.
I cranked out the first few cases and found a pattern.
. . $\displaystyle \begin{array}{|c||c|} \hline
n & \text{3 colors} \\ \hline
3 & 1 \\
4 & 3\\
5 & 6\\
6 & 10\\
\vdots & \vdots \\ \hline \end{array}$
There are $\displaystyle \dfrac{(n-2)(n-1)}{2}$ three-color arrangements.
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Hindsight is a marvelous gift!
Now I see the reason for this . . .
We have $\displaystyle \,n$ objects in a row, say, $\displaystyle n=7$
. . $\displaystyle \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;\_\; \circ\;\_\;\circ \;\_\;\circ $
There are 6 spaces between the objects.
Select 2 of the spaces and insert "dividers".
So that: .$\displaystyle \circ\:\circ\:|\:\circ\:|\:\circ\:\circ\:\circ\: \circ$ .represents: .$\displaystyle A\:A\:B\:C\:C\:C\:C$
. . Two of color A, one of color B, four of color C.
And: .$\displaystyle \circ\:\circ\:\circ\:|\: \circ\:\circ\:\circ\:|\:\circ$ .represents: .$\displaystyle A\:A\:A\:B\:B\:B\:C$
. . Three of color A, three of color B, one of color C.
With $\displaystyle \,n$ objects, there are $\displaystyle (n-1)$ spaces.
Selecting two spaces, there are: .$\displaystyle \displaystyle {n-1\choose2} \:=\:\frac{(n-1)(n-2)}{2}$ ways.