Combinatorics

Question 1

How many ways are there to place k labelled balls into n labelled boxes?

Answer 1

The number of ways to place k labelled balls into n labelled boxes is n^k.

Question 2

What is the Multinomial Theorem?

Answer 2

Let n be a positive integer. Then
(a1 + · · · + ar)ⁿ = ∑_{k1+···+kr=n} (nCk1, . . . , kr) * a₁^k1 · · · a_r^kr.

Question 3

How many ways are there to distribute n balls into n labelled boxes, with k1 balls coloured c1, . . . , kr balls coloured cr?

Answer 3

Suppose we have n labelled boxes, and n balls — k1 labelled with colour c1, k2 labelled with colour c2, and so on up to kr labelled with colour cr, where k1 + k2 + · · · + kr = n. Then the number of distinct ways of distributing the balls among the boxes is n!/k1!k2!···kr!

Question 4

What is the set [n]?

Answer 4

For brevity, rather than writing {1, . . . , n} and {1, . . . , k} all the time, we will write [n] and [k]. This is reasonably standard. Note that zero is not included, and that [0] is the empty set ∅.

Question 5

What is the Inclusion-Exclusion Theorem?

Answer 5

Let A1, . . . , Ar be sets. Then
|A1 ∪ · · · ∪ Ar| = ∑_{I⊆{1,…,r},I=∅} (−1)^|I|−1 |∩_i∈I Ai|

Question 6

How many surjections are there from [k] to [n]?

Answer 6

Surj(k,n) = ∑_m=0ⁿ (−1)^m(n − m)^k nCm.

Question 7

What are the Stirling Numbers (of the second kind)?

Answer 7

What if we count surjections, but with unlabelled boxes? This has a nice interpretation, namely counting the ways of dividing [k] into n nonempty pieces.
These numbers S(k, n) are called the Stirling numbers of the second kind.

Question 8

What is the formula for the Stirling Numbers.

Answer 8

S(k,n) = 1/n! * Surj(k,n)

Question 9

What are the Bell Numbers?

Answer 9

For k ≥ 0, define the Bell numbers Bk = ∑_n=0^k S(k, n). That is, Bk is the number of ways to partition [k] into any number of parts.

Question 10

How can we use Stars and Bars?

Answer 10

Where k unlabelled objects have to be shared among n labelled boxes, we can consider the ‘joint sequence’ of stars and bars, distributing the objects between the bars. Then we see that we have to choose where to place k objects among (n+k-1) places, giving
(n+k-1)Ck = (n+k-1)C(n-1) ways to distribute.

Question 11

What is a Generating function of a sequence?

Answer 11

Let (an)n≥0 be a sequence of numbers. The formal power series
∑n=0,∞ an * x^n
is called the ordinary generating function of (an)n≥0, and the formal power series
∑n=0,∞ an * (x^n/n!)
is called the exponential generating function of (an)n≥0.

Question 12

How are generating functions useful?

Answer 12

We use generating function to come up with a simple formula for a sequence.
Given a sequence that relies on some sort of recursion (e.g. the Fibonacci sequence), we can find a formula for the next term in the sequence, depending on n only.

Basically there will be some identity with the generating function of a sequence and that can be used to find individual terms from the coefficients of the series.

When choosing which type of generating function to use, use the one that has similar growth as to the sequence at hand. ie. use the exponential one if the sequence grows exponentially-ish.

Question 13

What is p(n) and p_k(n)?

Answer 13

These are the number of integer partitions into any number of boxes and the partitions into k boxes.

Question 14

What is the useful way of drawing integer partitions, a Ferrer diagram?

Answer 14

Given a partition of n, in order of size. So n = a1 + a2 + … + ar where a1>=a2>=…>=ar.
Then the diagram consists of r bars drawn horizontally, one of top of another and the bars are made up of ai squares.

Question 15

What is the conjugate of an integer partition?

Answer 15

