• Support PF! Buy your school textbooks, materials and every day products Here!

Another counting problem

  • Thread starter Townsend
  • Start date
  • #1
221
0
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
 

Answers and Replies

  • #2
learningphysics
Homework Helper
4,099
5
Townsend said:
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.
 
  • #3
Almost.

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

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

This means that the number of subsets of length [Tex]<= n[/Tex] will be exactly half the total number of subsets: [Tex]\frac{2^{n}}{2}=4^n[/Tex]
 
  • #4
AKG
Science Advisor
Homework Helper
2,565
4
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:

[tex]S_n = \sum _{i = 0} ^n {{2n + 1}\choose i}[/tex]

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

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

We want to prove that:

[tex]S_{k+1} = 4^{k+1}[/tex]

Well, we can do it:

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

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

[tex]S_{k + 1} = 1 + \sum _{i = 1} ^{k + 1} {{2k + 3}\choose i}[/tex]

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

[tex]S_{k + 1} = 1 + 1 + {{2k + 2}\choose {k+1}} + 2\sum _{i = 1} ^{k} {{2k + 2}\choose i}[/tex]

[tex]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 )[/tex]

[tex]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 )[/tex]

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

[tex]S_{k + 1} = {{2k + 1}\choose {k+1}} -{{2k + 1}\choose k} + 4(4^k)[/tex]

[tex]S_{k + 1} = {{2k + 1}\choose {k+1}} -{{2k + 1}\choose k} + 4^{k+1}[/tex]

[tex]S_{k+1} = 4^{k+1}[/tex]

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 [itex]4^n[/itex].
 
  • #5
AKG
Science Advisor
Homework Helper
2,565
4
Bah! noelhustler's solution is much clearer and simpler.
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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!
 
  • #7
learningphysics
Homework Helper
4,099
5
AKG said:
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.
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Well, the bad news is we did his homework for him. :tongue2: At least the message was consistent, though, so maybe it will still impress upon him.
 
  • #9
221
0
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

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

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
 

Related Threads on Another counting problem

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
Replies
3
Views
8K
  • Last Post
Replies
16
Views
1K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
18
Views
1K
  • Last Post
Replies
1
Views
968
  • Last Post
Replies
3
Views
2K
Top