Combinatorics

1 Permutations and Combinations

Partition: A partition of a set S is a collection of non-empty subsets of S such that every

element of S is included in exactly one of these subsets. In other words, a partition divides the
set S into disjoint subsets whose union is S.

S = S1 ∪ S2 ∪ .... ∪ Sn such that: Si ∩ Sj = ∅

Addition Principle: Suppose a set S is partitioned into pairwise disjoint parts S1 , S2 , . . . , Sm .

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:

|S| = |S1 | + |S2 | + . . . + |Sm |

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 given by: |S| = p × q

This principle can be generalized to any finite number of sets. For example, if there are n
tasks to perform, where the first task has p1 outcomes, the second task has p2 outcomes, and
so on, then the total number of outcomes is: p1 × p2 × . . . × pn

Subtraction Principle: Let A be a set and U a larger set containing A. The complement of
A in U is the set Ac consisting of all objects in U that are not in A. The number of objects in
A is given by: |A| = |U | − |Ac |

This principle is useful when it is easier to count the number of objects in U and in Ac than to
count the number of objects in A.

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:

|S|
k=
number of objects in each part
This principle is often applied in problems where objects are grouped equally, such as dis-
tributing items into bins or assigning tasks to workers.

Permutations: An r-permutation of a set S of n elements is an ordered arrangement of r

elements from S.

Linear Permutations: Linear permutations refer to the arrangements of elements in a se-

quence or line.

Number of Linear Permutations: The number of linear r−permutations of a set con-

taining n elements is given by: P (n, r) = n × (n − 1) × · · · × (n − r + 1)

Corollary: The numeber of ways to arrange n objects amoungst themselves is given by n!.

Circular Permutations: Circular permutations are arrangements of elements in a circle where

rotations of the same arrangement are considered identical.

1
Number of Circular Permutations: The number of circular r−permutations of a set con-
taining n elements is given by:

P (n, r) n!
=
r r · (n − r)!
Combinations: Let S be a set of n elements. A combination of a set S is an unordered
selection of the elements of S.
 
n
We denote by or C(n, r) the number of r-subsets of an n-element set.
r
 
n P (n, r) n!
Theorem: For 0 ≤ r ≤ n, = C(n, r) = =
r r! r!(n − r)!
Corollary: C(n, r) = C(n, n − r)

Pascals Formula: For all integers n and k with 1 ≤ k ≤ n − 1:

     
n n−1 n−1
= +
k k k−1

Theorem: For n ≥ 0, the number of subsets of an n-element set equals:

n  
X n
= 2n
r
r=0

Multiset: A multiset is a collection of objects that are not necessarily distinct.

Permutations of Multisets: If S is a multiset, an r-permutation of S is an ordered ar-

rangement of r of the objects of S.

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

Theorem: Let S be a multiset with objects of k different types with finite repetition numbers
n1 , n2 , . . . , nk , respectively. Let the size of S be n = n1 + n2 + . . . + nk . Then the number of
permutations of S equals:

n!
n1 ! n2 ! · · · nk !

Theorem: Let n be a positive integer and let n1 , n2 , . . . , nk be positive integers with n =

n1 + n2 + . . . + nk . The number of ways to partition a set of n objects into k labeled boxes
in which Box 1 contains n1 objects, Box 2 contains n2 objects, . . . , Box k contains nk objects
equals:

n!
x=
n1 ! n2 ! · · · nk !

n!
If the boxes are not labeled and ni = nj for i ̸= j, then: x =
k!n1 ! n2 ! · · · nk !

2
Theorem: There are n rooks of k colors with n1 rooks of the first color, n2 rooks of the
second color, . . . , and nk rooks of the kth color. The number of ways to arrange these rooks on
an n-by-n board so that no rook can attack another equals:

n!
n1 ! n2 ! · · · nk !

Combinations of Multisets: If S is a multiset, then an r-combination of S is an unordered

selection of r of the objects of S.

Theorem: Let S be a multiset with objects of k types, each with an infinite repetition number.
Then the number of r-combinations of S equals:
   
r+k−1 r+k−1
=
r k−1

Stars and Bars Theorem: Suppose you have m indistinguishable objects and want to dis-
tribute them into n distinguishable bins. The number of ways to do this is given by the binomial
coefficient:
 
m+n−1
a=
n−1
where a is the number of ways to place m indistinguishable objects into n distinct bins, with
each bin possibly containing zero or more objects.

Corollary: The number of solutions of x1 + x2 + ... + xk = n for xi ∈ W is: k+n−1 C

n−1

Corollary: The number of solutions of x1 + x2 + ... + xk = n for xi ∈ N is: n−1 C

k−1

Finite Probability: In finite probability, we deal with experiments that result in one of a
finite set of outcomes. Each outcome is assumed to be equally likely, meaning no outcome is
more probable than any other. The set of all possible outcomes is called the sample space of
the experiment and is denoted by S. If the sample space has n elements, S = {s1 , s2 , . . . , sn },
the probability of each outcome si is given by:
1
Prob(si ) = for i = 1, 2, . . . , n
n
Events: An event is a subset E of the sample space S, usually described in terms of the
outcomes it includes rather than explicitly listing all outcomes.

Theorem: The probability of an event E in an experiment with a sample space S is de-

fined as the proportion of outcomes in S that belong to E:

|E|
Prob(E) =
|S|
where |E| is the number of outcomes in the event E and |S| is the number of outcomes in
the sample space S.

3
2 Pigeonhole Principle
Pigeonhole Principle (Simple Form): If n + 1 objects are distributed into n boxes, then at
least one box contains two or more of the objects.

