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 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:
Exercise set 1 (combinatorial problems involving combinations).
Most learning materials found on this website are now available in a traditional textbook format.