How Many Subsets of a Set with Odd Elements Can Have Half or Fewer Elements?

[Townsend]

The question is...

How many subsets of a (2n+1)-element set have n elements or less?

To figure this out I started by using a workable example. Obviously n must be small to keep the total number of subsets small. So I started with n=1 and so there are 8 total subsets. And of course in general there will be 2^(2n+1) subsets. Writing these subsets out in order from smallest to largest seems to reveal a pattern. There is 1 empty set, 2n+1 one element sets and 2n 2 element sets all the way up to 1 2n+1 element set. So there must be 2n+1-n element sets with n elements or less plus the empty set to give me n+2. Does this sound correct?

Thanks

 

[learningphysics]

The question is...

How many subsets of a (2n+1)-element set have n elements or less?

To figure this out I started by using a workable example. Obviously n must be small to keep the total number of subsets small. So I started with n=1 and so there are 8 total subsets. And of course in general there will be 2^(2n+1) subsets. Writing these subsets out in order from smallest to largest seems to reveal a pattern. There is 1 empty set, 2n+1 one element sets and 2n 2 element sets all the way up to 1 2n+1 element set. So there must be 2n+1-n element sets with n elements or less plus the empty set to give me n+2. Does this sound correct?

Thanks

How did you get that there are 2n 2 element sets?

I believe your answer is wrong. Suppose n>1... How many 1 element sets are there... 2n+1... So the number of sets with n or less elements is at least 2n+1... which is greater than n+2.

 

[noelhustler]

Almost.

There are 2^{2n+1} subsets in total.
The number of subsets with k elements is actually \binom{2n+1}{k}.

Now, because we want the number of subsets of length <= n we can use the fact that the binomial expansion is symmetrical (about n and n+1 since 2n+1 is always odd.

This means that the number of subsets of length <= n will be exactly half the total number of subsets: \frac{2^{n}}{2}=4^n

 

[AKG]

How many ways can you make a set of i elements choosing from a set of 2n+1 elements? What values of i are "of interest" for this problem?

You want to find a closed form solution for:

S_n = \sum _{i = 0} ^n {{2n + 1}\choose i}

For n = 0, we can show that S_0 = 4^0 = 1. You can easily compute it for the first few values of n. Now, assume that for n = k, it is true that:

S_n = S_k = \sum _{i = 0} ^k {{2k + 1}\choose i} = 4^k

We want to prove that:

S_{k+1} = 4^{k+1}

Well, we can do it:

S_{k + 1} = \sum _{i = 0} ^{k + 1} {{2(k+1) + 1}\choose i}

S_{k + 1} = \sum _{i = 0} ^{k + 1} {{2k + 3}\choose i}

S_{k + 1} = 1 + \sum _{i = 1} ^{k + 1} {{2k + 3}\choose i}

S_{k + 1} = 1 + \sum _{i = 1} ^{k + 1} \left ({{2k + 2}\choose {i-1}} + {{2k + 2}\choose {i}}\right )

S_{k + 1} = 1 + 1 + {{2k + 2}\choose {k+1}} + 2\sum _{i = 1} ^{k} {{2k + 2}\choose i}

S_{k + 1} = 2 + {{2k + 1}\choose k} + {{2k + 1}\choose {k+1}} + 2\sum _{i = 1} ^{k} \left ({{2k + 1}\choose {i-1}} + {{2k+1}\choose i}\right )

S_{k + 1} = 2 + {{2k + 1}\choose k} + {{2k + 1}\choose {k+1}} + 2 + 2{{2k+1}\choose k} + 2\left (2\sum _{i = 1} ^{k-1} {{2k + 1}\choose i}\right )

S_{k + 1} = {{2k + 1}\choose {k+1}} -{{2k + 1}\choose k} + 4\sum _{i = 0} ^k {{2k + 1}\choose i}

S_{k + 1} = {{2k + 1}\choose {k+1}} -{{2k + 1}\choose k} + 4(4^k)

S_{k + 1} = {{2k + 1}\choose {k+1}} -{{2k + 1}\choose k} + 4^{k+1}

S_{k+1} = 4^{k+1}

Now, a lot of the steps above might not be clear at first. Hopefully you're familiar with Pascal's Triangle and some of the tricks that go along with it. If you're confused by any of the steps, I can explain them, although familiarity with Pascal's Triangle will help you get a nice intuitive understanding of what's going on. Otherwise, if you can't do it yourself (although I strongly suggest you do, since it's just basic algebra/arithmetic), I can prove why certain steps do indeed work. So the answer to the question would be 4^n.

 

[AKG]

Bah! noelhustler's solution is much clearer and simpler.

 

[Hurkyl]

Or, for a more elementary approach, note that you do know the number of subsets of a set of cardinality (2n+1). If you can find a relation between the number of subsets of cardinality n or less and the number of subsets of cardinality more than n, you might be able to solve!

 

[learningphysics]

Bah! noelhustler's solution is much clearer and simpler.

Well, the trick I used is that C(n,r)=C(n,n-r)

So the number of sets of elements 0,1,2,3,4...n is half the total number of sets.

 

[Hurkyl]

Well, the bad news is we did his homework for him. At least the message was consistent, though, so maybe it will still impress upon him.

 

[Townsend]

Thank you everyone for the overwhelming responses. After Learningphysics's reply I did manage to see my error and realized that I would end up using C(n,r) but that is about as far as I had taken it. This is what I had come up with on my own

\sum^n_{i=0}{\frac{(2n+1)!}{(2n+1-i)!i!}

Which I think that would be correct but not very nice to look at. I was going to attempt to simplify that creature and I still will try to. There is obviously more than one way to approach this kind of problem and I am going to look over all of them, thanks again.

Townsend