Additional Principles:

1. If n objects are put into n boxes and no box is empty, then each box contains exactly one
object.

2. If n objects are put into n boxes and no box gets more than one object, then each box
has an object in it.

Abstract Formulations:

Let X and Y be finite sets and let f : X → Y be a function from X to Y .

1. If X has more elements than Y , then f is not one-to-one.

2. If X and Y have the same number of elements and f is onto, then f is one-to-one.

3. If X and Y have the same number of elements and f is one-to-one, then f is onto.

Applications of the Pigeonhole Principle:

1. Birthdays: Among 13 people, at least two people will have their birthdays in the same
month. This follows directly from the pigeonhole principle because there are only 12
months and 13 people.

2. Married Couples: There are n married couples. To ensure that at least one married
couple is selected, n + 1 people must be chosen. If we think of each couple as a ”box”
and each selected person as an ”object,” the pigeonhole principle guarantees that one of
the ”boxes” (couples) will contain two ”objects” (people), meaning at least one married
couple is selected.

3. Integers: Given m integers a1 , a2 , . . . , am , there exist integers k and l with 0 ≤ k < l ≤ m

such that ak+1 + ak+2 + . . . + al is divisible by m.

4. Chess Master: A chess master has 11 weeks to prepare for a tournament, playing at
least one game each day but no more than 12 games in any calendar week. There exists a
succession of consecutive days during which the chess master will have played exactly 21
games.

5. Handshakes: In a party of n people, if each person shakes hands with at least one other
person, then there is at least one pair of people who have shaken hands with the same
number of people.

6. Socks: If you have 10 pairs of socks, and you randomly pull out 11 socks, you are
guaranteed to have at least one matching pair.

PHP (Strong Form): Let q1 , q2 , . . . , qn be positive integers. If q1 + q2 + · · · + qn − n + 1 objects

are distributed into n boxes, then either the first box contains at least q1 objects, or the second
box contains at least q2 objects, . . . , or the nth box contains at least qn objects.

4
Corollary: Let n and r be positive integers. If n(r − 1) + 1 objects are distributed into n
boxes, then at least one of the boxes contains r or more of the objects.

Averaging Principle: If the average of n nonnegative integers m1 , m2 , . . . , mn is greater

than r − 1, that is,
m1 + m2 + · · · + mn
> r − 1,
n
then at least one of the integers is greater than or equal to r.

Application 7: A basket of fruit is being arranged out of apples, bananas, and oranges.
What is the smallest number of pieces of fruit that should be put in the basket to guarantee
that either there are at least eight apples, or at least six bananas, or at least nine oranges?

Application 8: Two disks, one smaller than the other, are each divided into 200 congru-
ent sectors. In the larger disk, 100 of the sectors are chosen arbitrarily and painted red; the
other 100 sectors are painted blue. In the smaller disk, each sector is painted either red or blue
with no stipulation on the number of red and blue sectors. The small disk is then placed on
the larger disk so that their centers coincide. Show that it is possible to align the two disks so
that the number of sectors of the small disk whose color matches the corresponding sector of
the large disk is at least 100.

Application 9: From the integers 1, 2, . . . , 200, we choose 101 integers. Show that, among
the integers chosen, there are two such that one of them is divisible by the other.

Graphs: A graph G (also called a simple graph) is composed of two types of objects. It
has a finite set V of elements called vertices (sometimes also called nodes) and a set E of pairs
of distinct vertices called edges.

We denote the graph whose vertex set is V and whose edge set is E by G = (V, E).

The number n of vertices in the set V is called the order of the graph G. If a = {x, y} = {y, x}
is an edge of G, then we say that a joins x and y, and that x and y are adjacent; we also say
that x and a are incident, and y and a are incident. We also call x and y the vertices of the edge a.

Complete Graph: A graph of order n is called complete, provided that each pair of dis-
tinct vertices forms an edge. Thus, in a complete graph, each vertex is adjacent to every other
vertex. A complete graph of order n has (n(n − 1)/2) edges and is denoted Kn .

Edge Colouring: Edge coloring of a graph is an assignment of colors to the edges of the
graph such that no two adjacent edges share the same color.

Notation of Ramsey’s Theorem: The notation Kn → (Kr , Ks ) means that any two-coloring
of the edges of Kn will contain either a monochromatic Kr subgraph in the first color or a
monochromatic Ks subgraph in the second color.

Ramsey’s Theorem for Pairs: For any positive integers r and s, there exists a minimum
integer R(r, s) such that any complete graph KR(r,s) whose edges are colored with two colors
contains a monochromatic complete subgraph Kr in one color or a monochromatic complete
subgraph Ks in the other color.

5
3 Generating Permutations and Combinations
√  n n
Stirling’s Formula: n! ≈ 2πn
e
Johnson-Trotter Algorithm (Generating Permutations by Adjacent Transpositions):

Given an integer k, we first assign a direction to it by writing an arrow on top of it point-

ing to the left or right. Then the algorithm is as follows:

1. Start with the first permutation 1, 2, . . . , n.

2. Identify the largest mobile integer, which is an integer whose arrow points towards a
smaller adjacent integer.

3. Swap this mobile integer with the adjacent integer in the direction of its arrow.

4. Reverse the directions of the arrows of all integers greater than the largest mobile integer.

5. Repeat until no mobile integers exist, indicating all permutations have been generated.

Recursive Algorithm for Generating Permutations:

1. Start with the unique permutation of {1}.

2. For k = 2 to n:

(a) Generate the permutations of {1, 2, . . . , k − 1}.

