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.
A combination without repetition of objects from is a way of selecting objects from a list of . The selection rules are:
the order of selection does not matter (the same objects selected in different orders are regarded as the same combination);
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.
Let , ,..., be objects. A simple combination (or combination without repetition) of objects from the objects , ,..., is one of the possible ways to form a set containing of the 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, , and . There are three possible combinations of two objects from , and , that is, three possible ways to choose two objects from this set of three:Other combinations are not possible, because, for example, is the same as .
Denote by the number of possible combinations of objects from . How much is in general? In other words, how do we count the number of possible combinations of objects from ?
To answer this question, we need to recall the concepts of permutation and k-permutation introduced in previous lectures.
Like a combination, a -permutation of objects is one of the possible ways of choosing of the objects. However, in a -permutation the order of selection matters: two -permutations are regarded as different if the same objects are chosen, but they are chosen in a different order. On the contrary, in the case of combinations, the order in which the objects are chosen does not matter: two combinations that contain the same objects are regarded as equal.
Despite this difference between -permutations and combinations, it is very easy to derive the number of possible combinations () from the number of possible -permutations (). Consider a combination of objects from . This combination will be repeated many times in the set of all possible -permutations. It will be repeated one time for each possible way of ordering the objects. So, it will be repeated times ( is the number of all possible ways to order the objects - the number of permutations of objects). Therefore, if each combination is repeated times in the set of all possible -permutations, dividing the total number of -permutations () by , we obtain the number of possible combinations:
The number of possible combinations is often denoted byand is called a binomial coefficient.
Example The number of possible combinations of objects from is
A combination with repetition of objects from is a way of selecting objects from a list of . The selection rules are:
the order of selection does not matter (the same objects selected in different orders are regarded as the same combination);
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.
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 objectsis a valid multiset, but not a valid set, because the letter 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 , ,..., be objects. A combination with repetition of objects from the objects , ,..., is one of the possible ways to form a multiset containing objects taken from the set .
Example Consider three objects, , and . There are six possible combinations with repetition of two objects from , and , that is, six possible ways to choose two objects from this set of three, allowing for repetitions:Other combinations are not possible, because, for example, is the same as .
Denote by the number of possible combinations with repetition of objects from . How much is in general? In other words, how do we count the number of possible combinations with repetition of objects from ?
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 objects from . Let us represent an order as a string of crosses () and vertical bars (), where a vertical bar delimits two adjacent flavours and a cross denotes a scoop of a given flavour. For example,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 objects from . The number of possible ways to choose objects from is equal to the number of possible combinations without repetition of objects from . Therefore, there aredifferent orders we can make.
In general, choosing objects from with repetition is equivalent to writing a string with symbols, of which are vertical bars () and are crosses (). In turn, this is equivalent to choose the positions in the string (among the available ) that will contain a cross (the remaining ones will contain vertical bars). But choosing positions from is like choosing a combination without repetition of objects from . Therefore, the number of possible combinations with repetition is
The number of possible combinations with repetition is often denoted byand is called a multiset coefficient.
Example The number of possible combinations with repetition of objects from is
The following sections contain more details about combinations.
The binomial coefficient is so called because it appears in the binomial expansion:where .
The following is a useful recursive formula for computing binomial coefficients:
It is proved as follows:
Below you can find some exercises with explained solutions.
3 cards are drawn from a standard deck of 52 cards. How many different 3-card hands can possibly be drawn?
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 , then
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?
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 , then
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?
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 , then
Most learning materials found on this website are now available in a traditional textbook format.