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.

Pigeonhole Principle

The pigeonhole principle states:

If $m$ pigeons are in $n$ holes and $m>n$, then at least 2 pigeons are in the same hole.

Here is a reference of this famous principle. Another slide can also be helpful.

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 $P_1,P_2,\ldots,P_5$ in the interior of a square $S$ of side length 1. Show that one can find two of the points at distance at most $\sqrt{2}/2$ 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 $\sqrt{2}/2$.

Then we are going to see a more difficult problem. In this problem, the pigeonhole is not clear.

[Example.] Given $n$ integers $a_1,a_2,\ldots,a_n$, not necessarily distinct, there exist integers $k$ and $l$ with $% $ such that the sum $a_{k+1}+a_{k+2}+\cdots +a_{l}$ is a multiple of $n$.

[Proof.] Consider the $n$ integers:

We divide these integers by $n$, and thus we have

If one of these remainders $r_i$ is zero (i.e. $r_k=0$), then the corresponding $a_1+a_2+\cdots + a_k$ is a multiple of $n$. If none of $r_i$ is zero, then two of them must be the same integer (since $1\leqslant r_i\leqslant n-1$). We can assume $r_k=r_l$, which means that $a_1+a_2+\cdots + a_k$ is equal to $a_1+a_2+\cdots +a_l$. The minus of them, $a_{k+1},a_{k+2}+\cdots +a_{l}$, is a multiple of $n$.

