Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the set |n| = {1,2,...,n}. How many subsets does it have of cardinality k and that contain the element 1?

I understand that with each element, you can either include it or not to have a total of k elements, but I'm not sure exactly how to show this for any set of finite size.

share|improve this question
2  
Perhaps the most basic way to show this is by induction: the number of subsets with $\,k\,$ elements that a set with $\,n\, $elements, $\,n\geq k\, $ , is given by the binomial coefficient $$\binom{n}{k}:=\frac{n!}{k!(n-k)!}$$ –  DonAntonio Dec 9 '12 at 2:51

2 Answers 2

It can be reduced to the case when choosing $k-1$ elements from the set $\{2,3,...,n\}$.

So the answer is $\displaystyle\binom{n-1}{k-1}$.

share|improve this answer

In order to choose a $k$-element subset $S$ of $\{1,\dots,n\}$ that contains $1$, you just choose the $(k-1)$-element subset of $\{2,\dots,n\}$ consisting of the other $k-1$ elements of $S$. In more technical terms, there is an obvious bijection between $k$-element subsets of $\{1,\dots,n\}$ that contain $1$ and arbitrary $(k-1)$-element subsets of $\{2,\dots,n\}$.

How many ways are there to choose $k-1$ elements from the set $\{2,\dots,n\}$, which has $n-1$ elements?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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