- #1
SticksandStones
- 88
- 0
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?
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?