[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 $n_i\;\, (i \leqslant 77)$, 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 $a_i$ and $a_i+21$ are strictly increasing, then the two equal numbers must be of the forms $a_i$ and $a_j+21$. We conclude that on the days $j+1,j+2,\ldots,i$, 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 $r$ when divided by $n$, we can represent them as

Then if we subtract the first equation from the second, we have

Since $\gcd(m,n)=1$, we conclude that $n\,\vert\,(j-i)$. However, we know that $% $, which means this is a contradiction. Thus the $n$ integers have distinct remainders when divided by $n$. That is, each of the $n$ numbers $0,1,\ldots,n-1$ occur as a remainder. In particular, then number $b$ does.

Now we are going to see the Strong Form of the pigeonhole principle:

Let $q_1,q_2,\ldots,q_n$ be positive integers. If

objects are put into $n$ boxes, then either the 1st box contains at least $q_1$ objects, or the 2nd box contains at least $q_2$ objects, $\ldots$, the n-th box contains at least $q_n$ 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 $q_i-1$ 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 $q_1=q_2=\cdots=q_n=2$.

In elementary mathematics, the strong form of the pigeonhole principle is most often applied in the special case when $q_1=q_2=\cdots=q_n=r$.

If the average of $n$ nonnegative integers $a_1,a_2,\ldots,a_n$ is greater than $r-1$, i.e.

then at least one of the integers is greater than or equal to $r$. (i.e. $\exists\, i\in[1,n],\; a_i\geqslant r$)

There are two equivalent form:

• If $n(r − 1) + 1$ objects are put into $n$ boxes, at least one of the boxes contains $r$ or more objects.

• If $m$ objects are put into $n$ boxes, at least one of the boxes contains $\left\lceil\dfrac{m}{n}\right\rceil$ 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 $m \geqslant n\Big(\left\lceil\dfrac{m}{n}\right\rceil-1\Big) + 1$, then the second form can be derived by the first one.

Here is an example of the strong form.

[Example.] Show that every sequence $a_1,a_2,\cdots,a_{n^2+1}$ of $n^2+1$ real numbers contains either an increasing subsequence or decreasing subsequence of length $n+1$.

[Proof.] Suppose there is no increasing subsequence of length $n + 1$. We suffices to show that there must be a decreasing subsequence of length $n + 1$.

Let $\ell_k$ be the length of the longest increasing subsequence which begins with $a_k$, $1 \leqslant k \leqslant n^2+1$. Since it is assumed that there is no increasing subsequence of length $n + 1$, we have $1\leqslant \ell_k \leqslant n$ for all $k$. By the strong form of the pigeonhole principle, $n+1$ of the $n^2+1$ integers $\ell_1,\ell_2,\ldots,\ell_{n^2+1}$ must be equal. (In this case, we try to put $n^2+1$ objects into only $n$ box, for the range of $\ell_k$ is $[1,n]$, which contains $n$ different integers) i.e.

where $% $. If there is one $k_i$ ($1\leqslant i \leqslant n$) such that $% $, then any increasing subsequence of length $\ell_{k_{i+1}}$ beginning with $a_{k_{i+1}}$ will result a subsequence of length $\ell_{k_{i+1}}+1$ beginning with $a_{k_{i}}$ by adding $a_{k_{i}}$ in the front; so $\ell_{k_i}>\ell_{k_{i+1}}$, which is contradictory to $\ell_{k_i}=\ell_{k_{i+1}}$. Thus we must have

which is a decreasing subsequence of length $n + 1$.

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 $A,B,C,D,E$ and $F$. There must exist a subset $S\subset\{B,C,D,E,F\}$ of size three such that $A$ is either friends with all of $S$ or is friends with none of $S$, because there are 5 elements in the set $\{B,C,D,E,F\}$ and only two possible e friendship states (friend or not friend). Assuming, without loss of generality, that $A$ is friends with the three members of $S$, simply look at the friendship states of the members of $S$. If any two members $s_1,s_2\in S$ are friends, then the trio $A, s_1, s_2$ are the required trio of friends. If no pair of members of $S$ are friends, then $S$ 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 $G=(V,E)$ with $\vert V\vert=n$, we know that this is a graph in which every vertex is adjacent, or connected by an edge, to every other vertex in $G$. The number of edge in complete graph $K_n$ is

In the previous Ramsey problem, the number of vertex is 6, corresponding to a complete graph $K_6$ 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 $C$ be a set of colors $\{c_1,c_2,\ldots, c_m\}$, and $E(G)$ be the edges of a graph $G$. An edge coloring $f:E\rightarrow C$ assigns each edge in $E(G)$ to a color in $C$. If an edge coloring uses $k$ colors on a graph, then it is know as a k-colored graph.

Similar to this simple problem (we call it $K_6 >> K_3$), we can also prove some other useful propositions such as $K_6 >> K_3\,\vert\, K_3$, $K_{10}>> K_4 \,\vert\,K_3$, $K_{9}>> K_4\,\vert\, K_3$, $\ldots$

This class of problems can be sum up as Ramsey Number:

In 2-color case, a Ramsey Number, written as $n=R(r,b)$, is the smallest integer $n$ such that the 2-colored graph $K_n$, using the colors red and blue for edges, implies a red monochromatic subgraph $K_r$ or a blue monochromatic subgraph $K_b$.

In this way, the results of previous problems can be re-written by using Ramsey Number, $R(1,k)=1$, $R(3,3)=6$, $R(3,4)=9$, $R(4,4)=18$, $\ldots$

There are some basic theorems related to Ramsey Number:

• For all $k\in \mathbb{N}$, the equality $R(k,2)=k$ holds
• For all $r,b\in \mathbb{N}$, the relationship $R(r,b) = R(b,r)$ holds
• For all $r,b\in \mathbb{N}$, the inequality $R(r,b)\leqslant R(r-1,b)+R(r,b-1)$ holds
• For $r,b \geqslant 2$, $r,b\in\mathbb{N}$, we have $R(r,b)\leqslant \dbinom{r+b-2}{r-1}$

Now give the proof of the last theorem using mathematical induction.

First, we establish the base case $r=2$ and $b=2$:

Now assume that the relation holds for all $r=x-1$,$b=y$ and $r=x$, $b=y-1$ cases, we demonstrate that the $r=x$, $b=y$ case holds:

(Q.E.D.)

Since the proof of the last theorem is derived from the third one, we also give a proof here.

Let $G=(V,E)$ be a 2-colored graph on $R(r-1,b)+R(r,b-1)$ vertices. Consider vertex $v\in V$. We denote $n_r$ as the number of vertices adjacent to $v$ via a red edge and denote $n_b$ as the number of vertices adjacent to $v$ via a blue edge. Moreover, we let the $n_r$ vertices adjacent to $v$ by a red edge form a set $S_r$ and similarly the $n_b$ vertices adjacent to $v$ by a blue edge form the set $S_b$. It is clear that

From this we have two cases.

As the first case, if $% $, then $n_b \geqslant R(r,b-1)$ and we consider the vertices in $S_b$. Because $n_b \geqslant R(r,b-1)$, then in the complete subgraph of $G$ formed from the vertices of $S_b$ and all edges between them there is a complete monochromatic subgraph $M$ on $r$ vertices or $s-1$ vertices. Additionally, since we established that the vertices in $S_b$ were all connected to $v$ by a blue edge, we can say that the complete subgraph of $G$ formed from the vertices of $S_b+v$ and all edges between them will contain a blue complete monochromatic subgraph on $b$ vertices. Thus, $G$ has a blue monochromatic subgraph of size $b$, and the inequality holds in this case.

In the other case, we have $n_r \geqslant R(r-1,b)$ and consider the vertices in $S_r$. In the complete subgraph of $G$ formed from the vertices of $S_r$ and all edges between them, there is a complete monochromatic subgraph $N$ on $r-1$ vertices or $b$ vertices. Additionally, since all vertices in $S_r$ are connected to $v$ by a red edge, then the complete subgraph of $G$ formed from the vertices $S_r+v$ and all edges between them will contain a red complete monochromatic graph on $r$ edges. Thus, $G$ has a red monochromatic subgraph of size $r$, 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 $V$ can be divided into multiple sets. Here we introduce two graph notions:

• A clique of size $t$ is a set of $t$ vertices such that all pairs among them are edges
• An independent set of size $s$ is a set of $s$ vertices such that there is no edge between them

A clique or an independent set can be seen as a subset of total $\vert V\vert$ vertices. In this way, the Ramsey number can also be defined as this: The Ramsey Number $R(s,t)$ is the minimum number $n$ such that any graph on $n$ vertices contains either an independent set of size $s$ or a clique of size $t$.

The Ramsey Theorem states that: If $m\geqslant 2$ and $n\geqslant 2$ are integers, then there exists (and exists the smallest one) a positive integer $p$ 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 $n=R_k(s_1,s_2,\ldots,s_k)$ is the minimum number $n$ such that any coloring of the edges of $K_n$ with $k$ colors contains a clique of size $s_i$ in color $i$, for some $i$.

In the general form, we can also get some generalized theorems:

• For all $s_1,s_2,\ldots,s_k \in \mathbb{N}$, the inequality $R_k(s_1,s_2,\ldots,s_k)\leqslant R_2\big(s_1,R_{k-1}(s_2,s_3,\ldots,s_k)\big)$ holds
• For all $s_i \geqslant 2$, the inequality $R_k(s_1,s_2\ldots,s_k)\leqslant R_k(s_1-1,s_2,\ldots,s_k)+\cdots+R_k(s_1,s_2,\ldots,s_k-1)-k+2$ holds
• For all $s_i\geqslant 1$, the inequality $R_k(s_1,s_2,\ldots,s_k)\leqslant R_{k/2}\big(R_2(s_1,s_2),R_2(s_3,s_4),\ldots,R_2(s_{k-1},s_{k})\big)$ 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 $q_1+q_2+\cdots + q_n -n+1$ is very similar to the right hand of the inequality shown here. Let $G$ be a complete graph with $n$ vertices, and the value of $n$ is $R_k(s_1-1,s_2,\ldots,s_k)+\cdots+R_k(s_1,s_2,\ldots,s_k-1)-k+2$. Consider vertex $v\in V$, the number of vertex adjacent to $v$ 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 $t$ elements for some fixed integer $t\geqslant 1$. We denote $K_{n}^t$ as he collection of all subsets of $t$ elements of a set of $n$ elements. The general Ramsey Theorem states that:

Given integers $t\geqslant 2$, and integers $q_1, q_2,\ldots,q_k \geqslant t$, there exists an integer $p$ such that

In words, there exists an integer $p$ such that if each of the $t$-element subsets of a $p$-element set is assigned one of $k$ colors $c_1,c_2,\ldots,c_k$, then either there are $q_1$ elements, all of whose $t$-element subsets are assigned the color $c_1$, or there are $q_2$ elements, all of whose $t$-element subsets are assigned the color $c_2$, and etc. The smallest such integer $p$ is the Ramsey Number $R_k^t(q_1,q_2,\ldots,q_k)$. Note that the Ramsey Number $R_k$ we defined previously is the case that $t=2$, which corresponds to 2-subsets (i.e. edge).

Here we also look at the case $t=1$. The $R_{k}^1(q_1,q_2,\ldots,q_k)$ is the smallest number $p$ such that, if the elements of a set of $p$ elements are colored with one of the colors $c_1,c_2,\ldots,c_k$, then either there are $q_1$ elements of color $c_1$, or $q_2$ elements of color $c_2$, and etc. We find that this number $p$ 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 $S$ is a collection $S_1,S_2,\ldots,S_m$ of subsets of $S$ such that each element of $S$ is in exactly one of those subsets:

Thus, the sets $S_1,S_2,\ldots,S_m$ are pairwise disjoint sets, and their union is $S$.

There are some important principles and some of the counting formulas that they imply.

Suppose that a set $S$ is partitioned into pairwise disjoint parts $S_1,S_2,\ldots,S_m$. The number of objects in $S$ can be determined by finding the number of objects in each of the parts, and adding the numbers so obtained:

If the sets $S_i$ are allowed to overlap, then we need inclusion-exclusion principle.

Multiplication Principle

Let $S$ be a set of ordered pairs $(a,b)$ of objects, where the first object $a$ comes from a set of size $p$, and for each choice of object $a$ there are $q$ choices for object $b$. Then the size of $S$ is

The multiplication principle is actually a consequence of the addition principle.

Subtraction Principle

Let $A$ be a set and let U be a larger set containing $A$. Let

be the complement of $A$ in $U$. The the number of $\vert A\vert$ of objects in $A$ is given by the rule

The set $U$ here is usually some natural set consisting of all the objects.

Division Principle

Let $S$ be a finite set that is partitioned into $k$ 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 $S$ 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 $P(n,r)$ the number of r-permutations of an n-element set. If $r>n$, then $P(n,r)=0$. Clearly $P(n,1)=n$ for each positive integer $n$. An n-permutation of an n-element set $S$ will be more simply called a permutation of $S$.

r-permutation

For $n$ and $r$ positive integers with $r\leqslant n$,

Note that the number of permutations of $n$ elements is $P(n,n)=n!$.

circular r-permutation

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 $n$ elements is given by

In particular, the number of circular permutations of $n$ elements is $(n-1)!$.

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 $r$ linear r-permutations, the number of parts is given by $P(n,r)/r$. (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 $A,B,C,D,E$ and $F$. Since we are free to rotate these objects, any circular permutation can be rotated so that $A$ is in a fixed position; think it as the “head” of the circle. Now that $A$ is fixed, the circular permutations of all these 6 objects can be identified with the linear permutations of $B,C,D,E$ and $F$. We know that there are $5!$ linear permutations of these 5 objects, and hence $5!$ circular permutations of these 6 objects.

r-combinations of Sets

Let $S$ be a set of $n$ elements. A combination of a set $S$ is a term usually used to denote an unordered selection of the elements of $S$. The result of such a selection is a subset $A$ of the elements of $S$. Thus a combination of $S$ is a choice of a subset of $S$.

The result of an r-combination is an r-subset of $S$, a subset of $S$ consisting of $r$ of the $n$ objects of $S$. We denote $\binom{n}{r}$ 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 $0\leqslant r\leqslant n$:

hence we have the formulas to calculate the number of combination:

Pascal's Formula

The famous Pascal Triangle is an example of combination number. The corresponding Pascal’s Formula states that, for all integers $n$ and $k$ with $1\leqslant k \leqslant n-1$, we have

Here we give a combinatorial proof. Let $S$ be a set of $n$ elements. We distinguish one of the elements of $S$ and denote it by $x$. Let $S\,\backslash\,\{x\}$ be the set obtained from $S$ by removing the element $x$. We partition the set $X$ of k-subsets of $S$ into two parts, $A$ and $B$. In $A$ we put all those k-subsets which do not contain $x$. In $B$ we put all the k-subsets which do contain $x$. By the addition principle,

The k-subsets in $A$ are exactly the k-subset of the set $S\,\backslash\,\{x\}$ of $n-1$ elements. Thus, the size of $A$ is

A k-subset in $B$ can always be obtained by adjoining the element $x$ to a $(k-1)$-subset of $S\,\backslash\, \{x\}$. Thus, the size of $B$ 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 $S$ is a multiset, an r-permutation of $S$ is an ordered arrangement of $r$ of the objects of $S$. If the total number of objects of $S$ is $n$, then an n-permutation of $S$ will also be called a permutation of $S$.

Let $S$ be a multiset with objects of $k$ different types, where each object has an infinite repetition number. Then the number of r-permutation of $S$ is $k^r$.

The proof of this theorem is obvious. In constructing an r-permutation of $S$, we can choose the first item to be an object of any one of the $k$ types. Similarly, other positions can be an object of any one of the given $k$ types. The number of different choices for any item is always $k$ 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 $S$ be a multiset with objects of $k$ different types with finite repetition numbers, which is $S = \{n_1\cdot a_1,n_2\cdot a_2\ldots,n_k\cdot a_k\}$. Let the size of $S$ be $n = n_1+n_2+\cdots +n_k$. Then the number of permutations of $S$ equals

The proof is also simple, use multiplication principle to calculate the number of combination. There are $n$ place in the given multiset $S$, and we want to put exactly one of the objects of $S$ in each of the places. We first decide which places are to be occupied by the $a_1$’s, then decide the places which are to be occupied by the $a_2$’s, and so on. We continue like this, and invoke the multiplication principle and find that the number of permutations of $S$ equals

r-combination of infinite multiset

If $S$ is a multiset, then an r-combination of $S$ is an unordered selection of $r$ of the objects of $S$. Thus, the result of the selection is itself a multiset, a sub-multiset of $S$ of size $r$.

Let $S$ be a multiset with objects of $k$ types, each with an infinite repetition number. Then the number of the r-combination of $S$ equals

The proof of this theorem is very interesting. Here we give a short proof by converting it into another equivalent problem.

Let the $k$ types of objects of $S$ be $a_1,a_2,\ldots,a_k$ so that

Any r-combination of $S$ is of the form $\{x_1\cdot a_1,x_2\cdot a_2,\ldots,x_k\cdot a_k\}$, where $x_1,x_2,\ldots,x_k$ are non-negative integers with $\sum x_i=r$. Conversely, every sequence $x_1,x_2,\ldots,x_k$ of non-negative integers with $\sum x_i=r$ corresponds to an r-combination of $S$. Thus, the number of r-combinations of $S$ equals the number of solutions of

where $x_i$ are nonnegative integers. Actually, this number of these solutions equals the number of permutations of the following multiset

of $r+k-1$ objects of two different types. Given a permutation of $T$, the $k-1$ *’s divide the $r$ 1’s into $k$ groups as the following sequence

Thus, the number of r-combinations of the multiset $S$ equals the number of permutations of $T$, which is

The Binomial Coefficients

This subsection mainly talk about some fascinating properties of binomial coefficient. Actually, the binomial coefficient $\binom{n}{k}$ is the number of combination, which count the number of k-subsets of a set of $n$ element. Because of their appearance in the binomial theorem, they are called the binomial coefficients.

The Binomial Theorem

Let $n$ be a positive integer. Then, for all $x$ and $y$,

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 $(x+y)^n$ can be written as the product

which has $n$ factors each equal to $x+y$. Since, for each factor we can choose either $x$ or $y$ in multiplying out $(x+y)^n$, there are $2^n$ terms that result, and each can be arranged in the form $x^{n-k}y^k$ for some $k\in[0,n]$. We obtain the term $x^{n-k}y^k$ by choosing $y$ in $k$ of the $n$ factors and $x$ in the remaining $n-k$ factors. Thus the number of times the term $x^{n-k}y^k$ occurs in the expanded product equals the number $\binom{n}{k}$ of k-subsets of the set of $n$ factors. (Q.E.D.)

The second proof is by induction on $n$. If $n=1$, the formula becomes

and this is clearly true. We now assume that the formula is true for a positive integer $n$ and prove that it is true when $n$ is replaced by $n+1$.

Replacing $k$ by $k-1$ in the last summation, we obtain

Hence we have

which, using Pascal’s formula, becomes

This is the binomial theorem with $n$ replaced by $n+1$. (Q.E.D.)

Newton's Binomial Theorem

The binomial theorem has a generalized form given by Isaac Newton.

Let $\alpha$ be a real number. Then, for all $x$ and $y$ with $% $,

where

If $\alpha$ 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 $s_0,s_1,\ldots,s_n$ is unimodal, provided that there is an integer $t$ with $0\leqslant t\leqslant n$, such that

The number $s_t$ is the largest number in the sequence. The integer $t$ is not necessarily unique because the largest number may occur in the sequence more than once.

Let $n$ be a positive integer. The sequence of binomial coefficients $\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$ is a unimodal sequence.

If $n$ is an even integer,

If $n$ 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 $k$ be an integer with $1 \leqslant k \leqslant n$. Then

Hence, the partial order of successive binomial coefficients is decided by $n-k+1$ and $k$.

Now, $% $ if and only if $% $. If $n$ is even, then, since $k$ is an integer, $% $ is equivalent to $k \leqslant n/2$. If $n$ is odd, then $% $ is equivalent to $k\leqslant (n-1)/2$. Hence, the binomial coefficients increase as indicated in the statement of the theorem. We now observe that $k=n-k+1$ if and only if $2k=n+1$. If $n$ is even, $2k\neq n+1$ for any $k$. If $n$ is odd, then $2k=n+1$, for $k=(n+1)/2$. Thus, for $n$ even, no two consecutive binomial coefficients in the sequence are equal. For $n$ 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.)

Combinatorial Identities

A number of interesting identities can be derived from what we have known.

1. $\dbinom{n}{0}+\dbinom{n}{1}+\cdots + \dbinom{n}{n}=2^n$

2. $\dbinom{n}{0}+\dbinom{n}{2}+\cdots = \dbinom{n}{1}+\dbinom{n}{3}+\cdots = 2^{n-1}$

3. $\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-\cdots+(-1)^n\dbinom{n}{n} = 0$

4. $1\dbinom{n}{1}+2\dbinom{n}{2}+\cdots +n\dbinom{n}{n} = n\cdot 2^{n-1}$

5. $\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}^2 = \dbinom{2n}{n}$

