Permutation vs. combination
Many counting problems choose $k$ different objects from a set of $n$ objects, and the result is either a permutation or a combination. A permutation is an ordered list of the chosen objects, so $(A, B)$ and $(B, A)$ are different permutations. A combination is the set of the chosen objects, with no order, so $\setdef{A, B}$ and $\setdef{B, A}$ are the same combination. For the numbers of permutations and combinations, see $P(n, k)$ vs. $\binom{n}{k}$.
Definitions
A permutation of a list of items is another list that has the same objects in a different order.
Consider a set of $n$ objects and a number $k \leq n$. A permutation of $k$ of the $n$ objects is an ordered list of $k$ different objects from the set, in which the order of the objects matters.
Consider a set $S$ with $n$ elements and a number $k \leq n$. A $k$-permutation of $S$ is an injective function
\[\sigma : \setdef{1, \dots, k} \to S,\]which lists the elements $\sigma(1), \dots, \sigma(k)$ in order. A permutation of $S$ is an $n$-permutation of $S$, which is the same as a bijective function from $\setdef{1, \dots, n}$ to $S$.
Examples
-
Electing a president and a vice president from a club of $10$ members
Each outcome of electing a president and a vice president from $10$ members is a permutation of $2$ of the members, because the outcome lists who is president first and who is vice president second.
-
The ordered list $(A, B)$ of $2$ of the letters $A$, $B$, and $C$
The ordered list $(A, B)$ is a permutation of $2$ of the letters $A$, $B$, and $C$, because it lists $2$ different letters in order. The list $(B, A)$ is a different permutation.
Non-examples
-
Choosing a committee of $2$ members from a club of $10$ members
A committee of $2$ members chosen from $10$ members is not a permutation, because the order does not matter: Ana and Ben is the same committee as Ben and Ana.
-
Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters
A draw of $6$ lottery numbers from $49$ is not a permutation, because a ticket wins with the right numbers in every order of drawing.
-
The set $\setdef{A, B}$ of $2$ of the letters $A$, $B$, and $C$
The set $\setdef{A, B}$ is not a permutation, because a set does not list its elements in an order: $\setdef{A, B}$ and $\setdef{B, A}$ are the same set.
Properties
- The number of permutations of $k$ of $n$ objects is $P(n, k) = n! / (n - k)!$, and the number of permutations of all $n$ objects is $n!$.
Consider a set of $n$ objects and a number $k \leq n$. A combination of $k$ of the $n$ objects is a selection of $k$ different objects from the set, in which the order of the objects does not matter.
Consider a set $S$ with $n$ elements and a number $k \leq n$. A $k$-combination of $S$ is a subset of $S$ with $k$ elements.
Examples
-
Choosing a committee of $2$ members from a club of $10$ members
Each committee of $2$ members chosen from $10$ members is a combination of $2$ of the members, because a committee is a set of members, with no order.
-
Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters
Each draw of $6$ lottery numbers from $49$ is a combination of $6$ of the numbers, because only the set of numbers drawn matters.
-
The set $\setdef{A, B}$ of $2$ of the letters $A$, $B$, and $C$
The set $\setdef{A, B}$ is a combination of $2$ of the letters $A$, $B$, and $C$, because it contains $2$ different letters, with no order.
Non-examples
-
Electing a president and a vice president from a club of $10$ members
An outcome of electing a president and a vice president from $10$ members is not a combination, because the order matters: Ana as president and Ben as vice president is a different outcome from Ben as president and Ana as vice president.
-
The ordered list $(A, B)$ of $2$ of the letters $A$, $B$, and $C$
The ordered list $(A, B)$ is not a combination, because a combination has no order; the combination $\setdef{A, B}$ corresponds to both $(A, B)$ and $(B, A)$.
Properties
- The number of combinations of $k$ of $n$ objects is the binomial coefficient $\binom{n}{k}$, read “$n$ choose $k$.”
- Each combination of $k$ objects can be put in order in $k!$ ways, so each combination corresponds to $k!$ permutations.
Examples
| Example | permutation | combination | Why |
|---|---|---|---|
| The ordered list $(A, B)$ of $2$ of the letters $A$, $B$, and $C$ | ✓ | ✗ | |
| The set $\setdef{A, B}$ of $2$ of the letters $A$, $B$, and $C$ | ✗ | ✓ | The set $\setdef{A, B}$ is one combination, but the same two letters form two permutations, $(A, B)$ and $(B, A)$. |
| Electing a president and a vice president from a club of $10$ members | ✓ | ✗ | |
| Choosing a committee of $2$ members from a club of $10$ members | ✗ | ✓ | |
| Drawing $6$ different lottery numbers from $1, 2, \dots, 49$, where only the set of numbers drawn matters | ✗ | ✓ |
Notes
- The everyday word “combination,” as in a “combination lock,” usually means a permutation, because the order of the numbers matters.
A combination is written as a set, like ${A, B, C}$, because the order does not matter, whereas a permutation is written as a list or a tuple, like $(A, B, C)$ or $(C, B, A)$ because the order does matter.