Formula Table

Ordered

Repetitions

Unique

Definition

Example

Allegory

-

$C_{n}^{k} = \frac{n!}{k!(n-k)!}$

$\begin{eqnarray*} S &=& \{C_{n}^{3}|n=3,k=2\} \\ &=& \{ (1,2), (1,3), (2,3)\} \end{eqnarray*}$

, $|S| = 3$

Combinations

x

-

$A_{n}^{k} = \frac{n!}{(n-k)!}$

$\begin{eqnarray*} S &=& \{A_{n}^{k}|n=3,k=2\} \\ &=& \{ (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) \} \end{eqnarray*}$

, $|S| = 6$

Arrangements

x

-

$n^{k}$

$\begin{eqnarray*} S &=& \{n^{k}|n=3,k=2\} \\ &=& \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \} \end{eqnarray*}$

, $|S| = 9$

Permutations with Repetitions

Term	Usage
Combinations	Food items in a salad that can only be selected together with other items.
Arrangements	Sorting a subset of items in order such that each item can only be selected at most once.
Permutation	A special case of "Arrangements" where the items to select are equal to the selected group size.
Permutations with Repetitions	A combination lock.

Note that classical permutations $P_{n}$ can be seen as a special case of arrangements when $A_{n}^{n}$ or $A_{n}^{n-1}$ such that $A_{n}^{n}=A_{n}^{n-1}=P_{n}=n!$ due to $A_{n}^{n}=A_{n}^{n-1}$ . In that sense, arrangements can be seen as a generalization of permutations when only some subset of the available items (the items to chose) have to selected.

Having said that, an interesting "brain-bug" is to immediately think about "permutations", as in $P_{n}$ , as suitable to calculate the number of settings on a combination lock or a padlock when, in fact, "permutations with repetitions" is the correct response.

To illustrate the difference between both $P_{n}$ and $n^{k}$ cases by using a combination lock the following distinction can be made:

$P_{n}$ would correspond to a combination lock that has the same number of drums as numbers on each drum; for example, for $2$ drums and $2$ numerals on the drum, the total set of settings $S$ is generated $S=\{ (1,1), (1,2), (2,1), (2,2) \}$ such that $|S|=P_{2}=2!=4$
$n^{k}$ would correspond to a more realistic combination lock that has a smaller number of drums than numbers written on the drums; for example, $2$ drums with numbers ranging $0..9$ , such that the total set of settings $S$ is generated $S = \{ (0,1), (0,2), (0,3), ..., (1,1), (1,2), (1,3), ..., (2,1), (2,2), (2,3), ..., ... \}$ such that $|S|=10^{2}=100$