6. $\dbinom{n}{k}=\dbinom{n}{n-k}$

7. $\dbinom{n}{k}=\displaystyle\frac{n}{k}\dbinom{n-1}{k-1}$

8. $\dbinom{n}{k}=\displaystyle\frac{n}{n-k}\dbinom{n-1}{k}$

9. $\dbinom{n}{k} = \dfrac{n-k+1}{k}\dbinom{n}{k-1}$

10. $\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$

11. $\displaystyle\sum_{0\leqslant k\leqslant n}\dbinom{k}{m} = \dbinom{0}{m}+\dbinom{1}{m}+\cdots+\dbinom{n}{m}=\dbinom{n+1}{m+1}$

12. $\dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k}$

13. $\displaystyle\sum_{i=0}^{r}\dbinom{m}{i}\dbinom{n}{r-i}=\dbinom{m+n}{r}$

14. $\displaystyle\sum_{i=0}^{m}\dbinom{m}{i}\dbinom{n}{r+i}=\dbinom{m+n}{m+r}$

15. $\displaystyle\sum_{0\leqslant k\leqslant n}\dbinom{r+k}{k}=\dbinom{r+n+1}{n}$

The Multinomial Theorem

The binomial theorem gives a formula for $(x+y)^n$ for each positive integer $n$. It can be generalized to give a formula for the nth power of the sum of $t$ real numbers: $(x_1+x_2+\cdots+x_t)^n$. In the general formula, the role of the binomial coefficients is taken over by numbers called the multinomial coefficients,

