Step By Step Calculus » 8.5 - Permutations and Combinations

show_hiddenExpand All [+]
Synopsis
Factorial:\;\displaystyle n!=1\cdot 2\cdot 3\cdot 4\cdots(n-1)\cdot n\quad \forall n\in\mathbb{N}\;\displaystyle n!=1\cdot 2\cdot 3\cdot 4\cdots(n-1)\cdot n\quad \forall n\in\mathbb{N}
Generalized Permutations: There are P_{k}^{n}=\frac{n!}{(n-k)!}P_{k}^{n}=\frac{n!}{(n-k)!} possible arrangements of kk items selected from n\ge kn\ge k different objects.
Combinations: The number of ways to pick a group of size kk from nn distinct objects is
\displaystyle \binom{n}{k}=\frac{n!}{(n-k)!k!} .
\displaystyle \binom{n}{k}=\frac{n!}{(n-k)!k!} .
Facts about Combinations: These are the important facts to remember about combinations.
\displaystyle {\binom{n}{n}}\displaystyle {\binom{n}{n}}
\displaystyle =\displaystyle =
\displaystyle {\binom{n}{0}}=1 \displaystyle {\binom{n}{0}}=1
\displaystyle {\binom{n}{n-1}}\displaystyle {\binom{n}{n-1}}
\displaystyle =\displaystyle =
\displaystyle {\binom{n}{1}}=n \displaystyle {\binom{n}{1}}=n
\displaystyle {\binom{n}{k}}\displaystyle {\binom{n}{k}}
\displaystyle = \displaystyle =
\displaystyle \binom{n}{n-k} \displaystyle \binom{n}{n-k}
\displaystyle {\binom{n}{k}}\displaystyle {\binom{n}{k}}
\displaystyle = \displaystyle =
\displaystyle \binom{n-1}{k} + \binom{n-1}{k-1},\ \ (1\leq k\leq n) \displaystyle \binom{n-1}{k} + \binom{n-1}{k-1},\ \ (1\leq k\leq n)
Combination/Permutation Relation: One can relate permutation and combination using the following formulae:
\displaystyle \displaystyle Combinations\displaystyle ={n\choose k}=\frac{P_k^n}{k!}=\frac{\textrm{Permutations}}{\textrm{Orderings}} \displaystyle ={n\choose k}=\frac{P_k^n}{k!}=\frac{\textrm{Permutations}}{\textrm{Orderings}}
\bullet\bullet Order matters for permutations but is factored out for combinations.
Counting Strategies:
Question Type With replacement Without replacement
Ordered n^kn^k P_k^nP_k^n
Unordered Hard - try to avoid \binom{n}{k}\binom{n}{k}