Finding Combinatorial Solutions for 3 Subsets of [n]

[SticksandStones]

The question: How many ways are there to choose three subsets, A, B, and C of [n] that satisfy A$$\subseteq$$B$$\subseteq$$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?

 

[tiny-tim]

The question: How many ways are there to choose three subsets, A, B, and C of [n] that satisfy A$$\subseteq$$B$$\subseteq$$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?

Hi SticksandStones!

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

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

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

Try again!

 

[SticksandStones]

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.

 

[tiny-tim]

recurrence relation?

hmm …

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

if you know P_n, then what is P_n+1?

 

[SticksandStones]

hmm …

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

if you know P_n, then what is P_n+1?

I'm not entirely sure what you mean by this. Can you re-word it?

 

[tiny-tim]

I'm not entirely sure what you mean by this. Can you re-word it?

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 P₇ = 4661 to P₈, but from any P_n to P_n+1.

And then you just use that equation over and over again to get from P₁ to any P_n.