Let λ be a partition of n. The conjugate partition λT of λ is the partition corresponding to the reflection of the Ferrers diagram of λ over the (upper-left-to-lower-right) diagonal

Question 16

How are integer partitions related between amount of parts and size of parts?

Answer 16

The number of partitions of n into at most k parts is equal to the number of partitions of n into parts of size at most k.
We can relate the two by conjugation of their respective diagram.

Question 17

How is the number of integer partitions into odd parts and distinct parts related?

Answer 17

The number of partitions of n into odd parts is equal to the number of partitions of n into distinct parts.

Question 18

What is a triangulation?

Answer 18

A triangulation of a regular n-gon is a collection of non-crossing diagonals that divide the n-gon into triangles.

Question 19

What are the Catalan numbers?

Answer 19

The nth Catalan number Cn is the number of triangulations of a regular (n + 2)-gon.

Question 20

What is a Graph?

Answer 20

Definition 2.1. A graph (or simple graph) G = (V, E) is
* a set V , whose elements are called the vertices of G, and
* a set E of unordered pairs of distinct vertices, whose elements are called the edges of G.

Question 21

What is the terminology for graphs?

Answer 21

Let G = (V, E) be a graph.
* If e ∈ E contains v, we say e is incident to v, or v is an endpoint of e.
* If v1, v2 ∈ V are vertices such that {v1, v2} ∈ E, we say v1 and v2 are adjacent (or are neighbors).
* For v ∈ V, the number of edges incident to v is called the degree deg(v) or valence val(v) of v.

Question 22

What is a regular graph?

Answer 22

A graph is called k-regular if every vertex has degree k. (Or just regular if it is k-regular for some k.)

Question 23

What is the degree-sum fromula?

Answer 23

Let G = (V, E) be a graph. Then
∑_v∈V deg(v) = 2*|E|.
In particular, the number of odd-degree vertices of G is even.

Question 24

When are graphs isomorphic?

Answer 24

Two (simple) graphs G = (V, E) and G′ = (V′,E′) are isomorphic if there exists a bijection ϕ : V → V′such that {v1, v2} ∈ E
if and only if {ϕ(v1), ϕ(v2)} ∈ E′. (That is, if they differ only in the naming of the vertices).

Question 25

What are subgraphs? And spanning subgraphs, and induced subgraphs?

Answer 25

• Let G = (V, E) and H = (V′, E′) be simple graphs, where V′ ⊆ V . We say H is a subgraph of G if for all edges {v1, v2} ∈ E′, we have {v1, v2} ∈ E
• Let G = (V, E) be a connected graph, and let H = (V′, E′) be a subgraph (so V′ ⊆ V ). We say H is a spanning subgraph (or H spans G) if V′ = V.
• For a graph G = (V, E) and a subset V′ ⊆ V, the subgraph of G induced by V′ is the subgraph with vertex set V′ and edge set E′ = {e ∈ E : e ⊆ V′}. That is, the set of all edges between vertices in V′.

Question 26

When does a graph contain another?

Answer 26

Let G and G′ be graphs. We say G′
contains G if G is isomorphic to a subgraph of G′.

Question 27

What is a connected graph?

Answer 27

A graph G = (V, E) is connected if for every pair v1, v2 ∈ V, there is a path in G from v1 to v2. (Usually a good property if your graph represents, e.g., an airline, or the internet.) The maximal connected subgraphs of a (disconnected) graph are called its connected components.

Question 28

What is the independence set and vertex independence number?

Answer 28

An independent set of vertices in a graph is a subset of the vertices such that no two elements are adjacent. The vertex independence number ind_V (G) of G is the cardinality of the largest independent set in G.

Question 29

What is a matching and the matching number?

Answer 29

A matching in a graph is a subset of the edges such that no two elements share an endpoint. The matching number ind_E(G) of G is the cardinality of the largest matching in G. If there exists a matching using all vertices of G, it is called a perfect matching.

Question 30

What is a colouring of a graph and its chromatic number?

