> [!NOTE] Theorem > Let $A$ be a [[Finite Set|finite set]] of [[Cardinality|cardinality]] $n\in \mathbb{N}^{+}.$ Let $k\in \mathbb{N}^{+}$ such that $k\leq n.$ The number of [[Combination of n Letters|combinations]] of $k$ elements of $A$: that is, the number of [[Subsets|subsets]] $S \subset A$ such that $|S|=k$; is given by the [[Binomial Coefficient|Binomial Coefficient]] ${n \choose k} = \frac{n!}{k!(n-k)!}.$ ###### Double-counting proof: This proof essentially counts the number of injective function $f:[k]\to [n]$ in two ways. We know from [[Number of k-Permutations of n Letters (Injections between Finite Sets)]], that there are ${}^{n} P_{k} = \frac{n!}{(n-k)!}$ such functions. These injections can also be obtained uniquely by the following steps: 1. choose a $k$-element subset of $A$ (there are ${n \choose k}$ choices for this); 2. choose a permutation of these elements (by [[Number of Permutations of n Letters]], there are $k!$ choices for this). Thus by [[Product Rule for Counting (Fundamental Counting Principle)]], ${}^{n}P_{k} = {n\choose k} \cdot k!$which gives ${n \choose k} = \frac{{}^{n}P_{k}}{k!} = \frac{n!}{(n-k)!k!}.$ # Applications **Examples**: > [!Example] > A fair dies is tossed $8$ times. How many different outcomes can we have that contain the outcome $2$ exactly three times and the outcome $3$ exactly five? > > **Solution**: Each possible outcome is completely determined by specifying which tosses result to a $2$ - the remaining will be $3.$ Thus, to compute the number of possible outcomes, it is sufficient to compute the number of subsets of size $3$ from a set of cardinality $8.$ This is exactly ${8 \choose 3}=56.$ **Consequences**: See [[Number of Partitions of n Letters into Subsets of Given Sizes]].