Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Three subsets of [n]

  1. Sep 7, 2008 #1
    The question: How many ways are there to choose three subsets, A, B, and C of [n] that satisfy A[tex]\subseteq[/tex]B[tex]\subseteq[/tex]C?

    My attempt:

    Since C is the primary subset of [n] (the set upon which A and B are built) then the maximum number of ways to choose that set is based upon both n and |C| so it would be n Choose |C|. As B is a subset of C, the number of ways to make that set would be |C| Choose |B|. The same with A, with the number of ways A can exist being |B| Choose |A|. Thus the total number of ways that these three subsets can be created is n Choose |C| + |C| Choose |B| + |B| Choose |A|.


    Am I right on this line of thinking or do I fail terribly at this subject?
     
  2. jcsd
  3. Sep 7, 2008 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi SticksandStones! :smile:

    A good answer if |A| |B| and |C| are fixed (and I'm assuming you meant to type x not + :wink:) …

    but if they can be anything ≤ n, then they're all unknowns, so how can you calculate them? :confused:

    So … a good line of thinking … but not for this question!

    Try again! :smile:
     
  4. Sep 7, 2008 #3
    Hi,
    Through some brute force I have found that:
    Number of possibilities for C = Sum from k=1 to n of n Choose k
    Number of possibilities for B = Sum from a = 1 to n of the Sum from k=1 to a of n Choose a times a Choose k.

    But, I still can't figure out then what the number of possibilities for A would be. Following the same line of think that I was using to find C and B, for n = 3 I found that the number of possibilities would be 12 * 1 Choose 1 + 6 * 2 Choose 1 + 6 * 2 Choose 2 + 3 Choose 1 + 3 Choose 2 + 3 Choose 3. I must be missing something really simple because this looks like it should collapse nicely but I can't think of anyway to make it more generic to fit any number n.
     
  5. Sep 7, 2008 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    recurrence relation?

    hmm … :rolleyes:

    how about a recurrence relation (a sort-of proof by induction) …

    if you know Pn, then what is Pn+1? :smile:
     
  6. Sep 7, 2008 #5
    Re: recurrence relation?

    I'm not entirely sure what you mean by this. Can you re-word it?
     
  7. Sep 7, 2008 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Re: recurrence relation?

    Yup … suppose you know the answer for n = 7 is 4661.

    Now count all the ways for n = 8.

    If you start with |C| = 8 (so C = the whole of [8]), then you have a relatively easy problem.

    And for all the other cases, you can use the 4661 figure to hlep you.

    With luck, that wiil be easy enough to give you a general technique for getting not just from P7 = 4661 to P8, but from any Pn to Pn+1.

    And then you just use that equation over and over again to get from P1 to any Pn. :smile:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook