Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Ben Brink Posts: 201 From: Rosenberg, TX Registered: 11/11/06
RE: Sets problem
Posted: May 20, 2012 9:49 AM
 att1.html (2.8 K)

Vamph,
Let {a1, a2, a3, ..., ak} be any permutation of {1, 2, 3, ..., k}. Then S1 = {a1}, S2 = {a1, a2}, ..., Sk = {a1, a2, ..., ak} = {1, 2, ..., k},
with the last two sets in different orders, is an example of the required sequence. Also Sk = S says that any sequence of subsets, in which each set is a subset of the next, must be of this form. Note there are k! sequences of this type.
Since the inclusions may not be proper, the problem amounts to counting the number of ways we can "add in" elements to get Sk = S, where one or more sets may equal their predecessors. For example, S1 = S2 = S3 = ... = Sk-1 = { } (the empty set) and Sk = S is one of the sequences we can count.
So the problem amounts to this: In how many ways can we combine disjoint (no elements in common) of the power set in order to get Sk = S. Suggest you start with given values of k. For example, with k = 1 there is only one sequence, namely S1 = {1}. For k = 2 we have { }, {1,2} as one sequence, {1}, {1, 2} as a second sequence and {2}, {1,2} as a third.
Good luck with an interesting problem, and thanks!
Ben

> Date: Sun, 20 May 2012 08:06:24 -0400
> From: discussions@mathforum.org
> To: discretemath@mathforum.org
> 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.

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