Results 1 to 6 of 6

Math Help - Number of subsets

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    10

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by taylor1234 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by taylor1234 View Post
    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.
     \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 \text{Surj}(n,3)= \sum\limits_{k = 0}^3 {(-1)^k\binom{3}{k}(3-k)^n } .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.

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

    \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 3^n-3\cdot2^n+3. (Which is in agreement with the formula given by Plato.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by undefined View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,711
    Thanks
    630
    Hello, taylor1234!

    \text{What is the number of ways to color }n\text{ objects with 3 colors}
    \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.

    . . \begin{array}{|c||c|} \hline<br />
n & \text{3 colors} \\ \hline<br />
3 & 1 \\<br />
 4 & 3\\<br />
 5 & 6\\<br />
 6 & 10\\<br />
\vdots & \vdots \\ \hline \end{array}


    There are \dfrac{(n-2)(n-1)}{2} three-color arrangements.


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


    Hindsight is a marvelous gift!

    Now I see the reason for this . . .


    We have \,n objects in a row, say, n=7

    . . \circ\;\_\;\circ\;\_\;\circ\;\_\;\circ\;\_\; \circ\;\_\;\circ \;\_\;\circ


    There are 6 spaces between the objects.

    Select 2 of the spaces and insert "dividers".


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

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


    With \,n objects, there are (n-1) spaces.

    Selecting two spaces, there are: . \displaystyle {n-1\choose2} \:=\:\frac{(n-1)(n-2)}{2} ways.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets (2)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 18th 2011, 12:17 PM
  2. [SOLVED] R has an uncountable number of distinct subsets.
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: May 4th 2011, 03:31 PM
  3. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 10:33 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 12:48 AM
  5. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 07:54 PM

Search Tags


/mathhelpforum @mathhelpforum