(b) Insert k into every possible position in each permutation of {1, 2, . . . , k−1} to generate
the permutations of {1, 2, . . . , k}.

3. Repeat until the permutations of {1, 2, . . . , n} are obtained.

Inversion: An inversion in a permutation is defined as a pair of elements in which the order

of the elements in the permutation is opposite to their natural order. More formally, given a
permutation σ = (σ1 , σ2 , . . . , σn ) of the set {1, 2, . . . , n}, an inversion is a pair of indices (i, j)
such that i < j but σi > σj .

Inversions measure how far a permutation is from being sorted. If there are no inversions,
the permutation is in increasing order. The total number of inversions in a permutation is an
important characteristic used in sorting and combinatorial algorithms.

Inversion Sequence: An inversion sequence is a sequence of non-negative integers that

uniquely represents the number of inversions for each element in a permutation. Given a per-
mutation σ = (σ1 , σ2 , . . . , σn ) of the set {1, 2, . . . , n}, the inversion sequence I = (i1 , i2 , . . . , in )
is constructed such that each ik (for 1 ≤ k ≤ n) represents the number of elements greater than
σk that appear before σk in the permutation. Formally, for each k, the value ik is the number
of indices j such that j < k and σj > σk .

Theorem 4.2.1: Let b1 , b2 , . . . , bn be a sequence of integers satisfying:

0 ≤ b1 ≤ n − 1, 0 ≤ b2 ≤ n − 2, . . . , 0 ≤ bn−1 ≤ 1, bn = 0.

Then, there exists a unique permutation of {1, 2, . . . , n} whose inversion sequence is b1 , b2 , . . . , bn .

6
This theorem establishes that for any valid inversion sequence, there corresponds a unique
permutation of the set {1, 2, . . . , n}.

Algorithm I: Construction of a Permutation from its Inversion Sequence

• Write down the largest number, n.

• Consider bn−1 . If bn−1 = 0, place n − 1 before n. If bn−1 = 1, place n − 1 after n.

• Consider bn−2 . If bn−2 = 0, place n − 2 before the two numbers already written. If
bn−2 = 1, place n − 2 between the two numbers. If bn−2 = 2, place n − 2 after the two
numbers.

• Continue in this manner for each bn−k until b1 . For b1 , place 1 after the b1 -th number in
the sequence constructed in the previous step.

By following these steps, we determine the unique permutation corresponding to the inversion
sequence b1 , b2 , . . . , bn .

Algorithm II: Construction of a Permutation from its Inversion Sequence

• Begin with n empty positions labeled 1, 2, . . . , n.

• Since there are b1 integers preceding 1 in the permutation, place 1 in location b1 + 1.

• For k = 2, 3, . . . , n: Since there are bk integers preceding k in the permutation and these
integers have not yet been inserted, leave bk empty positions. Place k in the (bk + 1)-th
empty position from the left.

• Continue this process until n is placed in the last remaining position.

This algorithm ensures that the positions of all numbers in the permutation are determined
sequentially as each step is carried out.

Algorithm to Generate all Combinations: The base 2 algorithm for generating the
subsets of a set {xn−1 , xn−2 , . . . , x0 } works by using binary representations to correspond to
subsets of the set. Each subset can be associated with an n-bit binary number, where each bit
indicates whether a particular element is included in the subset.

Steps of the Base 2 Algorithm:

1. Start with the binary number 0: This corresponds to the empty subset, meaning no
elements are included in the subset.

2. Interpret the binary digits: Each binary digit (bit) corresponds to one element of the
set. If the bit is 1, the corresponding element is included in the subset. If the bit is 0, the
corresponding element is excluded.

3. Generate all binary numbers from 0 to 2n − 1: There are 2n possible subsets of a

set with n elements, corresponding to the binary numbers from 0 to 2n − 1. The binary
representation of each number gives a unique subset.

4. For each number i, translate the binary representation to a subset: The k-

th bit (from right to left) corresponds to the element xk . If the k-th bit of the binary
representation of i is 1, include xk in the subset. Otherwise, exclude xk .

7
Lexicographic Ordering of Subsets: In lexicographic ordering, the subsets of a set are
listed in the same way words are ordered in a dictionary. In this method, smaller elements come
first, and subsets are ordered primarily by size and secondarily by the order of elements within
each subset. The lexicographic order compares elements of each subset from left to right and
arranges them based on the first place where they differ, just like in the alphabetical order of
words.

Squashed Ordering of Subsets: In squashed ordering, subsets are ordered based on their
binary representations, as described in the base 2 algorithm. The binary string corresponding
to each subset is treated as a number, and subsets are ordered in increasing numerical order
of the corresponding binary numbers. Each subset corresponds to a binary number where each
bit indicates whether a specific element is included (1) or excluded (0).

Gray Code Order: Reflected Gray Code Order is a way of listing all binary strings (and
corresponding subsets) such that consecutive strings differ in exactly one bit. This method
generates an ordering where each subsequent subset differs from the previous subset by the ad-
dition or removal of a single element. The Gray code is often referred to as a ”minimal-change”
listing because only one bit changes from one binary string to the next.

Algorithm for Generating the n-tuples of 0s and 1s in the Reflected Gray Code
Order:

Begin with the n-tuple an−1 an−2 ....a0 = 00....0. While the n-tuple ̸= 10....0, do the follow-
ing:

1. Compute σ(an−1 ...a0 ) = an−1 + an−2 + ... + a0

2. If σ(an−1 ...a0 ) is even, change a0 (from 0 to 1 or from 1 to 0).

