Prove that $P(X)$ has exactly $\binom nk$ subsets of $X$ of $k$ elements each.

Question

Let set $X$ consist of $n$ members. $P(X)$ is power set of $X$.

Prove that set $P(X)$ has exactly $$\binom nk = \frac{n!}{k!(n-k)!}$$ subsets of $X$ of $k$ elements each. Hence, show that $P(X)$ contains $2^n$ members. Hint: use the binomial expansion of $(1 + 1)^n$.

I'm trying to get more into math (proof writing first) so I got this from a book about Real Analysis. It's a short first sub-chapter which was an intro review of set theory and I have absolutely no idea how to do this particular problem given what has been said in 8 pages.

I 'know' that it's true, since I've tried it. I can also somewhat prove that $P(X)$ has $2^n$ elements thinking of binary numbers. I can also see that the binomial expansion of $(1 + 1)^n$ does tell the number of subsets of $X$ that has $k$ elements via the coefficients. I just don't know how they all fit together given that the author thinks they should.

I've also seen some questions in here proving the summation of $\binom nk = 2^n$, which was suppose to help, but I couldn't understand them at all given my limited math/combinatorics knowledge.

Answer 1

Let $X$ a set with $n$ elements so to select a subset of $X$ with $k$ elements we have to choose $k$ elements from the $n$ elements of $X$ so we have $n\choose k$ possibilities of such choices.

The cardinal of $\mathcal{P}(X)$ is the number of all subset with $k$ elements for $k=0,\ldots,n$ so $$\mathrm{card}(\mathcal{P}(X))=\sum_{k=0}^n {n\choose k}=(1+1)^n=2^n.$$

Answer 2

I think some hints might be more appropriate here than actually answering the question: 1) If you take $k$ out of $n$ elements, you automatically also take $n-k$ out of $k$ elements - the other ones. The order of these elements doesn't matter.

2) All subsets of a finite set with $n$ elements have a certain amount of elements: $|\mathcal{P}(X)|=$the number of subsets = the number of subsets having no elements + the number of subsets having exactly one element+...+the number of subsets having exactly $n$ elements. How does this translate to $(1+1)^n$ using the first part of your question?

Answer 3

Personally, I'd take apart that fraction for the binomial co-efficient that has pieces that can be explained.

First, consider the idea of choosing $k$ elements from the set of $n$ elements where order matters initially. This should produce the $\frac{n!}{(n-k)!}$ expression that is a starting point.

Second, order doesn't matter here and thus this over counts the group where $k>1$ since one could re-order elements here. Thus, there is something to be said for dividing the initial quotient by $k!$ since this is the number of permutations of $k$ elements.

At least this would be my suggestion for how to go about doing a construction proof of what you want. If you want something to consider, look at Generating Functions where if you consider the expansion of $(x+1)^n$ and take the co-efficient of $x^k$ this would be the binomial coefficient. If you substitute $x=1$ then you would see how the $(1+1)^n$ is applicable here.