There is a strong relationship between Combinatorics and Computer Science. The knowledge of Combinatorics is not just used to solve difficult or boring math problems, but can really be used in our daily life (coding or counting). The importance of Combinatorics is the motivation of today’s article. In this article, I just want to show some basic methods related to Enumerative Combinatorics.
Table of Contents
- Pigeonhole Principle
- Combinations and Permutations
- Binomial Coefficients
- Inclusion-Exclusion Principle
- Generating Functions
The pigeonhole principle states:
If pigeons are in holes and , then at least 2 pigeons are in the same hole.
The Pigeonhole Principle is easy to understand, it is also very powerful for solving a class of problems whose goal is to find the existence of combination.
[Example.] Consider any five points in the interior of a square of side length 1. Show that one can find two of the points at distance at most apart.
[Proof.] Consider partitioning the square into 4 sub-squares. By the pigeonhole principle, 2 of the points must be in one sub-box. The distance between those two points must be less than the diameter of the sub-box, which is actually .
Then we are going to see a more difficult problem. In this problem, the pigeonhole is not clear.
[Example.] Given integers , not necessarily distinct, there exist integers and with such that the sum is a multiple of .
[Proof.] Consider the integers:
We divide these integers by , and thus we have
If one of these remainders is zero (i.e. ), then the corresponding is a multiple of . If none of is zero, then two of them must be the same integer (since ). We can assume , which means that is equal to . The minus of them, , is a multiple of .
[Example.] A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, in order not to tire himself, he decides not to play more than 12 games during any calendar week. Show that there exists a succession of consecutive days during which the chess master will have played exactly 21 games.
[Proof.] 11 weeks means that the chess master need to have a 77 day training. Suppose that the number of games he plays every day is , we can then define a sequence of integers:
It is obvious that , the sequence is strictly increasing.
Consider of a new sequence consists of 154 integer:
On the other hand, we know that
According to pigeonhole principle, two of the 154 integers must be equal. Since sub-sequence and are strictly increasing, then the two equal numbers must be of the forms and . We conclude that on the days , the chess master played a total of 21 games.
Besides the previous mentioned examples, pigeonhole principle is useful in number theory.
There is a famous example related to pigeonhole principle, Chinese Remainder Theorem.
[Example. Chinese Remainder Theorem] Let m and n be relatively prime positive integers. Then the following system has a solution.
[Proof.] we know that and . Consider of the following n integers:
Suppose that two of them had the same remainder when divided by , we can represent them as
Then if we subtract the first equation from the second, we have
Since , we conclude that . However, we know that , which means this is a contradiction. Thus the integers have distinct remainders when divided by . That is, each of the numbers occur as a remainder. In particular, then number does.
Now we are going to see the Strong Form of the pigeonhole principle:
Let be positive integers. If
objects are put into boxes, then either the 1st box contains at least objects, or the 2nd box contains at least objects, , the n-th box contains at least objects.
The proof of this theorem is simple, similar to the proof of the simple form of pigeonhole principle, we just use Counter-evidence. Suppose it is not true, the i-th box contains at most objects. Then the total number of objects can be at most:
which is a contradiction.
We can find that the simple form of the pigeonhole principle can be obtained from the strong form by taking .
In elementary mathematics, the strong form of the pigeonhole principle is most often applied in the special case when .
If the average of nonnegative integers is greater than , i.e.
then at least one of the integers is greater than or equal to . (i.e. )
There are two equivalent form:
If objects are put into boxes, at least one of the boxes contains or more objects.
If objects are put into boxes, at least one of the boxes contains or more objects.
The second one can be derived from the first one.
According to the definition of the ceiling function, we know that
We conclude that , then the second form can be derived by the first one.
Here is an example of the strong form.
[Example.] Show that every sequence of real numbers contains either an increasing subsequence or decreasing subsequence of length .
[Proof.] Suppose there is no increasing subsequence of length . We suffices to show that there must be a decreasing subsequence of length .
Let be the length of the longest increasing subsequence which begins with , . Since it is assumed that there is no increasing subsequence of length , we have for all . By the strong form of the pigeonhole principle, of the integers must be equal. (In this case, we try to put objects into only box, for the range of is , which contains different integers) i.e.
where . If there is one () such that , then any increasing subsequence of length beginning with will result a subsequence of length beginning with by adding in the front; so , which is contradictory to . Thus we must have
which is a decreasing subsequence of length .
The previous examples have shown the power of pigeonhole principle. Moreover, there are some other theories based on pigeonhole principle, for example, the Ramsey Theory.
Ramsey theory (click reference) is concerned with the preservation of structure under partitions. A famous and classical problem related to it is called Ramsey Problem:
[Example. Ramsey Problem] Given any six members of a social networking (or a dinner party), there will always exist either a trio whom are all friends, or a trio of which none are friends.
[Proof.] Label the six members in question and . There must exist a subset of size three such that is either friends with all of or is friends with none of , because there are 5 elements in the set and only two possible e friendship states (friend or not friend). Assuming, without loss of generality, that is friends with the three members of , simply look at the friendship states of the members of . If any two members are friends, then the trio are the required trio of friends. If no pair of members of are friends, then itself is a trio none of whom are friends. In either case, the required trio exists.
Actually, this kind of problems can be seen as graph edge coloring problem. Given a complete graph with , we know that this is a graph in which every vertex is adjacent, or connected by an edge, to every other vertex in . The number of edge in complete graph is
In the previous Ramsey problem, the number of vertex is 6, corresponding to a complete graph which describes the member relationship. If we use 2 color (e.g. red and blue) to colorize graph edges, there exists a triangle whose edges have the same color.
Here we give the formal definition of graph edge coloring:
Let be a set of colors , and be the edges of a graph . An edge coloring assigns each edge in to a color in . If an edge coloring uses colors on a graph, then it is know as a k-colored graph.
Similar to this simple problem (we call it ), we can also prove some other useful propositions such as , , ,
This class of problems can be sum up as Ramsey Number:
In 2-color case, a Ramsey Number, written as , is the smallest integer such that the 2-colored graph , using the colors red and blue for edges, implies a red monochromatic subgraph or a blue monochromatic subgraph .
In this way, the results of previous problems can be re-written by using Ramsey Number, , , , ,
There are some basic theorems related to Ramsey Number:
- For all , the equality holds
- For all , the relationship holds
- For all , the inequality holds
- For , , we have
Now give the proof of the last theorem using mathematical induction.
First, we establish the base case and :
Now assume that the relation holds for all , and , cases, we demonstrate that the , case holds:
Since the proof of the last theorem is derived from the third one, we also give a proof here.
Let be a 2-colored graph on vertices. Consider vertex . We denote as the number of vertices adjacent to via a red edge and denote as the number of vertices adjacent to via a blue edge. Moreover, we let the vertices adjacent to by a red edge form a set and similarly the vertices adjacent to by a blue edge form the set . It is clear that
From this we have two cases.
As the first case, if , then and we consider the vertices in . Because , then in the complete subgraph of formed from the vertices of and all edges between them there is a complete monochromatic subgraph on vertices or vertices. Additionally, since we established that the vertices in were all connected to by a blue edge, we can say that the complete subgraph of formed from the vertices of and all edges between them will contain a blue complete monochromatic subgraph on vertices. Thus, has a blue monochromatic subgraph of size , and the inequality holds in this case.
In the other case, we have and consider the vertices in . In the complete subgraph of formed from the vertices of and all edges between them, there is a complete monochromatic subgraph on vertices or vertices. Additionally, since all vertices in are connected to by a red edge, then the complete subgraph of formed from the vertices and all edges between them will contain a red complete monochromatic graph on edges. Thus, has a red monochromatic subgraph of size , and the inequality also holds. (Q.E.D.)
Actually, the coloring can be also seen as set partition problem. Edges with the same colors will be seen as a set, and all vertices can be divided into multiple sets. Here we introduce two graph notions:
- A clique of size is a set of vertices such that all pairs among them are edges
- An independent set of size is a set of vertices such that there is no edge between them
A clique or an independent set can be seen as a subset of total vertices. In this way, the Ramsey number can also be defined as this: The Ramsey Number is the minimum number such that any graph on vertices contains either an independent set of size or a clique of size .
The Ramsey Theorem states that: If and are integers, then there exists (and exists the smallest one) a positive integer such that
The above discussion concentrate on the case of 2-color, if we use multiple colors to do graph edge coloring, the Ramsey number becomes a generalized form. Here we introduce it from the perspective of partition: The Ramsey number is the minimum number such that any coloring of the edges of with colors contains a clique of size in color , for some .
In the general form, we can also get some generalized theorems:
- For all , the inequality holds
- For all , the inequality holds
- For all , the inequality holds
Note that the proof of the second theorem is similar to 2-color one, as what we have introduced. For general form, we also give a proof.
Recalling the strong form of the pigeonhole principle, it is clear that the form is very similar to the right hand of the inequality shown here. Let be a complete graph with vertices, and the value of is . Consider vertex , the number of vertex adjacent to is
whose form is the same as the strong form of the pigeonhole principle, the rest of this proof is obvious.
Now we give the general form of Ramsey Theorem in which pairs are replaced by subsets of elements for some fixed integer . We denote as he collection of all subsets of elements of a set of elements. The general Ramsey Theorem states that:
Given integers , and integers , there exists an integer such that
In words, there exists an integer such that if each of the -element subsets of a -element set is assigned one of colors , then either there are elements, all of whose -element subsets are assigned the color , or there are elements, all of whose -element subsets are assigned the color , and etc. The smallest such integer is the Ramsey Number . Note that the Ramsey Number we defined previously is the case that , which corresponds to 2-subsets (i.e. edge).
Here we also look at the case . The is the smallest number such that, if the elements of a set of elements are colored with one of the colors , then either there are elements of color , or elements of color , and etc. We find that this number is actually given by the strong form of pigeonhole principle.
which has already been proven.
Combinations and Permutations
This subsection is about the counting problems.
First we state the definition of the partition of a set. A partition of set is a collection of subsets of such that each element of is in exactly one of those subsets:
Thus, the sets are pairwise disjoint sets, and their union is .
There are some important principles and some of the counting formulas that they imply.
Suppose that a set is partitioned into pairwise disjoint parts . The number of objects in can be determined by finding the number of objects in each of the parts, and adding the numbers so obtained:
If the sets are allowed to overlap, then we need inclusion-exclusion principle.
Let be a set of ordered pairs of objects, where the first object comes from a set of size , and for each choice of object there are choices for object . Then the size of is
The multiplication principle is actually a consequence of the addition principle.
Let be a set and let U be a larger set containing . Let
be the complement of in . The the number of of objects in is given by the rule
The set here is usually some natural set consisting of all the objects.
Let be a finite set that is partitioned into parts in such a way that each part contains the same number of objects. Then the number of parts in the partition is given by the rule
Thus, we can determine the number of parts if we know the number of objects in and the common value of the number of objects in the parts.
Use the previous four principles, we can deal with many counting problems on a set or a multiset. We denote the number of r-permutations of an n-element set. If , then . Clearly for each positive integer . An n-permutation of an n-element set will be more simply called a permutation of .
For and positive integers with ,
Note that the number of permutations of elements is .
The permutations that we have just considered are more properly called linear permutations. If objects are arranged in a circle, the number of permutation is smaller. The number of circular r-permutation of a set of elements is given by
In particular, the number of circular permutations of elements is .
It is natural to regard two circular permutations as being the same provided one can be brought to the other by a rotation, that is, by a circular shift. Thus, we can prove the formula of circular permutation by using division principle.
The set of linear r-permutations can be partitioned into parts in such a way that two linear r-permutations correspond to the same circular r-permutation if and only if they are in the same part. Thus, the number of circular r-permutations equals the number of parts. Since each part contains linear r-permutations, the number of parts is given by . (Q.E.D.)
There is another useful way to view the counting of circular permutations. Suppose we wish to count the number of circular permutations of and . Since we are free to rotate these objects, any circular permutation can be rotated so that is in a fixed position; think it as the “head” of the circle. Now that is fixed, the circular permutations of all these 6 objects can be identified with the linear permutations of and . We know that there are linear permutations of these 5 objects, and hence circular permutations of these 6 objects.
r-combinations of Sets
Let be a set of elements. A combination of a set is a term usually used to denote an unordered selection of the elements of . The result of such a selection is a subset of the elements of . Thus a combination of is a choice of a subset of .
The result of an r-combination is an r-subset of , a subset of consisting of of the objects of . We denote the number of r-subsets of an n-elements set.
The following facts are readily seen to be true for each nonnegative integer n:
Actually, we know that the following equation can be derived for :
hence we have the formulas to calculate the number of combination:
The famous Pascal Triangle is an example of combination number. The corresponding Pascal’s Formula states that, for all integers and with , we have
Here we give a combinatorial proof. Let be a set of elements. We distinguish one of the elements of and denote it by . Let be the set obtained from by removing the element . We partition the set of k-subsets of into two parts, and . In we put all those k-subsets which do not contain . In we put all the k-subsets which do contain . By the addition principle,
The k-subsets in are exactly the k-subset of the set of elements. Thus, the size of is
A k-subset in can always be obtained by adjoining the element to a -subset of . Thus, the size of is
Combining these facts, we obtain
which is the same as what we state in Pascal’s Formula. (Q.E.D.)
r-permutation of infinite multiset
If is a multiset, an r-permutation of is an ordered arrangement of of the objects of . If the total number of objects of is , then an n-permutation of will also be called a permutation of .
Let be a multiset with objects of different types, where each object has an infinite repetition number. Then the number of r-permutation of is .
The proof of this theorem is obvious. In constructing an r-permutation of , we can choose the first item to be an object of any one of the types. Similarly, other positions can be an object of any one of the given types. The number of different choices for any item is always and it does not depend on the choices of any previous items. (Q.E.D.)
r-permutation of finite multiset
It is obvious that the number of an element in a multiset can be a finite integer. Let be a multiset with objects of different types with finite repetition numbers, which is . Let the size of be . Then the number of permutations of equals
The proof is also simple, use multiplication principle to calculate the number of combination. There are place in the given multiset , and we want to put exactly one of the objects of in each of the places. We first decide which places are to be occupied by the ’s, then decide the places which are to be occupied by the ’s, and so on. We continue like this, and invoke the multiplication principle and find that the number of permutations of equals
r-combination of infinite multiset
If is a multiset, then an r-combination of is an unordered selection of of the objects of . Thus, the result of the selection is itself a multiset, a sub-multiset of of size .
Let be a multiset with objects of types, each with an infinite repetition number. Then the number of the r-combination of equals
The proof of this theorem is very interesting. Here we give a short proof by converting it into another equivalent problem.
Let the types of objects of be so that
Any r-combination of is of the form , where are non-negative integers with . Conversely, every sequence of non-negative integers with corresponds to an r-combination of . Thus, the number of r-combinations of equals the number of solutions of
where are nonnegative integers. Actually, this number of these solutions equals the number of permutations of the following multiset
of objects of two different types. Given a permutation of , the *’s divide the 1’s into groups as the following sequence
Thus, the number of r-combinations of the multiset equals the number of permutations of , which is
The Binomial Coefficients
This subsection mainly talk about some fascinating properties of binomial coefficient. Actually, the binomial coefficient is the number of combination, which count the number of k-subsets of a set of element. Because of their appearance in the binomial theorem, they are called the binomial coefficients.
The Binomial Theorem
Let be a positive integer. Then, for all and ,
Note that this famous theorem can be proved by using various methods. The combinatorial proof or induction method are common used. Here we show both of these two methods.
We know that can be written as the product
which has factors each equal to . Since, for each factor we can choose either or in multiplying out , there are terms that result, and each can be arranged in the form for some . We obtain the term by choosing in of the factors and in the remaining factors. Thus the number of times the term occurs in the expanded product equals the number of k-subsets of the set of factors. (Q.E.D.)
The second proof is by induction on . If , the formula becomes
and this is clearly true. We now assume that the formula is true for a positive integer and prove that it is true when is replaced by .
Replacing by in the last summation, we obtain
Hence we have
which, using Pascal’s formula, becomes
This is the binomial theorem with replaced by . (Q.E.D.)
Newton's Binomial Theorem
The binomial theorem has a generalized form given by Isaac Newton.
Let be a real number. Then, for all and with ,
If is a positive integer n, it becomes the previous binomial theorem.
Unimodality of Binomial Coefficients
Check binomial coefficients in a row of Pascal’s triangle, we find that the numbers increase for a while and then decrease. A sequence of number with this property is called unimodal.
A sequence is unimodal, provided that there is an integer with , such that
The number is the largest number in the sequence. The integer is not necessarily unique because the largest number may occur in the sequence more than once.
Let be a positive integer. The sequence of binomial coefficients is a unimodal sequence.
If is an even integer,
If is an odd integer,
The largest binomial coefficients in the sequence is
Now we prove that the binomial coefficient is unimodal.
We consider the quotient of successive binomial coefficients in the sequence.
Let be an integer with . Then
Hence, the partial order of successive binomial coefficients is decided by and .
Now, if and only if . If is even, then, since is an integer, is equivalent to . If is odd, then is equivalent to . Hence, the binomial coefficients increase as indicated in the statement of the theorem. We now observe that if and only if . If is even, for any . If is odd, then , for . Thus, for even, no two consecutive binomial coefficients in the sequence are equal. For odd, the only two consecutive binomial coefficients of equal value are
That the binomial coefficients decrease as indicated in the theorem follows in a similar way. (Q.E.D.)
A number of interesting identities can be derived from what we have known.
The Multinomial Theorem
The binomial theorem gives a formula for for each positive integer . It can be generalized to give a formula for the nth power of the sum of real numbers: . In the general formula, the role of the binomial coefficients is taken over by numbers called the multinomial coefficients,
Here, are nonnegative integers with .
Actually, the binomial coefficient can be written as multinomial form
Let be a positive integer. For all ,
where the multinomial coefficient is equal to the number of r-permutation of finite multiset.
Pascal’s formula for the multinomial coefficients is
which can be verified by direct substitution, using the value of the multinomial coefficients.
The Pigeonhole principle is useful, which helps us for solving some basic counting problems. In this subsection, an important counting formula called the inclusion-exclusion principle is introduced. The addition principle gives a formula for counting the number of objects in a union of sets, provided that the sets do not overlap. The inclusion-exclusion principle gives a formula for general circumstances in which the sets are free to overlap without restriction.
Actually, the subtraction principle is the simplest instance of the inclusion-exclusion principle. As a first generalization of the subtraction principle, let S be a finite set of objects, Let be the subset of objects of that have property , and let be the subset of objects of that have property . we have the following formula
The inclusion-exclusion principle can be extend to any number of properties. Let be properties referring to the objects in , and let
be the subset of objects of that have property . The inclusion-exclusion principle states that the number of objects of the set that have none of the properties is given by
where the first sum is over all 1-subsets , the second sum is over all 2-subsets , and so on.
Here is a short proof of inclusion-exclusion principle. The left side of the equation counts the number of objects of with none of these properties . We know that an object with none of these properties makes a net contribution of 1 to the right side, and an object with at least one of the properties makes a net contribution of O. Consider an object with exactly properties. The contribution of to is 1, its contribution to the second item is , its contribution to is , its contribution to is , and so on. Thus, the net contribution of is
We know that this expression equals 0 according to the combinatorial identity. (Q.E.D.)
From the equation of inclusion-exclusion principle, we can get an corollary. The number of objects of which have at least one of the properties is given by
which can be derived from .
r-combination of finite multiset
Recalling that the number of r-combinations of a multiset with distinct objects, each with an infinite repetition number, equals . Now we consider of the number of r-combinations of a multiset without any restrictions on its repetition numbers.
Suppose is a multiset and an object of of a certain type has a repetition number that is greater than . The number of r-combinations of equals the number of r-combinations of the multiset obtained from by replacing the repetition number of by . This is so because the number of times can be used in an r-combination of cannot exceed .
Now we consider of an example to show how to use inclusion-exclusion principle to deal with this kind of problem. Although we shall take a specific example, it should be clear that the method works in general.
[Example.] Determine the number of lO-combinations of the multiset .
We shall apply the inclusion-exclusion principle to the set of all lO-combinations of the multiset . Let be the property that a 10-combination of has more than 3 ’s. Let be the property that a 10-combination of has more than 4 ’s. Finally, Let be the property that a 10-combination of has more than 5 ’s. As usual, let be the correspond set of property .
Then we can use the previous infinite version to find
Then the result can be obtained, it is .
We are given an n-element set in which each element has a specified location, and we are asked to find the number of permutations of the set in which no element is in its specified location. If we take to be , a derangement of is a permutation such that .
We denote by the number of derangements of . The inclusion–exclusion principle enables us to get a formula for the derangement numbers . For ,
Here we also give a proof. Let be the set of all permutations of . for , let be the property that, in a permutation, is in its natural position. Thus, the permutation has property provided . Let denote the set of permutations of with property . Hence,
and we use the inclusion–exclusion principle to evaluate .
Thus, the theorem is proved. (Q.E.D.)
Permutations with relative Forbidden Positions
We introduce the problem as follows: Suppose a class of eight boys takes a walk every day. The students walk in a line of eight so that every boy except the first is preceded by another. In order that a child not see the same person in front of him, on the second day the students decide to switch positions so that no boy is preceded by the same boy who preceded him on the first day. In how many ways can they switch positions?
For each positive integer , we let denote the number of permutations of in which none of the patterns , , , occurs. For
Here we give a proof.
Let be the set of all permutations of . Let be the property that, in a permutation, the pattern does occur, (). Thus, a permutation of is counted in the number if and only if it has none of the properties . Let denote the set of permutations of that satisfy property . Then
and we apply the inclusion-exclusion principle to evaluate .
It is clear that
Since, for each , there are k-subsets, applying the inclusion-exclusion principle we obtain the formula in the theorem.
Möbius Inversion is a more sophisticated mathematics than what we have talked about. I plan to write another independent article to introduce this technique. Here we just need to know that the inclusion-exclusion principle is an instance of Möbius Inversion on a finite partially ordered set.
In this subsection, we introduce the method of generating functions. Generating functions can be regarded as algebraic objects whose formal manipulation allows us to count the number of possibilities for a problem by means of algebra.
Suppose there is a infinite sequence of numbers
Its generating function is defined to be the infinite series
The coefficient of in is the nth term of the sequence.
Note that the generating function is just a algebraic object, we do not interested in the convergence or divergence of the series itself, but concentrate on the coefficient sequence. For those series which cannot converge, we define formal power series. In formal power series, the is just a abstract symbol which does not has specific value.
We denote all formal power series on as . With addition and multiplication, it becomes an entire ring. Designating a sequence whose term at index n is an by , one defines addition of two such sequences by
and multiplication by
which is called the Cauchy product of the two sequences of coefficients.
We can also define the derivative of formal power series as
which is called formal derivative of formal power series.
Now we will show 8 properties of generating functions. Consider two sequence and .
If , then
If , then
If , then
if , then
If , then
If , then
If , then
Using these 8 properties, we can derive 9 important generating functions:
Now we have shown some useful generating functions, they can be used for various counting problems about permutation and combination. The details of this kind of counting technique are introduced in any of textbooks of combinatorics, we are not going to show them here any more.
Now we just introduce two simple theorems about combination and permutation using generating functions.
[generating functions for combination]
If we want to extract element from , the times may occur is given by set , then the corresponding generating function of combination sequence is
[generating functions for permutation]
In this kind of problem, we usually use Exponential Generating Functions to simplify calculation. In exponential generating function, the basis is instead of .
Consider of k-permutation of . If the times may occur is given by set , the exponential generating function of the permutation sequence is