# Number of subsets with at most n elements of a set of $2n+1$ elements (updated)

A set contains $2n+1$ elements. What is the number of subsets of the set which contain at most n elements? Apart from the answer, please guide how to solve and go through this question? Please note: These subsets intersect. (update)

• do these sets intersects? – dato datuashvili Apr 6 '13 at 7:36
• Yes. The subsets intersect. – Nimit Apr 6 '13 at 7:38
• then please update question – dato datuashvili Apr 6 '13 at 7:38

Hint: There is a natural bijection between your sets and the subsets with $n+1$ or more elements, via complementation. And all together, your sets and their complements make up all subsets.

**Hint**You need subset with the property of having less than $n$ element, one basic thing to do when you are trying to count something is to decompose the given property in more rectrictive properties that you can count. It could be helpful if this more rectrictive propreties implied that the element they define are mutually exclusive.

Here you could start by says ok if I could count the elements with exactly $0$ elements exaclty $1$ element and so on you would be done. But this is easily arranged. \begin{align} \sum _{k=0}^{n} {2n+1 \choose k}&=\sum _{k=0}^{n} {2n+1 \choose 2n+1-k} \\ \end{align} $$\sum _{k=0}^{n} {2n+1 \choose k}+\sum _{k=0}^{n} {2n+1 \choose 2n+1-k}=(1+1)^{2n+1}=2^{2n+1}$$

Question is similar to this.

Hint:

You have $2^{2n+1}$ in total, you have subsets with fewer or equal $n$ elements the number of such sets equals the number of subsets with elements MORE than $n$ .

$$\dfrac{2^{2n+1}}{2}=2^{2n}$$

You may select $k$ element subset from $2n+1$ element set in $(2n + 1)\choose k$ different ways. In this case as we want to construct sets of at most $n$ elements $k \le n$. So total number of subsets we are getting $\sum {(2n + 1)\choose k}$