Combination
High school
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.
Undergraduate (combinatorics)
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
Examples
-
Choosing a committee of $2$ members from a club of $10$ members
High school
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
High school
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$
High school
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
Things that may be mistaken for examples.
-
Electing a president and a vice president from a club of $10$ members
High school
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$
High school
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.
Distinctions involving this term
- 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}$.