In mathematics, a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter. In smaller cases, it is possible to count the number of combinations. For example, given $3$ pieces of fruit: an apple, an orange and a pear. There are $3$ combinations of $2$ that can be drawn from this set: an apple and a pear, an apple and an orange, or a pear and an orange. 

Combinations can refer to the combination of $n$ things taken $k$ at a time with or without repetition. In the above example, repetition was not allowed. If, however, it was possible to have $2$ of any $1$ kind of fruit there would be $3$ more combinations: $2$ apples, $2$ oranges, and $2$ pears.

To understand the difference between a permutation and combination, consider a deck of $52$ cards, from which a poker hand ($5$ cards) is dealt. How many possible poker hands are there?

At first glance, this may seem like a permutation question, where one might consider how many distinct ways there are to make a stack of cards. However, there is one important difference: order does not matter in this problem. When dealt a poker hand during a game, order does not matter so you will have the same hand regardless of the order in which the cards are dealt. Combination problems involve such scenarios.

To approach such a question, begin with the permutations: how many possible poker hands are there, if order does matter? 

Recall the permutation formula: $\displaystyle{\frac{n!}{(n-k)!}}$, where $n$ is the number of distinct objects in the set, and $k$ is the number of objects selected. In this case, we can calculate the number of permutations as:

$$ $\displaystyle \begin{aligned} \frac{52!}{(52-5)!}&=\frac{52!}{47!}\\ &=52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \end{aligned}$

This yields approximately $311.9$ million possible poker hands. However, one has to count every possible hand many different times in this calculation. How many different times is one counting each distinct hand?

The key insight is that this second question—"How many different times is one counting each distinct hand?" is itself a permutation question. It is the same as the question "How many different ways can these five cards be rearranged in a hand?" There are $5$ possibilities for the first card, $4$ for the second, and so on. The answer is $5!$, which is $120$. So, since every possible hand has been counted $120$ times, divide our earlier result by $120$ to find that there are $\frac {52!}{(47!)(5! )}$, or about $2.6$ million possible poker hands.

Combinations turn out to have a surprisingly large number of applications. Consider the following questions:

• A school offers $50$ classes. Each student must choose $6$ of them to fill out a schedule. How many possible schedules can be made?
• A basketball team has $12$ players, but only $5$ will start. How many possible starting teams can they field?
• Your computer contains $300$ videos, but you can only fit $10$ of them on your phone. How many possible ways can you load your phone?

Each of these is a combinations question, and can be answered exactly like the card scenario. Since this type of question comes up in so many different contexts, it is given a special name and symbol. The last question would be referred to as "$300$ choose $10$" and written $\begin{pmatrix} 300\\ 10 \end{pmatrix}$. It is calculated as $\frac {300!}{(290!)(10! )}$, for reasons explained above.

Each possible combination of $k$ distinct elements of a set $S$ is known as a $k$-combination. If the set has $n$ elements, the number of $k$-combinations is equal to

$\begin{pmatrix} n\\ k \end{pmatrix} = \dfrac {n(n-1)...(n-k+1)}{k(k-1)...1}$ 

Which can be written using factorials as

$\dfrac {n!}{k!(n-k)! }$ 

Whenever $k \leq n$, and which is zero when $k > n$. The set of all $k$-combinations of a set $S$ is often denoted by $\begin{pmatrix} S \\ k \end{pmatrix}$, which is read as "$S$ choose $k$," such as in the phone example above. The set of $k$-combinations may also be denoted in certain texts by $C(n,k)$, or by a variation such as $C_k^n$, $_nC_k$, or $^nC_k$. 

General Considerations

The number of $k$-combinations, or $\begin{pmatrix} S \\ k \end{pmatrix}$, is also known as the binomial coefficient, because it occurs as a coefficient in the binomial formula. The binomial coefficient is the coefficient of the $x^k$ term in the polynomial expansion of $(1+x)^n$. $$