A Sales Pitch for Combinatorics

“kakuhen”

1 Llendo al Territorio Catal´an

Recall from the basic counting review that binomial coeﬃcients are deﬁned 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 ﬁrst 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 coeﬃcients in an equally fast but signiﬁcantly 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 coeﬃcient.”

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 suﬃces 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

ﬁrst 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 reﬂected 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. Reﬂect 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 ﬁxed, we may recover P by reﬂecting 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.

Deﬁnition 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 .

Deﬁnition 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 ﬁnite 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.

Deﬁnition 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).

Deﬁnition 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.

Deﬁnition 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

Deﬁnition 2.7. A graph is complete if every vertex is mutually adjacent.

Example 2.8. The ﬁgure 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 ﬁnite, 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.

Deﬁnition 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.

Deﬁnition 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 deﬁned 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 diﬀerent

ﬂavor of mathematics. Thank you for your time!