Answer 30

An colouring of a graph G = (V, E) with colour set C is a function f : V → C such that for every edge e of G, the endpoints of e are different colours (i.e. if the endpoints are called v1 and v2, then f(v1) ̸= f(v2)). The chromatic number χ(G) of G is the cardinality of the smallest colour set for which there exists a colouring of G.

Question 31

What is the distance between two vertices and diameter of a graph?

Answer 31

The distance between two vertices v1, v2 in a graph G = (V, E) is the length of the shortest path containing v1 and v2. The diameter diam(G) of G is the maximum distance between two vertices in G.

Question 32

What is the girth of a graph?

Answer 32

The girth girth(G) of a graph G = (V, E) is the length of the shortest cycle in G.

Question 33

What is an acyclic graph?

Answer 33

A graph G is called acyclic if it does not contain any cycles. That is, there is no subgraph isomorphic to Cn for any n ≥ 1.

Question 34

What is a tree?

Answer 34

A connected acyclic graph is called a tree. (A disconnected acyclic graph, i.e. a union of trees, is called a forest.)

Question 35

How does removing an edge affect a tree?

Answer 35

If G = (V, E) is a tree, and e = {v1, v2} ∈ E is an edge, then G′ = (V, E \ e) is not connected. (“Cutting any edge disconnects the tree.”)

Question 36

What type of graph is G if it is connected and removing any edge disconnects G?

Answer 36

Conversely, if G is connected, and cutting any edge disconnects G, then G is a tree.

Question 37

How many edges does a tree with n vertices have?

Answer 37

A tree with n vertices has n − 1 edges.

Question 38

What is a leaf?

Answer 38

A vertex in a tree with degree 1.

Question 39

How many leaves does a tree have?

Answer 39

A (finite) tree with at least two vertices has at least one leaf. (In fact, at least two!)

Question 40

What are the equivalent statements about a graph that is a tree?

Answer 40

Let G = (V, E) be a graph. The following are equivalent:
(1) G is a tree — that is, G is connected and acyclic.
(2) G is minimally connected — that is, G is connected, but removing any edge disconnects G.
(3) G is connected and satisfies |E| = |V | − 1.

Question 41

What are the upper bound on the chromatic number?

Answer 41

Proposition 6.4. χ(G) ≤ (max_v∈V deg(v)) + 1

Question 42

What is a bipartite graph?

Answer 42

A graph that has a 2-colouring is called bipartite. That is, G is bipartite if χ(G) ≤ 2. Sometimes G is called k-partite if χ(G) ≤ k

Question 43

How does a graph being bipartite relate to cycles?

Answer 43

A graph is bipartite if and only if it contains no odd-length cycles

Question 44

What is the complete bipartite graph?

Answer 44

The complete bipartite graph Ka,b has vertex set V = V1 ⊔ V2, where |V1| = a, |V2| = b, and there is a single edge connecting every vertex of V1 to every vertex of V2. (So ab edges altogether.) These will show up quite a bit.
One can also define the complete multipartite graph Ka1,a2,…,ar , in which vertices are divided into partite sets of sizes a1,…,ar, and vertices are connected by an edge if they are in different partite sets.

Question 45

What is the Kneser graph?

Answer 45

The Kneser graph Kn(n, k) is defined as follows. The vertices of Kn(n, k) are the k-element subsets of [n]. Two vertices are connected by an edge if they are disjoint.
Kn(n, k) can be coloured with n − 2k + 2 colours.

Question 46

What is an Eulerian Circuit?

Answer 46

An Eulerian circuit of a graph G is a closed walk (ends where it starts) that traverses each edge exactly once. If an Eulerian circuit of G exists, we say G is Eulerian.
In order for an Eulerian circuit to exist, we need every vertex to have even degree.

Question 47

How does a graph being Eulerian relate to degree?

Answer 47

A connected graph G is Eulerian if and only if every vertex has even degree.

Question 48