3. Else, determine j such that aj = 1 and ai = 0 for all i with j > i and then change aj+1
(from 0 to 1 or 1 to 0)

Theorem: The preceding algorithm for generating n-tuples of 0s and 1s produces the reflected
gray code of order n for each positive integer n.

Theorem: Let a1 a2 . . . ar be an r-subset of {1, 2, . . . , n}. The first r-subset in the lexicographic
ordering is 12 . . . r, and the last r-subset in the lexicographic ordering is (n−r+1)(n−r+2) . . . n.
Assume that a1 a2 . . . ar ̸= (n − r + 1)(n − r + 2) . . . n. Let k be the largest integer such that
ak < n and ak + 1 is different from each of ak+1 , . . . , ar .

Then, the r-subset that is the immediate successor of a1 a2 . . . ar in the lexicographic ordering is:

a1 a2 . . . ak−1 (ak + 1)(ak + 2) . . . (ar + 1).

The Algorithm for Generating r-subsets of 1, 2, ..., n in Lexicographic Order:

Begin with the r-subset a1 a2 ....ar = 123....r. While a1 a2 . . . ar ̸= (n − r + 1)(n − r + 2) . . . n, do

the following:

1. Determine the largest integer k such that ak + 1 ≤ n and ak + 1 is not one of a1 , a2 , . . . , ar .

2. Replace a1 a2 . . . ar with the r-subset a1 a2 . . . ak−1 (ak + 1)(ak + 2) . . . ar .

8
Theorem: The r-subset a1 a2 . . . ar of {1, 2, . . . , n} occurs in place number
       
n n − a1 n − a2 n − ar
− − − ··· −
r r r−1 1
in the lexicographic order of the r-subsets of {1, 2, . . . , n}.

Partial Orders and Relations:

A partial order on a set X is a relation R on X that is:

1. Reflexive: xRx for all x ∈ X.

2. Antisymmetric: xRy and yRx imply x = y.

3. Transitive: xRy and yRz imply xRz.

A strict partial order is a relation that is:
1. Irreflexive: x ̸ Rx for all x ∈ X.

2. Antisymmetric.

3. Transitive.
For example, the relations ⊆ (subset) and divisibility are partial orders, while the relations ⊂
(proper subset) and < (less than) are strict partial orders.

Special Properties of Relations:

1. Reflexive: xRx for all x ∈ X.

2. Irreflexive: x ̸ Rx for all x ∈ X.

3. Symmetric: If xRy, then yRx.

4. Antisymmetric: xRy and yRx imply x = y.

5. Transitive: If xRy and yRz, then xRz.

A partially ordered set (poset) is a set X together with a partial order ≤ on X. If R is a
partial order, the usual inequality symbol ≤ is often used instead of R.

Theorem: Let X be a finite set with n elements. Then there is a one-to-one correspon-
dence between the total orders on X and the permutations of X. In particular, the number of
different total orders on X is n!.

Theorem: Let (X, ≤) be a finite partially ordered set. Then there is a linear extension of
(X, ≤).

Algorithm for a Linear Extension of a Partially Ordered Set:

1. Choose a minimal element x1 of X (with respect to the partial order ≤).

2. Delete x1 from X and choose a minimal element x2 from among the remaining n − 1
elements.

3. Delete x2 from X and choose a minimal element x3 from among the remaining n − 2
elements.

9
 4. Continue this process until you have chosen all elements x1 , x2 , . . . , xn .

Definition of Equivalence Relations:

Equivalence Relations: A relation ∼ on a set X is called an equivalence relation if it satisfies

the following three properties:

1. Reflexive: For all x ∈ X, x ∼ x.

2. Symmetric: For all x, y ∈ X, if x ∼ y, then y ∼ x.

3. Transitive: For all x, y, z ∈ X, if x ∼ y and y ∼ z, then x ∼ z.

Equivalence Classes: An equivalence relation partitions the set X into disjoint, nonempty
subsets called equivalence classes, where each element of X belongs to exactly one equivalence
class.

Theorem: Let ∼ be an equivalence relation on a set X. Then the distinct equivalence classes
partition X into nonempty parts. Conversely, given any partition of X into nonempty parts,
there is an equivalence relation on X whose equivalence classes are the parts of the partition.

4 The Binomial Coefficients

The Pascal’s Triangle: Pascal’s triangle is an infinite array of binomial coefficients arranged
in a triangular structure. It is constructed using Pascal’s formula, which is given by:
     
n n−1 n−1
= +
k k k−1
where 0 ≤ k ≤ n. The boundary values of the triangle are always 1. The other entries of
Pascal’s triangle are obtained by summing the two entries directly above it.

The first few rows are:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Binomial Theorem: Let n be a positive integer. Then, for all real numbers x and y,
n  
X n n−k k
(x + y)n = x y .
k
k=0

Theorem: Let n be a positive integer. Then, for all x,

     
n n n n−1 n n−2 n
(x + 1) = x + x + x + ··· + x + 1.
1 2 n−1
       
n n n n−1 n n−2 n n
(x − 1)n = x − x + x − · · · + (−1)
0 1 2 n

10
Identities Related to the Binomial Coefficients:
   
n n−1
• k =n n, k ∈ Z +
k k−1
[n/2]   [n/2]+1  
X n X n
• = = 2n−1
2k 2k − 1
k=0 k=1
n  
X n
• k = n2n−1
k
k=0
n  2  
X n 2n
• =
k n
k=0

k    
X r+t r+k+1
• =
t k
t=0

Unimodality: A sequence of numbers is said to be unimodal if it increases to a maximum

value and then decreases, having only one peak point.

