Math Help Forum: Number of subsets

What is the number of ways to color n objects with 3 colors if every color must be used at least once?

Originally Posted by taylor1234

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.

Originally Posted by taylor1234

What is the number of ways to color n objects with 3 colors if every color must be used at least once?

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.


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.
.

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.

is number of ways to color with at most 3 colors, no restrictions

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 . (Which is in agreement with the formula given by Plato.)

Originally Posted by undefined

Hm I assumed the objects are non-identical since the thread thread title has "subsets" in it and sets typically have no duplicates.

In counting problems that may or may not be the case.
Many authors do use the term multi-set over against just set.
But that rather recent as history goes.

Hello, taylor1234!

I am assuming that the objects are indistinguishable.


I cranked out the first few cases and found a pattern.

. .


There are three-color arrangements.


~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


Hindsight is a marvelous gift!

Now I see the reason for this . . .


We have objects in a row, say,

. .


There are 6 spaces between the objects.

Select 2 of the spaces and insert "dividers".


So that: . .represents: .
. . Two of color A, one of color B, four of color C.

And: . .represents: .
. . Three of color A, three of color B, one of color C.


With objects, there are spaces.

Selecting two spaces, there are: . ways.