A Sales Pitch for Combinatorics
“kakuhen”
1 Llendo al Territorio Catal´an
Recall from the basic counting review that binomial coefficients are defined as
n
k
=
n(n − 1) · · · (n − k + 1)
k!
=
n!
k!(n − k)!
and we showed a rather interesting result: that
2n
n
is even for all n > 0. It turns out there are
many equally interesting identities out there. We begin with a classical example.
Example 1.1. Suppose we form a 5-card poker hand from a standard 52-card deck
1
. There are
52
5
ways to do this. However, notice that every hand either contains the ace of spades or does not.
If we form a hand by first including the ace of spades, we choose 4 cards from a deck of 51 cards.
If we decide to not include the ace of spades, then we choose 5 cards from a deck of 51 cards. This
yields
52
5
=
51
4
+
51
5
.
By replacing “deck” with “set,” “hand” with “subset,” and “ace of spades” with “distinguished
element,” we essentially proved the following.
Theorem 1.2. (Pascal’s Identity) For all 0 ≤ k ≤ n, we have
n
k
=
n−1
k−1
+
n−1
k
.
This identity allows us to compute binomial coefficients in an equally fast but significantly neater
way than the absorption identity. It gives rise to what we call “Pascal’s triangle.”
n = 0 1
n = 1 1 1
n = 2 1 2 1
n = 3 1 3 3 1
n = 4 1 4 6 4 1
n = 5 1 5 10 10 5 1
n = 6 1 6 15 20 15 6 1
Example 1.3. The centermost numbers are precisely the values of
2n
n
, hence the name “central
binomial coefficient.”
Example 1.4. Any number greater than 1 is the sum of the two numbers right above it; this is
one “visualization” of Pascal’s identity.
Example 1.5. Summing the numbers in each row yields 1, 2, 4, 8, and so on. This is not a
coincidence. Recall [n] has 2
n
subsets, so the sum of all k-element subsets of [n] should be 2
n
.
1
For readers unfamiliar with these cards, see https://en.wikipedia.org/wiki/Standard_52-card_deck.
Combinatorics Sale Pitch
Theorem 1.6.
P
n
k=0
n
k
= 2
n
.
Proof. The right-hand side counts the number of subsets of [n]. The left-hand side counts the
number of k-element subsets separately and sums over all k, but these are all the subsets of [n].
Theorem 1.7.
P
n
k=0
(−1)
k
n
k
= 0.
Proof. It suffices to show the number of even-size subsets of [n] equals the number of odd-size
subsets of [n]. Pick an element x ∈ [n]. The complement of an odd subset containing x is an even
subset not containing x. On the other hand, the complement of an odd subset not containing x is an
even set containing x. Summing the number of odd subsets thus yields the sum of even subsets.
We could also prove the above statement by invoking the binomial theorem, but that gives no
intuition! Let us now move on to an example that we will use for the rest of this section.
Example 1.8. Suppose we are on a grid of integers, and we can move either north or east. How
many paths
2
exist from, say, the origin (0, 0) to the point (2, 5)? Drawing out such a path, we see
that we must take exactly 2 steps east and 5 steps north for a total of 7 steps. But the positions
of the east paths determine when we go north! For instance, E = {1, 3} tells us to go east for the
first and third steps, and north for the remaining steps. So the paths are really 2-element subsets
of [7], and we know there are
7
2
= 21 of those!
Lemma 1.9. There are exactly
n
k
paths from (0, 0) to (k, n − k).
Theorem 1.10. (Symmetry Identity)
n
k
=
n
n−k
.
Proof. The left-hand side counts the number of paths from (0, 0) to (k, n − k), whereas the right-
hand side counts the number of paths from (0, 0) to (n − k, k). Let O = (0, 0), P = (k, n − k), and
Q = (n − k, k). Then OP paths reflected along the line y = x yield OQ paths, and vice versa.
We could also prove the symmetry identity by talking about k-element subsets of [n], but the
above “geometric” proof is nicer. In fact, let us prove Pascal’s identity using paths.
Proof of Theorem 1.2. Suppose we want to form a path from (0, 0) to (k, n − k). We can approach
the last point in two directions: eastward from (k −1, n −k) or northward from (k, n−k − 1). These
sets of paths are inherently disjoint, so there are
n−1
k−1
+
n−1
k
paths from (0, 0) to (k, n − k).
Let us add an interesting constraint to our paths. Let C
n
enumerate paths from (0, 0) to (n, n)
that do not go above the main diagonal. The subtraction principle tells us C
n
is equal to the number
A
n
of paths from (0, 0) to (n, n) minus the number B
n
of paths that go above the diagonal at some
point. Clearly A
n
=
2n
n
, but how do we count B
n
?
Lemma 1.11. There is a bijection between paths counted by B
n
and paths from (−1, 1) to (n, n).
Proof. Let O = (−1, 1) and P be a path counted by B
n
. Then P intersects with line y = x + 1 at
some point (why?). Let Q denote this point of intersection. Reflect the segment OQ along the line
y = x + 1. This yields a path starting at O
0
= (0, 0) where north and east steps are swapped until
we reach the point Q. Since Q is fixed, we may recover P by reflecting O
0
Q along y = x + 1.
Therefore
C
n
=
2n
n
−
2n
n + 1
=
2n
n
−
(2n)!
(n + 1)!(n − 1)!
·
n
n
=
2n
n
−
n
n + 1
(2n)!
n!
2
=
1
n + 1
2n
n
.
These numbers count so many things
3
that we give them a special name: the Catalan numbers.
2
Technically, these “paths” are north-east lattice paths, but for sake of brevity, we will just say “path.”
3
Enough that there are entire books written on what they can count!
Combinatorics Sale Pitch
2 Graph Theory
So we have seen what enumerative combinatorics deals with, albeit in a very restricted scope due to
lack of time and lack of diversity in examples. We will end this lecture by introducing yet another
discrete structure and we will connect them with the previous discussion.
Definition 2.1. A graph is a pair G = (V, E) where V is called a vertex set and E is called an edge
set. Vertices are simply elements of V . Edges are 2-element subsets of V .
Definition 2.2. Given a graph G, we say a vertex u is adjacent to v if uv ∈ E. We also say E is
incident to u (or v). The set of vertices adjacent to u is the neighborhood of u, denoted N (u).
We assume V and E are finite and there are no loops or multiple edges. Note that vertices need
not belong to an edge. In fact, V or E may be empty! When both V and E are empty, we have a
trivial graph. When only E is empty, we have an empty graph.
Definition 2.3. The order of a graph is |V |, and the size of a graph is |E|. The number of edges
incident to vertex v is the degree of v, written as deg(v).
Definition 2.4. A walk is a sequence of vertices v
1
, · · · , v
n
where v
i
v
i+1
∈ E for 1 ≤ i ≤ n − 1. If
edges are unique, then we have a trail. If both vertices and edges are unique, then we have a path.
Definition 2.5. A connected graph is a graph where there is a path between any two vertices.
Example 2.6. Below is a graph of order 5 and size 4. The vertex v
4
, for instance, has degree 2.
Notice there are no paths from v
1
to v
3
, and these vertices are not adjacent. Moreover, this graph
is not connected, so this graph is disconnected. Lastly, N (v
1
) = {v
2
}.
v
1
v
2
v
3
v
4
v
5
Definition 2.7. A graph is complete if every vertex is mutually adjacent.
Example 2.8. The figure below is a complete graph on 6 vertices, which we denote as K
6
.
We will now show some basic results about graphs.
Theorem 2.9. Let G be a graph. Then
P
v∈V
deg(v) = 2|E|.
Proof. Edges have two endpoints, so we count each edge twice when summing over each vertex.
Corollary 2.10. The number of vertices of odd degree in a graph must be even.
Combinatorics Sale Pitch
Theorem 2.11. Let u, v be vertices of a graph. Then a u-v walk contains a u-v path.
Proof. Given a walk u = v
1
v
2
· · · v
n
= v, let k be the smallest integer satisfying v
k
= v
r
for some
r > k. Then construct the walk u = v
1
· · · v
k
v
r+1
· · · v
n
= v and repeat the process until no such k
exists. As the walk is finite, this process eventually terminates.
We will now show some results reminiscent of those in the previous section.
Lemma 2.12. The maximum number of edges in a graph with n vertices is
n
2
.
Proof. First choose a vertex; there are exactly n of them. Each vertex can be connected to at most
n − 1 other vertices. Since edges uv and vu are indistinguishable, we divide by 2 and hence the
result holds.
Theorem 2.13. A graph of order n with at least
n−1
2
+ 1 edges is connected.
Proof. Suppose a graph is disconnected into two components with k vertices and n − k vertices. By
the above lemma, there are at most
k
2
and
n−k
2
edges, respectively. Since
k
2
+
n−k
2
≤
n−1
2
for 1 ≤ k ≤ n − 1 (prove this), the result follows.
Since we have little time, we will see how graphs connect to Catalan numbers quickly, and,
hopefully, discuss one beautiful connection between graph theory and group theory.
Definition 2.14. A cycle is a path with equal endpoints. A graph without cycles is acyclic. An
acyclic connected graph is a tree. A rooted tree is a tree with a designated “topmost” vertex called
a root. A parent of a vertex v is the adjacent vertex u lying on the path to the root. We also say v
is a child of u. A full binary tree is a tree where every vertex has 0 or 2 children.
Example 2.15. How many full binary trees with n + 1 leaves are there? Exactly C
n
. We will leave
the reader to imagine (or search up) a bijection between the paths counted in the previous section
and these kinds of trees.
Some graphs turn out to have virtually identical structure to other graphs in the sense that we
can relabel vertices between two graphs without altering edges.
Definition 2.16. A graph isomorphism is a bijective function f : G → H where uv is an edge in
G if and only if f (u)f (v) is an edge in H. A graph automorphism is a graph isomorphism from a
graph G to itself. The automorphism group of a graph is denoted as Aut(G).
We now end this lecture with a quick example.
Theorem 2.17. Aut(G)
∼
=
S
n
if G is an empty or complete graph on n vertices.
Proof. In an empty graph, the automorphisms are bijections from [n] to itself, which is precisely S
n
.
As for a complete graph, notice that we may send any vertex anywhere without adding restrictions
on the placement of the other n − 1 vertices since each vertex is mutually adjacent.
Let G = (V, E) and K denote all 2-element subsets of V . The complement of G is defined as
G = (V, K − E). Notice the complement of a complete graph is an empty graph. If you take a
course in algebraic combinatorics, then you may see the more general result Aut(G)
∼
=
Aut(G).
Although this was not too enlightening, hopefully this entire lecture has shown you a different
flavor of mathematics. Thank you for your time!