Theorem: Let n be a positive integer. The sequence of binomial coefficients is a unimodal

sequence.
   
n n
Corollary: The largest of the binomial coefficients in (x + y)n is: =
⌊n/2⌋ ⌈n/2⌉
Antichain: An antichain in a partially ordered set is a collection of elements such that no
element in the collection is comparable to any other element in that collection. In simpler
terms, if you have an antichain of sets, it means that for any two sets in the antichain, one set is
not a subset of the other. Thus, none of the elements in the antichain are related by the partial
order.

Sperner’s Theorem: Let S be a set of n elements. The largest antichain of S, which is a col-
lection of subsets of S with no subset being contained in another, contains at most C{n, ⌊n/2⌋}
subsets.

The Multinomial Theorem: Let n be a positive integer. For all x1 , x2 , . . . , xt ,

X n!
(x1 + x2 + · · · + xt )n = xn1 1 xn2 2 · · · xnt t ,
n1 +n2 +···+nt
n !n
=n 1 2
! . . . n t !

where the summation extends over all nonnegative integral solutions n1 , n2 , . . . , nt of n1 +

n2 + · · · + nt = n.

Newton’s Binomial Theorem: Let a be a real number. Then, for all x and y with |x| < |y|,
∞    
X a k a−k a a(a − 1) · · · (a − k + 1)
(x + y)a = x y ; where =
k k k!
k=0

11
5 Recurrence Relations and Generating Functions

Sequences: A sequence is a list of numbers arranged in a specific order, typically following a

rule. Each number in a sequence is called a term.

Arithmetic Sequence: An arithmetic sequence is a sequence of numbers in which the dif-

ference between consecutive terms is constant. This constant difference is referred to as the
common difference.

General Formula: hn = h1 + (n − 1) · d

• hn is the n-th term of the sequence,

• h1 is the first term,

• d is the common difference.

Partial Sum: The partial sum of a sequence is the sum of the first n terms of the sequence.
This concept is particularly important in series and summation.
n
Partial Sum of an Arithmetic Sequence: Sn = · (2h1 + (n − 1) · d)
2
• Sn is the sum of the first n terms,

• h1 is the first term,

• d is the common difference.

Geometric Sequence: A geometric sequence is a sequence of numbers in which each term

after the first is obtained by multiplying the previous term by a fixed, non-zero number called
the common ratio.

General Formula: hn = h1 · rn−1

• hn is the n-th term of the sequence,

• h1 is the first term,

• r is the common ratio.

1−rn
Partial Sum of a Geometric Sequence: Sn = h1 · 1−r

• Sn is the sum of the first n terms,

• h1 is the first term,

• r is the common ratio, and r ̸= 1.

The Fibonacci Sequence: The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2 , for n ≥ 2 where F0 = 0, F1 = 1

√ !n √ !n
1 1+ 5 1 1− 5
Theorem: The n’th fibonacci number satisfies: fn = √ −√
5 2 5 2

12
Theorem: The sums of the binomial coefficients along the diagonals of Pascal’s triangle run-
ning upward from the left are Fibonacci numbers. More precisely, the n-th Fibonacci number
Fn satisfies:
⌊(n−1)/2⌋  
X n−1−k
Fn =
k
k=0

Generating Functions: The generating function of the sequence h0 , ..., hn , ... is given by:

g(x) = h0 + h1 x + h2 x2 + ... + hn xn + ...

The coefficient of xk is the (k + 1)’th term of {hn }. xk acts as a placeholder for hk in the
context of generating functions.

Theorem: Let n be a positive integer. Then:

(1 − x)(1 − x2 )(1 − x3 )...(1 − xn )

gn (x) = (1 + x)(1 + x + x2 )...(1 + x + x2 + · · · + xn−1 ) =
(1 − x)n
Exponential Generatig Functions: Given a sequence {an }, the exponential generating func-
tion E(x) for this sequence is defined as:
∞
X an xn
E(x) =
n!
n=0
Exponential generating functions are particularly powerful in combinatorial analysis where the
order or labeling of elements plays a crucial role. They are used to solve problems involving
permutations, counting labeled objects, and other combinatorial structures that require consid-
eration of factorial growth in the sequence terms.

Theorem: Let S be the multiset {n1 · a1 , n2 · a2 , . . . , nk · ak }, where n1 , n2 , . . . , nk are nonneg-

ative integers. Let hn be the number of n-permutations of S. Then the exponential generating
function g (e) (x) for the sequence h0 , h1 , h2 , . . . , hn , . . . is given by:
k
Y
g (e) (x) = fni (x)
i=1
x2 xni
where, for i = 1, 2, . . . , k, fni (x) = 1 + x + + ... +
2! ni !
Recurrence Relations: A recurrence relation is an equation that defines a sequence of values,
where each term of the sequence is expressed as a function of the preceding terms. Formally, a
recurrence relation for a sequence {an } can be written as:

an = f (an−1 , an−2 , . . . , an−k )

where f is some function, and k is the number of preceding terms that an depends on.

Linear Recurrence Relations: A linear recurrence relation of order k is a relation satisfied

by a sequence {hn } such that:hn = a1 hn−1 + a2 hn−2 + · · · + ak hn−k + bn , where a1 , a2 , . . . , ak
and bn may depend on n, and ak ̸= 0. If bn = 0 for all n, then the recurrence relation is called
homogeneous. The order of the recurrence relation is determined by the number of preceding
terms used to determine hn .

13
Characteristic Equation: The characteristic equation of a linear recurrence relation is a
polynomial equation derived from the recurrence relation that helps find the general solution of
the sequence.

