Combinatorics Basics

Counting techniques and graph theory (undergraduate years 1-2)

Overview

Concept map: basic combinatorics Diagram showing the relationship among the four areas studied in basic combinatorics: counting principles, recurrences, existence theorems, and an introduction to graph theory. Counting principles Bijective principle Double counting Inclusion-exclusion Recurrences Fibonacci sequence Catalan numbers Partition numbers Existence theorems Pigeonhole principle Diagonal argument Graph theory intro Graph definitions Trees and Eulerian trails Planar graphs

The basic level introduces the foundational techniques of combinatorics at the undergraduate level. It covers powerful counting tools such as inclusion-exclusion and the pigeonhole principle, analysis of sequences via recurrences, and an introduction to graph theory.

Learning goals

  • Understand and apply the inclusion-exclusion principle
  • Set up and solve recurrence relations
  • Construct existence proofs using the pigeonhole principle
  • Understand the fundamental concepts and properties of graphs

Table of contents

  1. Chapter 1 Counting principles

    Bijective principle, double counting, use of symmetry

  2. Chapter 2 Inclusion-exclusion principle

    The inclusion-exclusion formula, derangements, Euler's totient function

  3. Chapter 3 Recurrence relations

    Linear recurrences, characteristic equation, general term

  4. Chapter 4 Pigeonhole principle

    Basic form, generalizations, applications

  5. Chapter 5 Basics of graphs

    Definition of graphs, degree, connectivity

  6. Chapter 6 Trees and Eulerian trails

    Properties of trees, Eulerian trails, Hamiltonian paths

Prerequisites

Key formulas

Inclusion-exclusion principle

$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_i |A_i| - \sum_{i \lt j} |A_i \cap A_j| + \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$$

Example: $|A \cup B| = |A| + |B| - |A \cap B|$. The cardinality of a union is obtained by correcting for double-counted intersections.

Pigeonhole principle

Placing $n+1$ objects into $n$ boxes forces at least one box to contain two or more objects.

Example: among any 13 people, at least two share a birth month (13 people distributed among 12 months).

Handshake lemma

$$\sum_{v \in V} \deg(v) = 2|E|$$

The sum of degrees over all vertices equals twice the number of edges. Each edge contributes one unit to the degree of each of its two endpoints, so the identity holds.

References