Date: May 20, 2012 8:06 AM
Author: Vamph
Subject: Sets problem

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.