Theorem: Let q be a nonzero number. Then hn = q n is a solution of the linear homoge-

neous recurrence relation

hn = a1 hn−1 + a2 hn−2 + · · · + ak hn−k

with constant coefficients if and only if q is a root of the polynomial equation

q k − a1 q k−1 − a2 q k−2 − · · · − ak = 0

If the polynomial equation has k distinct roots q1 , q2 , . . . , qk , then

hn = c1 q1n + c2 q2n + · · · + ck qkn

is the general solution of the recurrence relation, where c1 , c2 , . . . , ck are constants determined
by initial conditions.

Theorem: Let q1 , q2 , . . . , qt be the distinct roots of the following characteristic equation of

the linear homogeneous recurrence relation with constant coefficients:

hn = a1 hn−1 + a2 hn−2 + · · · + ak hn−k

If qi is a root of multiplicity si of the characteristic equation, the part of the general solu-
tion of this recurrence relation corresponding to qi is:
(i)
Hn = (C1 + C2 n + · · · + Csi nsi −1 )qin

The general solution of the recurrence relation is a sum of these parts for all distinct roots:
(1) (2) (3) (t)
hn = Hn + Hn + Hn + ... + Hn

Theorem: Let {hn } be a sequence of numbers that satisfies the linear homogeneous recur-
rence relation of order k with constant coefficients:

hn = a1 hn−1 + a2 hn−2 + · · · + ak hn−k

Then its generating function g(x) is of the form: g(x) = p(x)/q(x)

where q(x) is a polynomial of degree k with a nonzero constant term and p(x) is a polynomial
of degree less than k. Conversely, given such polynomials p(x) and q(x), there is a sequence
{hn } satisfying a linear homogeneous recurrence relation with constant coefficients of order k
whose generating function is given by the same form.

Solving Non-homogeneous Recurrence Relations: The technique to solve non-homogeneous

recurrence relations can be summarized as the following:

1. Solve the Homogeneous Part: Begin by solving the associated homogeneous recur-
rence relation. This involves finding the characteristic equation and its roots to determine

14
 the general solution of the homogeneous equation.

2. Find a Particular Solution: Find a particular solution for the nonhomogeneous part.
This often involves guessing a solution form based on the form of the nonhomogeneous
term (e.g., polynomial, exponential, trigonometric) and substituting back into the original
equation to determine the constants.

3. Combine Solutions: The general solution of the nonhomogeneous recurrence is the sum
of the general solution of the homogeneous part and the particular solution.

Theorem: Let hn denote the number of ways of dividing a convex polygonal region with n + 1
sides into triangular regions by inserting diagonals that do not intersect in the interior. Define
h1 = 1. Then hn satisfies the recurrence relation:

hn = h1 hn−1 + h2 hn−2 + · · · + hn−1 h1 ,(n ≥ 2)

 
1 2n − 2
The solution of this recurrence relation is: hn = , (n = 1, 2, 3, . . . )
n n−1

6 Special Counting Sequences

 
1 2n
Catalan Numbers: The n’th Catalan Number is defined by: Cn = , n∈W
n+1 n
The first few Catalan numbers are C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, and so on.
The sequence of Catalan numbers is known as the Catalan sequence.

The catalan numbers arise in various combinatorial problems, one of them being: Find the
number of ways to divide a convex polygonal region with n + 1 sides into triangles by inserting
diagonals that do not intersect in the interior.

Theorem: The number of sequences a1 , a2 , . . . , a2n of 2n terms that can be formed by us-
ing exactly n +1’s and exactly n −1’s, whose partial sums are always positive:

Sk = a1 + a2 + · · · + ak > 0 (k = 1, 2, . . . , 2n)

equals the n-th Catalan number

4n − 2
Recursive Formula for the Catalan Numbers: Cn = Cn−1 C0 = 1.
n+1
Pseudo Catalan Numbers: The pseudo-Catalan numbers Cn∗ are defined in terms of the
Catalan numbers Cn−1 for n ≥ 1. Specifically, the pseudo-Catalan numbers are given by:

(2n − 2)!
Cn∗ = n!Cn−1 = , for n = 1, 2, 3, . . .
(n − 1)!
Recursive Formula: Cn∗ = (4n − 6)Cn−1
∗ , C1∗ = 1

Difference Sequences: Let h0 , h1 , h2 , . . . , hn , . . . be a sequence of numbers. We define a

new sequence ∆h0 , ∆h1 , ∆h2 , . . . , ∆hn , . . . , called the (first-order) difference sequence of the
original sequence, by ∆hn = hn+1 − hn , (n ≥ 0). The terms of the difference sequence are the
differences of consecutive terms of the original sequence. We can form the difference sequence
of the first-order difference sequence and obtain the second-order difference sequence and so on.

15
More generally, we can inductively define the pth-order difference sequence of the original se-
quence by ∆p h0 , ∆p h1 , ∆p h2 , . . . , ∆p hn , . . . (p ≥ 1), where ∆p hn = ∆(∆p−1 hn ).

Thus, the pth-order difference sequence is the first-order difference sequence of the (p − 1)th-
order difference sequence.

Theorem: Let the general term of a sequence be a polynomial of degree p in n:

hn = ap np + ap−1 np−1 + · · · + a1 n + a0 , (n ≥ 0).

Then the (p + 1)th-order differences of this sequence are all zero: ∆p+1 hn = 0 for all n ≥ 0.

Difference Table: The difference table for a sequence h0 , h1 , h2 , . . . , hn , . . . is obtained by

