Algebra
Textbooks
Boundless Algebra
Combinatorics and Probability
Combinatorics
Algebra Textbooks Boundless Algebra Combinatorics and Probability Combinatorics
Algebra Textbooks Boundless Algebra Combinatorics and Probability
Algebra Textbooks Boundless Algebra
Algebra Textbooks
Algebra
Concept Version 10
Created by Boundless

Combinations

A combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.

Learning Objective

  • Calculate the number of ways of selecting several things out of a larger group (where order doesn't matter) using combinations


Key Points

    • A combination is a mathematical concept where one counts the number of ways one can select several elements out of a larger group.
    • Unlike a permutation, when determining the number of combinations, order does not matter.
    • Formally, a $k$-combination of a set $S$ is a subset of $k$ distinct elements of $S$. If the set has $n$ elements the number of $k$-combinations is equal to the binomial coefficient: $\begin{pmatrix} n\\ k \end{pmatrix} = \frac {n(n-1)...(n-k+1)}{k(k-1)...1}$, which can be written using factorials as $\frac {n!}{k!(n-k)! }$ whenever $k \le n$ and which is zero when $k > n$.

Terms

  • binomial coefficient

    A coefficient of any of the terms in the expansion of the binomial power $(1+x)^n$.

  • combination

    A way of selecting elements from a set, where order does not matter.


Full Text

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$. $$

[ edit ]
Edit this content
Prev Concept
Permutations of Nondistinguishable Objects
Binomial Expansions and Pascal's Triangle
Next Concept
Subjects
  • Accounting
  • Algebra
  • Art History
  • Biology
  • Business
  • Calculus
  • Chemistry
  • Communications
  • Economics
  • Finance
  • Management
  • Marketing
  • Microbiology
  • Physics
  • Physiology
  • Political Science
  • Psychology
  • Sociology
  • Statistics
  • U.S. History
  • World History
  • Writing

Except where noted, content and user contributions on this site are licensed under CC BY-SA 4.0 with attribution required.