**Resources**: [[MA241 Combinatorics Resources.canvas|MA241 Combinatorics Resources]]. **Summary**: Study of finite structures. We enumerate many labelled (and unlabelled structures incl. weak compositions). Introduce some graph theory. ---- # Enumerative Combinatorics ### 1. Placing balls in boxes **Proposition 1.6.** [[Placing Labelled Balls into Labelled Boxes]]. **Remark 1.4.** If we allow unlabelled balls, then two functions $f_{1}, f_{2}:[n]\to [k]$ are equivalent if $f_{1}=f_{2}\circ \pi$ for some $\pi \in \text{Sym}([n])$. [[Burnside's Lemma]] & [[Pólya's Enumeration Theorem]] lend themselves to enumerating the equivalence classes. If we also allow unlabelled boxes, then we may apply Burnside's lemma again or [[Power Group Enumeration]]. ### 2. Counting permutations **Proposition 2.2.** [[Number of Permutations of n Letters]]. Think also about [[Number of k-Permutations of n Letters (Injections between Finite Sets)]]. ### 3. Combinatorial (double-counting & bijective) proofs for subsets **Proposition 3.1/2.** [[Number of k-Combinations of n Letters]]. **Definition 3.3.** [[Binomial Coefficient]]. **Proposition 3.5.** [[Pascal's Identity for Binomial Coefficients]]. **Example 3.6.** [[Sum of Binomial Coefficients]]. **Exercise 3.7.** [[Hockey Stick Identity for Binomial Coefficients]]. **Exercise 3.8.** [[Sum of Squares of Binomial Coefficients]]. **Theorem 3.9.** [[Binomial Theorem]]. **Theorem 3.12.** [[Multinomial Theorem]]. ### 4/5/6. Inclusion-Exclusion & Counting Surjections These were covered in Week 2. **Theorem 5.2.** [[Inclusion-Exclusion Principle]]. See [[Enumerating surjections between finite sets]]. **Remark**. We observe that a surjective function $f : [k] \to [n]$ induces a partition of $[k]$ into $n$ nonempty parts, by declaring $i \sim j$ if and only if $f(i) = f(j)$. The parts of the partition are precisely the preimages $f^{-1}(1)$, $f^{-1}(2)$, \dots, $f^{-1}(n)$. However, different surjections can induce the same partition if they differ by a relabelling of the target set $[n]$. This relabelling corresponds to an action of the symmetric group $S_n$ on the set of surjections $\text{Surj}(k, n)$, where $\sigma \in S_n$ acts on $f$ by composition: $(\sigma \cdot f)(i) = \sigma(f(i))$. This action is *free*, meaning that no nontrivial permutation fixes a surjection, and two surjections belong to the same orbit if and only if they define the same set partition. Therefore, by Burnside’s lemma (or simply by counting orbits under a free group action), the number of orbits — that is, the number of distinct partitions of $[k]$ into $n$ parts — is given by $S(k, n) = \frac{\#\text{Surj}(k, n)}{n!},$where $S(k, n)$ is known as a [[Stirling numbers of the second kind|Stirling number of the second kind]]. ### 7. Set Partitions: Stirling Numbers We define [[Stirling numbers of the second kind]] and [[Bell Numbers]]. **Proposition 7.2.** [[Recurrence relation for Stirling numbers of the second kind]]. **Proposition 7.6.** [[Recurrence relation for Bell numbers]]. ### 8. ~~Derangements (NON-EXAMINABLE)~~ ### 9. Stars & Bars **Proposition 9.5.** [[Enumerating Multisets (Stars-and-bars)]]. **Remark 9.2/6**. Partitioning by number cookies person $1$ gets gives another proof of the [[Hockey Stick Identity for Binomial Coefficients|hockey-stick identity]]. **Exercise 9.7.** **Exercise 9.8.** ### 10/11. Generating Functions **Example 10.5.** [[Closed formula for Fibonacci Sequence]]. **Example 11.1.** See [[Enumerating Multisets (Stars-and-bars)#^0c2f94]]. **Example 11.3.** [[Exponential generating function for Bell numbers]]. ### 12/13. Integer Partitions [[Recurrence Relations for Number of Integer Partitions with k Parts]]. [[Ordinary Generating Function of Partition Function]]. [[Ordinary Generating Function of Partition Function Restricted by Number of Parts]]. [[Number of Partitions of n into k parts equals Number of Integer Partitions of n-k into Parts that are at Most k]]. [[Self-Conjugate Integer Partitions are in Bijection with Partitions into Distinct Odd Parts]]. [[Numbers of Strict and Odd Integer Partitions are Equal]]. [[Euler's Pentagonal Number Theorem]]. ### 14. Catalan Numbers [[Catalan Numbers Count Polygon Triangulations]]. [[Ordinary Generating Function of Catalan Numbers]]. [[Catalan Numbers Count Monotonic Lattice Paths]]. [[Catalan Numbers in Terms of Central Binomial Coefficient]]. # Graph Theory ### 2/3. The Language of Graphs *From week 6 lectures.* **Definition 2.1.** (Simple) [[Graphs]]. **Definition 2.2.** Incidence of edge to vertex; adjacency of vertices; degree. **Definition 2.3.** Regularity of graphs. **Proposition 2.5.** [[Degree-Sum Formula]]. **Definition 3.1.** [[Isomorphism of Graphs]]; Automorphism. **Remark 3.2.** No known polynomial time algorithm for graph isomorphism problem, except some special cases. **Definition 3.4.** Let $G$ and $G'$ be graphs. We say $G′$ *contains* $G$ if $G$ is isomorphic to a subgraph of $G'$. E.g. A graph may contain a [[Path (Type of Simple Graph)]] or [[Cycle (Type of Simple Graph)]]. **Definition 3.6.** [[Connected Graph]]. **Remark 3.7.** A walk is sequence of edges such that consecutive edges are incident to a common vertex (or equivalently, a sequence of vertices such that consecutive vertices are adjacent). A path in $G$ as defined above prescribes a walk with distinct edges. However, demanding a path between two edges is not a stronger condition than demanding a walk, since one can always modify a walk to gain a path by omitting detours: sub-walks that start and end at the same vertex. ### 4. Basic Measurements of Graphs **Definition 4.1.** [[Independent set of vertices (in graphs)]]; independence number, denoted $\text{ind}_{V}(G)$. **Definition 4.2.** [[Clique (in graphs)]]; clique number, denoted $\text{clique}(G)$. **Definition 4.4.** [[Matching (in graphs)]]; matching number, denoted $\text{ind}_{E}(G)$. **Definition 4.6.** [[Graph Colouring]]; chromatic number, denoted $\chi(G)$. *From week 7 lectures.* Definition 4.9. [[Diameter of graph]]. Definition 4.11. The girth girth(G) of a graph G = (V, E) is the length of the shortest cycle in G. Definition 4.13. A graph G is called Eulerian if there is a closed walk on G that traverses each edge exactly once. Definition 4.14. A graph G is called Hamiltonian if there is a closed walk on G that visits each vertex exactly once. Definition 4.15. A graph G is called acyclic if it contains no cycles (subgraphs isomorphic to Cn for n ≥ 3. **Definition 4.16.** [[Crossing number (graph theory)]]; Planarity. **Definition 4.17.** [[Adjacency Matrix]]. **Exercise**: Study these measurements on the [[Petersen graph|Petersen graph]]. ### 5/6. Trees **Theorems 5.5($\implies$)/6($\impliedby$)/8/10($\implies$)/11($\impliedby$)/13.** See [[Trees (graph theory)]]. Equivalent characterisations of trees as: edge-minimal connected graphs (5 & 6); use [[Finite tree with at least two vertices has a leaf|finite trees have at least one leaf]] (8) to prove [[Finite tree is a connected graph with one less edge than vertices]] (10 & 11); know that trees have at least one root (13) **Theorem 6.2** [[Enumeration of trees on labelled vertices (Cayley's Formula)]]. ### 7. Graph (Vertex) Colouring *From Week 8.* Lemma 7.7. [[Trees are Bipartite]]. Theorem 7.5. [[Graph is Bipartite iff does not contain Odd Cycle]]. ### 9. Matchings of bipartite graphs [[Hall's Theorem]]. ### 8/10. Graph Traversal Problems: Eulerian & ~~Hamiltonian Graphs~~ **Theorem 8.4.** [[Euler's Circuit Theorem]]. ### 11/12. Planarity Theorem 11.7 [[Euler's Characteristic for Connected Planar Graphs]] ### 13. The 4/5/6 colour theorems ### 14. ~~Kneser graphs (NON-EXAMINABLE)~~ ### 15. Some Ramsey theory ### 16. Another probabilistic proof ### ~~17. Triangle-free graphs with high chromatic number: The Mycielski construction (NON-EXAMINABLE)~~