arranging the sequence as row 0 and then computing the successive differences between consec-
utive elements for each row. For the p-th row, the differences are calculated from the (p − 1)-th
row until all the differences become zero. The difference table is fully determined by the entries
in the 0th row and the diagonal elements along the left edge of the table, which are the 0-th,
1-st, 2-nd differences, and so on.

Theorem: The general term of the sequence whose difference table has its 0th diagonal equal to

c0 , c1 , c2 , . . . , cp , 0, 0, 0, . . . , where cp ̸= 0
     
n n n
is a polynomial in n of degree p satisfying: hn = c0 + c1 + c2 + · · · + cp
1 2 p
Theorem: Assume that the sequence h0 , h1 , h2 , . . . , hn , . . . has a difference table whose 0th
diagonal equals c0 , c1 , c2 , . . . , cp , 0, 0, . . ..
n      
X n+1 n+1 n+1
Then hk = c0 + c1 + · · · + cp
1 2 p+1
k=0
Stirling Numbers of the Second Kind: The Stirling numbers of the second kind, de-
noted as S(n, k), are defined as the number of ways to partition a set of n elements into k
non-empty subsets. These numbers satisfy the recurrence relation:

S(n, k) = kS(n − 1, k) + S(n − 1, k − 1)

with initial conditions: S(0, 0) = 1, S(n, 0) = 0 for n > 0, S(0, k) = 0 for k > 0

The Stirling numbers of the second kind can also be expressed using the formula:
k  
1 X k−i k
S(n, k) = (−1) in
k! i
i=0

The Bell Number: The Bell number Bn represents the number of ways to partition a set of n
elements into non-empty subsets. It can be defined using Stirling numbers of the second kind:
n
X
Bn = S(n, k)
k=0

16
Alternatively, the Bell numbers can be computed recursively with:
n  
X n
B0 = 1, Bn+1 = Bk
k
k=0

Stirling Numbers of the First Kind: The Stirling numbers of the first kind, denoted
as c(n, k) or s(n, k), count the number of ways to arrange n elements into k non-empty circular
permutations. These numbers satisfy the recurrence relation:

s(n, k) = (n − 1)s(n − 1, k) + s(n − 1, k − 1)

with initial conditions: s(0, 0) = 1, s(n, 0) = 0 for n > 0, s(0, k) = 0 for k > 0

The Stirling numbers of the first kind can also be represented explicitly as:
k  
k−i k
X
s(n, k) = (−1) in
i
i=0
Partition of an Integer: A partition of a positive integer n is a way of writing n as a
sum of positive integers, where the order of the summands does not matter. Each of the posi-
tive integers in the sum is called a part of the partition.

The partition of n is sometimes written as λ = nan ...2a2 ...1a1 , where ai is a nonnegative integer
equal to the number of parts equal to i.

Note: The λ notation is purely symbolic; Its terms are not exponentials nor is the expres-
sion a product.

Partition Sequence: The partition sequence is a sequence of numbers that represents the
count of all possible partitions for each positive integer n. The n-th term in the sequence,
denoted by p(n), gives the number of ways in which the integer n can be expressed as a sum of
positive integers, disregarding the order of the addends.

The partition sequence starts as follows:

p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11, ...

Ferrers Diagram: A Ferrers diagram is a graphical representation of a partition of a pos-

itive integer n. It consists of rows of dots or boxes, where each row represents one part of
the partition, arranged in non-increasing order. Specifically, if n = a1 + a2 + · · · + ak , where
a1 ≥ a2 ≥ · · · ≥ ak > 0, then the Ferrers diagram of this partition consists of k rows, with ai
dots or boxes in the i-th row. The rows are left-justified.

Theorem: Let n and r be positive integers with r ≤ n. Let pn (r) be the number of par-
titions of n in which the largest part is r, and let qn (r) be the number of partitions of n − r in
which no part is greater than r. Then pn (r) = qn (r)

Conjugate Partition: A conjugate partition of a given partition is obtained by transpos-

ing the rows with columns of the Ferrers diagram of that partition. If the partition of a positive
integer n is represented as n = a1 + a2 + · · · + ak , where a1 ≥ a2 ≥ · · · ≥ ak > 0, its Ferrers
diagram consists of k rows, with ai dots or boxes in the i-th row.

17
Self Conjugate Partition: A self-conjugate partition is a partition of a positive integer that
is equal to its conjugate partition. In other words, when the Ferrers diagram of the partition is
transposed (by swapping rows and columns), the resulting diagram is identical to the original
one.

Theorem: Let n be a positive integer. Let psn be the number of self-conjugate partitions
of n, and let ptn be the number of partitions of n into distinct odd parts. Then: psn = ptn

Theorem: Let n be a positive integer. Let pon be the number of partitions of n into odd
parts, and let pdn be the number of partitions of n into distinct parts. Then: pon = pdn
∞ ∞
X Y 1
Theorem: p n xn =
1 − xk
n=0 k=1
This theorem provides an expression for the generating function of the sequence of partition
numbers in the form of an infinite product. The expression on the right equals the product of
geometric series for each positive integer k, which counts the number of partitions of n.

Theorem: Lexicographic order is a linear extension of the partial order of majorization on

the set Pn of partitions of a positive integer n.

Simple stated, The lexicographic order is a way of arranging partitions of an integer n in a

sequence, similar to how words are arranged in a dictionary. This ordering is consistent with
the majorization order, which is a way of comparing partitions based on their sizes. Essentially,
lexicographic order preserves the natural hierarchy that exists among partitions when compar-
ing their sums and distributions.

