1
$\begingroup$

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.

  • 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)!}$2012-12-09

2 Answers 2

4

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

3

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?