1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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


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


    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


    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:
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?