Here, $n_i$ are nonnegative integers with $n_1+n_2+\cdots+n_t=n$.

Actually, the binomial coefficient can be written as multinomial form

Let $n$ be a positive integer. For all $x_1,x_2,\ldots,x_t$,

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.

Inclusion-Exclusion Principle

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 $A_1$ be the subset of objects of $S$ that have property $P_1$, and let $A_2$ be the subset of objects of $S$ that have property $P_2$. we have the following formula

The inclusion-exclusion principle can be extend to any number of properties. Let $P_1,P_2,\ldots,P_m$ be $m$ properties referring to the objects in $S$, and let

be the subset of objects of $S$ that have property $P_i$. The inclusion-exclusion principle states that the number of objects of the set $S$ that have none of the properties $P_1,P_2,\ldots,P_m$ is given by

where the first sum is over all 1-subsets $\{i\}$, the second sum is over all 2-subsets $\{i,j\}$, and so on.

Here is a short proof of inclusion-exclusion principle. The left side of the equation counts the number of objects of $S$ with none of these properties $P_i$. 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 $y$ with exactly $n\geqslant 1$ properties. The contribution of $y$ to $\vert S\vert$ is 1, its contribution to the second item $\sum\vert A_i\vert$ is $n$, its contribution to $\sum\vert A_i\cap A_j\vert$ is $\binom{n}{2}$, its contribution to $\sum \vert A_i \cap A_j \cap A_k\vert$ is $\binom{n}{3}$, and so on. Thus, the net contribution of $y$ 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 $S$ which have at least one of the properties $P_1,P_2,\ldots,P_m$ is given by