When is a graph Hamiltonian?

Answer 48

A Hamiltonian cycle of a graph G is a spanning cycle in G. That is, a walk in G that is closed (ends where it started), and touches each vertex exactly once (except the start/end, which is touched twice). If G has a Hamiltonian cycle, we say G is Hamiltonian.

Question 49

How can we tell a graph is Hamiltonian from the amount of vertices and their degree?

Answer 49

Suppose G is a simple connected graph with n ≥ 3 vertices, such that every vertex has degree at least n/2. Then G has a Hamiltonian cycle.

Question 50

How do matchings work in a bipartite graph depending on the cardinality of the partite groups?

Answer 50

If |A| < |B| , then the largest matching we can possibly hope for is of size |A|, since every edge contains a vertex in A. Our main problem will be determining whether G has a perfect matching (only possible if |A| = |B|), but we might as well generalize slightly to ask if G contains a “matching of A.” (If |A| > |B|, we just reverse the role of A and B.)

Question 51

What is Hall’s condition and theorem?

Answer 51

Hall’s condition: In order to have a matching of A, we must have that for every subset S ⊆ A, we have |NG(S)| ≥ |S| (where NG(S) is the set of all neighbours of all elements of S).

Hall’s Theorem: If G satisfies Hall’s condition, then there is a matching of A.

Question 52

How does a regular bipartite graph admit a matching?

Answer 52

A regular bipartite graph has |A| = |B| and admits a perfect matching.

Question 53

What is the Crossing Number and when is a graph Planar?

Answer 53

The crossing number cross(G) of a graph G is the fewest number of edge crossings required to draw G in the plane. (Edges are not allowed to pass through vertices other than their endpoints.) A graph with crossing number zero is called a planar graph. So, a planar graph has a drawing in the plane with no edge crossings.

Question 54

What is a face of a planar graph?

Answer 54

A face of the graph is a region bounded by a set of edges and vertices in the embedding. NOTE that the outer region is also a face.

Question 55

How are the number of vertices, edges and faces related?

Answer 55

For a drawing of a connected planar graph, |V | − |E| + |F| = 2.

Question 56

What is an upper bound on the number of edges in a planar graph?

Answer 56

A simple connected planar graph with n ≥ 3 vertices has at most 3n − 6 edges.

Question 57

What can we tell about a vertex in a planar graph?

Answer 57

A simple planar graph has a vertex with degree at most 5.

Question 58

What does it mean to contract and delete an edge?

Answer 58

Given a graph G and an edge e of G, we can contract e; this means that we remove e and merge its two endpoints. We can also delete e (leaving its endpoints alone).

Question 59

What does it mean to delete a vertex?

Answer 59

Given a graph G and a vertex v, we can delete v which also includes deleting all edges incident to v.

Question 60

What is a minor graph?

Answer 60

A graph H is a minor of a graph G if H can be obtained from G by a sequence of edge contractions, edge deletions, and vertex deletions.

Question 61

What minors will a planar graph not have?

Answer 61

A graph G is planar if and only if it if does not have K3,3 or K5 as a minor.

Question 62

What is an upper bound on the chromatic number of a planar graph?

Answer 62

If G is planar, then χ(G) ≤ 4.

Question 63

What is Ramsey’s Theorem?

Answer 63

Let r, s ≥ 2. Then for sufficiently large n, every 2-coloring of the edges of Kn contains a red Kr or a blue Ks.

The minimal such n is called the Ramsey number R(r, s).

Question 64

What is an upper bound on the Ramsey number?

Answer 64

R(k, ℓ) ≤ (k+ℓ−2)C(k−1)

Question 65

What is a lower bound on the Ramsey number?

Answer 65

For k ≥ 4, we have R(k, k) > 2^k/2

Question 66

How can we make a graph with any chromatic number?

Answer 66

For any positive integers k and r, there exists a graph with chromatic number > r, with girth > k. (That is, no cycles of length ≤ k.)