Search for probability and statistics terms on Statlect
StatLect
Index > Mathematical tools

Combinations

by , PhD

This lecture introduces combinations, one of the most important concepts in combinatorial analysis. Before reading this lecture, you should be familiar with the concept of permutation.

We first deal with combinations without repetition and then with combinations with repetition.

Table of Contents

Combinations without repetition

A combination without repetition of k objects from n is a way of selecting k objects from a list of n. The selection rules are:

  1. the order of selection does not matter (the same objects selected in different orders are regarded as the same combination);

  2. each object can be selected only once.

A combination without repetition is also called a simple combination or, simply, a combination.

The following subsections give a slightly more formal definition of combination and deal with the problem of counting the number of possible combinations.

Definition of combination without repetition

Let a_1, a_2,..., a_n be n objects. A simple combination (or combination without repetition) of k objects from the n objects a_1, a_2,..., a_n is one of the possible ways to form a set containing k of the n objects. To form a valid set, any object can be chosen only once. Furthermore, the order in which the objects are chosen does not matter.

Example Consider three objects, a_1, a_2 and $a_{3}$. There are three possible combinations of two objects from a_1, a_2 and $a_{3}$, that is, three possible ways to choose two objects from this set of three:[eq1]Other combinations are not possible, because, for example, [eq2] is the same as [eq3].

Number of combinations without repetition

Denote by $C_{n,k}$ the number of possible combinations of k objects from n. How much is $C_{n,k}$ in general? In other words, how do we count the number of possible combinations of k objects from n?

To answer this question, we need to recall the concepts of permutation and k-permutation introduced in previous lectures.

Like a combination, a k-permutation of n objects is one of the possible ways of choosing k of the n objects. However, in a k-permutation the order of selection matters: two k-permutations are regarded as different if the same k objects are chosen, but they are chosen in a different order. On the contrary, in the case of combinations, the order in which the k objects are chosen does not matter: two combinations that contain the same objects are regarded as equal.

Despite this difference between k-permutations and combinations, it is very easy to derive the number of possible combinations ($C_{n,k}$) from the number of possible k-permutations ($P_{n,k}$). Consider a combination of $k $ objects from n. This combination will be repeated many times in the set of all possible k-permutations. It will be repeated one time for each possible way of ordering the k objects. So, it will be repeated $P_{k}=k!$ times ($P_{k}$ is the number of all possible ways to order the k objects - the number of permutations of k objects). Therefore, if each combination is repeated $P_{k}$ times in the set of all possible k-permutations, dividing the total number of k-permutations ($P_{n,k}$) by $P_{k}$, we obtain the number of possible combinations:[eq4]

The number of possible combinations is often denoted by[eq5]and $inom{n}{k}$ is called a binomial coefficient.

Example The number of possible combinations of $3$ objects from $5$ is[eq6]

Combinations with repetition

A combination with repetition of k objects from n is a way of selecting k objects from a list of n. The selection rules are:

  1. the order of selection does not matter (the same objects selected in different orders are regarded as the same combination);

  2. each object can be selected more than once.

Thus, the difference between simple combinations and combinations with repetition is that objects can be selected only once in the former, while they can be selected more than once in the latter.

The following subsections give a slightly more formal definition of combination with repetition and deal with the problem of counting the number of possible combinations with repetition.

Definition of combination with repetition

A more rigorous definition of combination with repetition involves the concept of multiset, which is a generalization of the notion of set (see the lecture entitled Set theory). Roughly speaking, the difference between a multiset and a set is the following: the same object is allowed to appear more than once in the list of members of a multiset, while the same object is allowed to appear only once in the list of members of an ordinary set. Thus, for example, the collection of objects[eq7]is a valid multiset, but not a valid set, because the letter a appears more than once. Like sets, multisets are unordered collections of objects, i.e. the order in which the elements of a multiset are listed does not matter.

Let a_1, a_2,..., a_n be n objects. A combination with repetition of k objects from the n objects a_1, a_2,..., a_n is one of the possible ways to form a multiset containing k objects taken from the set [eq8].