which can be derived from $\vert A_1 \cup A_2 \cup \cdots \cup A_m\vert = \vert S\vert - \vert \overline{A}_1\cap \overline{A}_2\cap \cdots \cap \overline{A}_m\vert$.

r-combination of finite multiset

Recalling that the number of r-combinations of a multiset with $k$ distinct objects, each with an infinite repetition number, equals $\binom{r+k-1}{r}$. Now we consider of the number of r-combinations of a multiset without any restrictions on its repetition numbers.

Suppose $T$ is a multiset and an object $x$ of $T$ of a certain type has a repetition number that is greater than $r$. The number of r-combinations of $T$ equals the number of r-combinations of the multiset obtained from $T$ by replacing the repetition number of $x$ by $r$. This is so because the number of times $x$ can be used in an r-combination of $T$ cannot exceed $r$.

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 $T = \{3\cdot a, 4\cdot b, 5\cdot c\}$.

We shall apply the inclusion-exclusion principle to the set $S$ of all lO-combinations of the multiset $T^*=\{\infty\cdot a. \infty\cdot b,\infty\cdot c\}$. Let $P_1$ be the property that a 10-combination of $T^*$ has more than 3 $a$’s. Let $P_2$ be the property that a 10-combination of $T^*$ has more than 4 $b$’s. Finally, Let $P_3$ be the property that a 10-combination of $T^*$ has more than 5 $c$’s. As usual, let $A_i$ be the correspond set of property $P_i$.

