Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Sets problem
Replies: 1   Last Post: May 20, 2012 9:49 AM

 Messages: [ Previous | Next ]
 Vamph Posts: 1 Registered: 5/20/12
Sets problem
Posted: May 20, 2012 8:06 AM
 problem.png (3.1 K)

Let S be the set: {1, 2, 3, ..., k}. How many sequences of k sets S_1,S_2,S_3, ...,S_k are there such that each set is a subset (not necessarily proper) of the next one, and S_k is S?

So, I am working on that question and could not figure out an easy way to solve it.
Here is my attempt:
The idea that I have is that we start from the set S_k and do its power set P(S_k). The sets included in P(S_k) are the different possible S_k-1. Then, for each of these possibilities we do the same things (the power sets of these sets to have the possible S_k-2) until we have all the possible sets for S_1. The number of these possible sets S1 will be the answer of that question. This is actually true, and can be tried for small values of k, but I think that it is impossible to apply it for k and compute the number of sequences. I also tried to see the problem from different perspectives, but none of them is applicable for k.
I don't know if there is any way to know the total of the number of subsets of the subsets of a set. I think that it will solve the problem.

Date Subject Author
5/20/12 Vamph
5/20/12 Ben Brink