Euler’s pentagonal number theorem: Let n be a positive integer. Let peven n be the number
of partitions of n into an even number of distinct parts, and let podd
n be the number of partitions
of n into an odd number of distinct parts. Then: peven
n − p odd = e
n n

j(3j ± 1)
(−1)j if n = for some integer j,

where en is given by: en = 2
0 otherwise
Lattice Paths: A lattice path is a path in a Cartesian coordinate plane that consists of a
sequence of moves between points with integer coordinates. Typically, the moves are restricted
to certain directions, such as up, down, left, or right. Most commonly, lattice paths involve
steps from one point to another in specific directions.

Theorem 8.5.1: The number of rectangular lattice paths from (r, s) to (p, q) equals the bino-
mial coefficient:
   
p−r+q−s p−r+q−s
=
p−r q−s

Theorem: Let n be a nonnegative integer. Then the number of subdiagonal rectangular

lattice paths from (0, 0) to (n, n) equals the n-th Catalan number:
 
1 2n
Cn =
n+1 n

18
Subdiagonal rectangular lattice paths are lattice paths from the point (0, 0) to the point
(n, n) that consist of moves only to the right or up, and that never go above the line y = x (i.e.,
the diagonal line from (0, 0) to (n, n)).

In other words, as the path moves from (0, 0) to (n, n), it always remains on or below the
diagonal y = x. This means that for any point (x, y) on the path, it must satisfy the condition
y ≤ x.

Theorem 8.5.3: Let p and q be positive integers with p ≥ q. Then the number of subdi-
agonal rectangular lattice paths from (0, 0) to (p, q) equals.
 
p−q+1 p+q
p+1 q
HVD lattice paths HVD lattice paths are lattice paths on a Cartesian grid that are allowed
to use three specific types of moves:

1. Horizontal (H): Moving one unit to the right, represented as (x, y) → (x + 1, y).

2. Vertical (V): Moving one unit up, represented as (x, y) → (x, y + 1).

3. Diagonal (D): Moving one unit diagonally, represented as (x, y) → (x + 1, y + 1).

Theorem: Let K(p, q) be the number of HVD-lattice points from (0, 0) to (p, q) and let
K(p, q : rD) be the number of such paths that use exactly r diagonal steps D. Let r ≤ min{p, q}.
Then:
 
p+q−r (p + q − r)!
K(p, q : rD) =
r (p − r)!(q − r)!r!
min{p,q}
X (p + q − r)!
K(p, q) =
(p − r)!(q − r)!r!
r=0

Theorem: Let R(p, q) be the number of subdiagonal HVD-lattice paths from (0, 0) to (p, q)
and let R(p, q : rD) be the number of such paths that use exactly r diagonal steps D.Let p and
q be positive integers with p ≥ q, and let r be a nonnegative integer with r ≤ q. Then:

p−q+1 (p + q − r)!
R(p, q : rD) = ·
p − r + 1 r!(p − r)!(q − r)!
q
X p−q+1 (p + q − r)!
R(p, q) = ·
p − r + 1 r!(p − r)!(q − r)!
r=0

Schroder Paths: Schroder paths are lattice paths from the point (0, 0) to the point (n, n)
that consist of three types of allowed moves:

1. Horizontal (H): Moving one unit to the right, represented as (x, y) → (x + 1, y).

2. Vertical (V): Moving one unit up, represented as (x, y) → (x, y + 1).

3. Diagonal (D): Moving one unit diagonally, represented as (x, y) → (x + 1, y + 1).

A Schroder path always stays on or below the diagonal y = x and is associated with the Schroder
numbers, which count the total number of such paths for a given n.

19
Fully Parenthasizing Expressions: Fully parenthesizing an expression means adding paren-
theses to an expression involving multiple terms and binary operations in such a way that the
entire expression is completely and uniquely defined by the parentheses structure, leaving no
ambiguity about the order of operations.

Small Schröder numbers: (sn ): These count the number of ways to fully parenthesize an
expression involving n + 1 variables with only binary operations, where only valid full bracket-
ings are allowed, and the parentheses structure must avoid certain configurations that can be
directly related to diagonal lattice paths.

Large Schröder numbers: (Rn ): These count the number of ways to fully parenthesize
an expression involving n + 1 variables using binary operations, where partial bracketings that
may include products without restrictions are also allowed.
n
X 1 (2n − 1)!
Rn = R(n, n) = ·
n − r + 1 r!((n − r)!)2
r=0

Algorithm to Construct Bracketings

1. Start with a Sequence: Start with the sequence a1 , a2 , . . . , an .

2. While Loop (Condition: Sequence Length ≥ 3):

(a) While the sequence γ has at least three symbols, do the following steps:
i. Insert Parentheses: Put a set of parentheses around any number k ≥ 2 of con-
secutive symbols, say ai ai+1 . . . ai+k−1 , to form a new symbol (ai ai+1 . . . ai+k−1 ).
ii. Replace Sequence: Replace γ with the new expression in which (ai ai+1 . . . ai+k−1 )
is treated as one symbol.

3. Output the Current Expression: After processing the sequence in all possible ways,
output the resulting bracketing.

Theorem: The generating function for the sequence (sn : n ≥ 1) of small Schröder numbers is:
∞ p
X 1 + x − (1 + x)2 − 8x
g(x) = =
4
n=1

Theorem: The generating function for the sequence (Rn : n ≥ 0) of large Schröder num-
bers is:
 √ 
∞ 1 − x − x 2 − 6x + 1
X
Rn xn =
2x
n=0

Relationship Between Small and Large Schroder Numbers: Rn = 2sn

20