Then we can use the previous infinite version to find

Then the result can be obtained, it is $66 - (28 + 21 + 15) + (3+1+0) - 0=6$.

Derangements

We are given an n-element set $X$ in which each element has a specified location, and we are asked to find the number of permutations of the set $X$ in which no element is in its specified location. If we take $X$ to be $\{1,2,\ldots,n\}$, a derangement of $\{1,2,\ldots,n\}$ is a permutation $i_1i_2\ldots i_n$ such that $i_k \neq k$.

We denote by $D_n$ the number of derangements of $\{1,2,\ldots,n\}$. The inclusion–exclusion principle enables us to get a formula for the derangement numbers $D_n$. For $n\geqslant 1$,

Here we also give a proof. Let $S$ be the set of all $n!$ permutations of $\{1,2,\ldots,n\}$. for $j = 1,2,\ldots,n$, let $P_j$ be the property that, in a permutation, $j$ is in its natural position. Thus, the permutation $i_1i_2\ldots i_n$ has property $P_j$ provided $i_j=j$. Let $A_j$ denote the set of permutations of $\{1,2,\ldots,n\}$ with property $P_j$. Hence,

and we use the inclusion–exclusion principle to evaluate $D_n$.

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 $n$, we let $Q_n$ denote the number of permutations of $\{1,2,\ldots,n\}$ in which none of the patterns $12$, $23$, $\ldots$, $(n-1)n$ occurs. For $n \geqslant 1$