Example Consider three objects, a_1, a_2 and $a_{3}$. There are six possible combinations with repetition of two objects from a_1, a_2 and $a_{3}$, that is, six possible ways to choose two objects from this set of three, allowing for repetitions:[eq9]Other combinations are not possible, because, for example, [eq10] is the same as [eq11].

Number of combinations with repetition

Denote by $C_{n,k}^{prime }$ the number of possible combinations with repetition of k objects from n. How much is $C_{n,k}^{prime }$ in general? In other words, how do we count the number of possible combinations with repetition of k objects from n?

To answer this question, we need to use a slightly unusual procedure, which is introduced by the next example.

Example We need to order two scoops of ice cream, choosing among four flavours: chocolate, pistachio, strawberry and vanilla. It is possible to order two scoops of the same flavour. How many different combinations can we order? The number of different combinations we can order is equal to the number of possible combinations with repetition of $2$ objects from $4$. Let us represent an order as a string of crosses ($ imes $) and vertical bars ($|$), where a vertical bar delimits two adjacent flavours and a cross denotes a scoop of a given flavour. For example,[eq12]where the first vertical bar (the leftmost one) delimits chocolate and pistachio, the second one delimits pistachio and strawberry and the third one delimits strawberry and vanilla. Each string contains three vertical bars, one less than the number of flavours, and two crosses, one for each scoop. Therefore, each string contains a total of five symbols. Making an order is equivalent to choosing which two of the five symbols will be a cross (the remaining will be vertical bars). So, to make an order, we need to choose $2$ objects from $5$. The number of possible ways to choose $2$ objects from $5$ is equal to the number of possible combinations without repetition of $2$ objects from $5$. Therefore, there are[eq13]different orders we can make.

In general, choosing k objects from n with repetition is equivalent to writing a string with $n+k-1$ symbols, of which $n-1$ are vertical bars ($|$) and k are crosses ($ imes $). In turn, this is equivalent to choose the k positions in the string (among the available $n+k-1$) that will contain a cross (the remaining ones will contain vertical bars). But choosing k positions from $n+k-1$ is like choosing a combination without repetition of k objects from $n+k-1$. Therefore, the number of possible combinations with repetition is[eq14]

The number of possible combinations with repetition is often denoted by[eq15]and [eq16] is called a multiset coefficient.

Example The number of possible combinations with repetition of $3$ objects from $5$ is[eq17]

More details

The following sections contain more details about combinations.

Binomial coefficients and binomial expansions

The binomial coefficient is so called because it appears in the binomial expansion:[eq18]where $nin U{2115} $.

Recursive formula for binomial coefficients

The following is a useful recursive formula for computing binomial coefficients:[eq19]

Proof

It is proved as follows:[eq20]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

3 cards are drawn from a standard deck of 52 cards. How many different 3-card hands can possibly be drawn?

Solution

First of all, the order in which the 3 cards are drawn does not matter (the same cards drawn in different orders are regarded as the same 3-card hand). Furthermore, each card can be drawn only once. Therefore the number of different 3-card hands that can possibly be drawn is equal to the number of possible combinations without repetition of 3 objects from 52. If we denote it by $C_{52,3}$, then[eq21]

Exercise 2

John has got 1 dollar, with which he can buy green, red and yellow candies. Each candy costs 50 cents. John will spend all the money he has on candies. How many different combinations of green, red and yellow candies can he buy?

Solution

First of all, the order in which the 3 different colours are chosen does not matter. Furthermore, each colour can be chosen more than once. Therefore, the number of different combinations of coloured candies John can choose is equal to the number of possible combinations with repetition of 2 objects from 3. If we denote it by $C_{3,2}^{prime }$, then[eq22]

Exercise 3

The board of directors of a corporation comprises 10 members. An executive board, formed by 4 directors, needs to be elected. How many possible ways are there to form the executive board?

Solution

First of all, the order in which the 4 directors are selected does not matter. Furthermore, each director can be elected to the executive board only once. Therefore, the number of different ways to form the executive board is equal to the number of possible combinations without repetition of 4 objects from 10. If we denote it by $C_{10,4}$, then[eq23]

How to cite

Please cite as:

Taboga, Marco (2021). "Combinations", Lectures on probability theory and mathematical statistics. Kindle Direct Publishing. Online appendix. https://www.statlect.com/mathematical-tools/combinations.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.