1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.$$

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ On a side note, I'd define $\binom nk$ as the number of ways to get a $k$-element subset from an $n$-element set. $\endgroup$
    – HSN
    Jul 29 '13 at 17:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.