Here we give a proof.

Let $S$ be the set of all $n!$ permutations of $\{1,2,\ldots,n\}$. Let $P_j$ be the property that, in a permutation, the pattern $j(j+1)$ does occur, ($j = 1,2\ldots,n-1$). Thus, a permutation of $\{1,2,\ldots,n\}$ is counted in the number $Q_n$ if and only if it has none of the properties $P_1,P_2,\ldots,P_{n-1}$. Let $A_j$ denote the set of permutations of $\{1,2,\ldots,n\}$ that satisfy property $P_j$. Then

and we apply the inclusion-exclusion principle to evaluate $Q_n$.

It is clear that

Since, for each $k=1,2,\ldots,n-1$, there are $\binom{n-1}{k}$ k-subsets, applying the inclusion-exclusion principle we obtain the formula in the theorem.

Möbius Inversion

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.

Generating Functions

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 $x^n$ in $g(x)$ is the nth term $h_m$ 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 $g(x)$ itself, but concentrate on the coefficient sequence. For those series which cannot converge, we define formal power series. In formal power series, the $x$ is just a abstract symbol which does not has specific value.

We denote all formal power series on $\mathbb{R}$ as $\mathbb{R}[[x]]$. With addition and multiplication, it becomes an entire ring. Designating a sequence whose term at index n is an by $(a_n)_{n\in\mathbb{N}}$, 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 $\sum a_kx^k\in\mathbb{R}[[x]]$ as

