Notes on the counting techniques (basic and advanced) I learned in the course Discrete Math.
Basic counting principles
(Product Rule, Addition Rule, Division Rule)
The Pigeonhole Principle
Theorem. If there are k > 0 boxes and k + 1 or more objects, there is at least one box containing more than one object.
Theorem. If N objects are placed into k boxes, then there is at least one box containing at least objects.
Some applications
Corollary. A function f from a set with k+1 or more elements to a set with k elements is not injective.
Theorem. Every sequence of distinct real numbers contains a monotonic (increasing or decreasing) subsequence of length n+1.
Theorem. (Erdös-Szekeres Theorem). For given r, s they showed that any sequence of distinct real numbers with length at least (r − 1)(s − 1) + 1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s.
Proof:
Assign to each element of the sequence a pair of numbers where:
- indicates the length of the longest increasing subsequence ending at
- indicates the length of the longest decreasing subsequence ending at .
For some , if then (since we can extend the increasing subsequence ending at to ending at ). Similarly, if then . Basically, there does not exist any two indicies such that . (*)
We will prove by contradiction that there exist some such that or . Suppose that and for all . There are at most possible pairs, but there are numbers in the sequence. Hence there exist some two indicies such that , contradicting to what we have shown at (*). Hence, the theorem.
Theorem. In a simple undirected graph, there are at least 2 vertices having the same degree.
Bionomial Coefficients and Identities
Theorem. Let x and y be variables and n be a non-negative integer, then:
If we substitute in the expansion, we get the result that:
If we substitute in the expansion, we get the result that:
If we substitute in the expansion, we get the result that:
Pascal's identity
Theorem. (Pascal's Identity). Let n and k be positive number with , then:
One can construct what is called a Pascal triangle:
| n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | |||||||
| 1 | 1 | 1 | ||||||
| 2 | 1 | 2 | 1 | |||||
| 3 | 1 | 3 | 3 | 1 | ||||
| 4 | 1 | 4 | 6 | 4 | 1 | |||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | ||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | |
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |
Although we can use factorial-formula to calculate the combination, Pascal identity is rather more useful if we need to work with integers exclusively (avoid division).
Vandermonde's identity
Theorem. (Vandermonde's Identity). Let be non-negative integers and . Then:
This means the number of ways to choose r objects from the set one of m objects and the set two of n objects (all objects are distinct). We have two equivalent ways of counting:
- combine two sets together and calculate the combination. (LHS)
- choose k objects from the set two and then r-k objects from the set one, which can be done in ways. Moreover, k ranges from 0 to r, hence the sum. (RHS)
In a special case where , we have a nicer result:
This is called a central binomial coefficient. A closely related term is a Catalan number, which is
u
Another identity
Theorem. Let be two positive integers. Then:
| n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | |||||||
| 1 | 1 | 1 | ||||||
| 2 | 1 | 2 | 1 | |||||
| 3 | 1 | 3 | 3 | 1 | ||||
| 4 | 1 | 4 | 6 | 4 | 1 | |||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | ||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | |
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |
Generalized Permutations and Combinations
Theorem. The number of -permutations with repititon from the set of objects is .
Interpretation: Subsequently choose objects from the set of types of objects. There are choices
at each step. Using the product rule, the total number of ways to choose objects is .
Theorem. The number of -combinations with repitition from the set of objects is .
Interpretation:
Choose objects from the set of different types of objects but the order of choosing is not important. Basically we care about how many objects of each type we choose. It is equivalent to choosing the number of non-negative integer solutions to the equation
whereas is the number of objects of type that we should choose.
A more visual way to look at this problem is putting walls among objects to create groups of objects. The -th group contains objects.
For example, :
- The arrangement tells us that we should choose 1 object of type 1, 2 objects of type 2, and 2 objects of type 3.
- The arrangement tells us that we should choose 3 objects of type 1, 2 objects of type 2, and 0 object of type 3.
There are positions in an arrangement, and we need to choose positions among them to be the walls and the rest will be objects. Hence there are ways.
Permutations with identical objects
Theorem. The number of different permutations of objects, where there are objects of type , with ( is the total number of types) is:
Of course, .
Interpretation: Suppose that we have a string of length which contains different letters. The frequency of letter is denoted by . We are interested in the number of different anagrams. Assume that we "over-generated" anagrams, some of which may be duplicate and need to be removed. Note that, for each string, if we permute the positions of identical characters, we still get the same string. The number of ways to permute a string and still get the same string is . Using the division rule, we get the theorem above.
Distribute Objects into Boxes
Before we start, I want to introduce a few new terms.
A -partition of a set A is a collection of non-empty subsets of A. The number of -partition of a set of elements is denoted by . This value is called a Stirling number of the second kind. (The forumula will be discussed later.)
A -partition of a positive integer is an integer solution to the equation , where . The number of solutions is denoted by . (The closed formula is, however, not yet discovered.)
In the four following cases, the number of objects is and the number of boxes is .
Different objects and Different boxes
The boxes are numbered from 1 to n. The objects are numbered from 1 to k. Each object is assigned with a number from 1 to n, denoting the box into which this object will be put. An arrangement is the sequence . Count the number of arrangements.
| Condition | # |
|---|---|
| None | |
| Each box has 1 object (only if ) | |
| Each box has 1 object (only if ) | |
| Box contains objects |
Identical objects and Different boxes
The boxes are numbered from 1 to n. Each box is assigned with a number , denoting the number of objects put into the box. An arrangement is the sequence such that .
| Condition | # |
|---|---|
| None | |
| Each box has 1 object (only if ) | |
| Each box has 1 object (only if ) |
Different objects and Identical boxes
The objects are numbered from 1 to k. An arrangement is a -partition of the set ( depends on the condition).
| Condition | # |
|---|---|
| None | |
| Each box has 1 object (only if ) | |
| Each box has 1 object (only if ) |
Identical objects and Identical boxes
An arrangement is a -partition of ( depends on the condition).
| Condition | # |
|---|---|
| None | |
| Each box has 1 object (only if ) | |
| Each box has 1 object (only if ) |
Ordinary Generating Function of a Sequence
A sequence of numbers can be represented as a formal power series
This series is called a generating function. The sequence can have infinitely or finitely many terms. A formal power series is very much like a polynomial, except that a series can have infinitely many terms, while a polynomial cannot; and a formal series means that the convergence of this series can be completely ignored. We can look at as a placeholder / a bookkeeping device, we generally do not care about what value it may be, we are only interested in the coefficients.
Let's begin with a simple sequence, . What is the generating function for this sequence? Let's first call it . Straightforward from the definition, we have:
However, we can try to find a "closed form" of A(x). Notice that:
which implies that . However, shortening a generating function like this is only valid when converges to some value, in this case, when . As I said above, we generally do not care about the convergence, but in some occasions it is important to consider at which values of that the series converges.
Sometimes, we are given a generating function and we need to find the terms of the sequence. For example, we are given . In this case, we can apply the Taylor's series expansion of a function. Recall that a Taylor's series expansion of a function around the neighborhood of is:
It is somewhat a notion / a convention to use (a Taylor's series at is also known as a Maclaurin's series), because it is easier to evaluate the coefficients.
Some calculating rules
There are some basic techniques to work with generating functions. Let and be the generating function for and , respectively. We have the following rules:
- Addition rule:
- Scaling rule:
- Right-shifting rule:
- Derivative rule:
Convolution rule
This deserves its own section. Let be a sequence where . The generating function for will be .
Other interpretation of the convolution rule is: If is the generating function for selecting items from set A and is the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from is .
Combination with repitition
One classic example is to find the generating function of the combination with repitition, i.e. select a objects from types of objects. Let be a sequence where . What is the generating function for ? We approach this problem as follows:
How many ways to select objects from only type ? Obviously: one, i.e. choose objects of type . The generating function for this selection is .
Since the sets of types are disjoint (there are sets in total), we can use the convolution rule to answer the question: "How many ways to select objects from types ?". The answer is:
which essentially counts the number of non-negative solutions of the equation , precisely what we are looking for.
Generating functions of some popular sequences
| Generating Function | Sequence |
|---|---|
otherwise | |
or | |
Exchanging money
How many ways to draw dollars using the `$1, $
2, \$5 tokens?The order of the tokens are not important
Each draw is a natural solution $
(x_1, x_2, x_3)$ to the equation $x_1 + 2x_2 + 5x_3 = n$.It is close to the combination with repetition. We choose $
n$ objects from three types of objects, but the condition is that:- The number of the first-type objects is arbitrary.
- The number of the second-type objects is divisible by 2.
- The number of the third-type objects is divisible by 5.
Using the convolution rule, the generating function for drawing $
n$ dollars using the $1, \$2, $`5 tokens are:The order of the tokens are important
We add an extra parameter to the problem. Let's denote the number of tokens used. Each draw is a natural solution to the equation where each is either 1, 2, or 5.
We use the convolution rule times. Observe that the generating function for drawing dollars using only one token is , it means you can only draw when is equal to 1, 2, or 5, and in such cases there is only one way. If you can choose tokens, the generating function is , i.e. the number of ways to draw dollars is the coefficient of .
However, the original problem permits any amount of tokens, so the number of ways to draw dollars is the coefficient of in:
Ultimately, the coefficient of in this case is also , very similar to the result of the case where the order is ignored, but the constructions of the generating functions are very much different and hence the results are also different.
Partition of a number
Recall: A -partition of a positive integer is an integer solution to the equation , where . The number of solutions is denoted by .
What is the generating function for the sequence and ? (Assume that ) In other words, find the generating function for the number of partitions of .
The only thing that matters in each partition is how many number 1 are used, how many number 2 are used, etc. Each partition is a natural solution to the equation . It's very similar to the exchanging money problem, which would yield:
Since we are allowed to use infinitely many types of tokens, i.e. , the number of ways to partition into positive integers is the coefficient of in:
Solving Recurrence Relations
Using Generating Function
Generating function is a tool to find the closed formula of a sequence whose recursive formula is known. We take the Fibonacci sequence as an example:
We first need to find the generating function, then the Maclaurin's series expansion, and finally the closed formula of the coefficients.
Denote the generating function by .
Hence:
We then decompose into partial fractions:
We can easily find the roots of the denominator , which are and . and are the inverses of the roots, hence:
Further more, the numerator. We solve the following system:
We have and .
The closed formula of will be therefore:
Using Characteristic Equation
Homogeneous
Suppose we have a homogeneous recurrence relation:
The characteristic equation is defined to be:
If the equation has distinct roots , then the closed form of is:
where are constants. They can be found by substituting some known values of and solving the system of equation.
If the equation has distinct roots with multiplicity , respectively, then the closed form of is:
where denotes a polynomial of with constant coefficients and its degree is less than , i.e.
Again, the coefficients can be found by substituting some known values of and solving the system of equation.
Non-homogeneous
Suppose we have a non-homogeneous recurrence relation:
where
Suppose that is a polynomial of of degree and is a constant (for ).
The characteristic equation is defined to be:
We solve this equation to obtain the roots. Depends on whether the roots are distinct or not, we apply the same techniques as above to find the closed formula.
The Characteristic Equation method can be shown to be derived from the Generating Function method, which I believe more intuitive.