which is called formal derivative of formal power series.

Now we will show 8 properties of generating functions. Consider two sequence $a_k$ and $b_k$.

[property 1.]

If

then

[property 2.]

If $b_k = a_{k+\ell}$, then

[property 3.]

If $b_k = \sum_{i=0}^{k} a_i$, then

[property 4.]

If $b_k = \sum_{i=0}^{k} a_i$, then

[property 5.]

if $b_k = ka_k$, then

[property 6.]

If $b_k = \frac{a_k}{k+1}$, then

[property 7.]

If $c_k = \alpha a_k + \beta b_k$, then

[property 8.]

If $c_k = a_k b_0 + a_{k-1}b_1 + \cdots + a_0 b_k$, then

Using these 8 properties, we can derive 9 important generating functions:

1. $G\{1\} = \dfrac{1}{1-x}$

2. $G\{a^k\} = \dfrac{1}{1-ax}$

3. $G\{k\} = \dfrac{x}{(1-x)^2}$

4. $G\{k(k+1)\} = \dfrac{2x}{(1-x)^3}$

5. $G\{k^2\}=\dfrac{x(1+x)}{(1-x)^3}$

6. $G\{k(k+1)(k+2\}=\dfrac{6x}{(1-x)^4}$

7. $G\bigg\{\dfrac{1}{k!}\bigg\} = e^x$

8. $G\bigg\{\dbinom{\alpha}{k}\bigg\} = (1+x)^\alpha$

9. $G\bigg\{\dbinom{n+k}{k}\bigg\}=\dfrac{1}{(1-x)^{n+1}}$

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 $k$ element from $S = \{a_1,a_2\,\ldots,a_n\}$, the times $a_i$ may occur is given by set $M_i\,(1\leqslant i\leqslant n)$, 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 $\dfrac{x^k}{k!}$ instead of $x^k$.

Consider of k-permutation of $\{\infty\cdot a_1,\infty \cdot a_2,\ldots,\infty\cdot a_n\}$. If the times $a_i$ may occur is given by set $M_i\,(1\leqslant i\leqslant n)$, the exponential generating function of the permutation sequence is