maths.free › Combinatorics & Graph Theory

Combinatorics & Graph Theory

How many, and how connected. Counting arguments that turn into generating functions, and graphs — dots and lines — that model everything from road networks to molecules.

Lesse

Introductory The counting principles Product rule, sum rule, permutations, combinations, and when each applies. 5 choose 2 Core Pigeonhole principle and inclusion–exclusion Two counting ideas that prove things without listing anything. {1,2,3,4} union {3,4,5,6} Core Binomial coefficients and Pascal's triangle Identities, the binomial theorem, and combinatorial proofs. expand (a + b)^6 Core Recurrences and generating functions Solving recurrence relations, and encoding a sequence as a power series. fib(25) Introductory Graphs: vertices, edges, degrees The basic objects of graph theory and the handshake lemma. sum of k for k = 1 to 5 Core Paths, cycles, trees, Euler and Hamilton Connectivity, spanning trees, Euler circuits and the bridges of Königsberg. 5 choose 2 Core Colouring and planar graphs Chromatic number, Euler's formula V − E + F = 2, and the four-colour theorem. 6 - 2

Chapters from Keller & Trotter, Applied Combinatorics

Every section of the book, condensed into a lesson with its own practice problems.

1. An Introduction to Combinatorics

IntroductionEnumerationCombinatorics and Graph TheoryCombinatorics and Number TheoryCombinatorics and GeometryCombinatorics and OptimizationSudoku PuzzlesDiscussion

2. Strings, Sets, and Binomial Coefficients

Strings: A First LookPermutationsCombinationsThe Ubiquitous Nature of Binomial CoefficientsThe Binomial TheoremMultinomial CoefficientsDiscussionAn Activity on Lattice Paths, the Binomial Theorem, and the Multinomial TheoremStrings, Sets, and Binomial Coefficients: exercises

3. Induction

IntroductionThe Positive Integers are Well OrderedThe Meaning of StatementsBinomial Coefficients RevisitedSolving Combinatorial Problems RecursivelyMathematical InductionInductive DefinitionsProofs by InductionStrong InductionDiscussionInduction: exercises

4. Combinatorial Basics

The Pigeon Hole PrincipleAn Introduction to Complexity TheoryThe Big Oh and Little Oh NotationsExact Versus ApproximateDiscussionCombinatorial Basics: exercises

5. Graph Theory

Basic Notation and Terminology for GraphsMultigraphs: Loops and Multiple EdgesEulerian and Hamiltonian GraphsGraph ColoringCounting Labeled TreesA Digression into Complexity TheoryDiscussionGraph Theory: exercises

6. Partially Ordered Sets

Basic Notation and TerminologyAdditional Concepts for PosetsDilworth's Chain Covering Theorem and its DualLinear Extensions of Partially Ordered SetsThe Subset LatticeInterval OrdersFinding a Representation of an Interval OrderDilworth's Theorem for Interval OrdersDiscussionPartially Ordered Sets: exercises

7. Inclusion-Exclusion

IntroductionThe Inclusion-Exclusion FormulaEnumerating SurjectionsDerangementsThe Euler \phi FunctionDiscussionAn Activity to Enumerate SurjectionsInclusion-Exclusion: exercises

8. Generating Functions

Basic Notation and TerminologyAnother look at distributing apples or foldersNewton's Binomial TheoremAn Application of the Binomial TheoremPartitions of an IntegerExponential generating functionsDiscussionGenerating Functions: exercises

9. Recurrence Equations

IntroductionLinear Recurrence EquationsAdvancement OperatorsSolving advancement operator equationsFormalizing our approach to recurrence equationsUsing generating functions to solve recurrencesSolving a nonlinear recurrenceDiscussionRecurrence Equations: exercises

12. Graph Algorithms

Minimum Weight Spanning TreesDigraphsDijkstra's Algorithm for Shortest PathsHistorical NotesGraph Algorithms: exercises

13. Network Flows

Basic Notation and TerminologyFlows and CutsAugmenting PathsThe Ford-Fulkerson Labeling AlgorithmA Concrete ExampleInteger Solutions of Linear Programming ProblemsNetwork Flows: exercises

14. Combinatorial Applications of Network Flows

IntroductionMatchings in Bipartite GraphsChain partitioningCombinatorial Applications of Network Flows: exercises

15. Pólya's Enumeration Theorem

Coloring the Vertices of a SquarePermutation GroupsBurnside's LemmaPólya's TheoremApplications of Pólya's Enumeration FormulaPólya's Enumeration Theorem: exercises

16. The Many Faces of Combinatorics

On-line algorithmsExtremal Set TheoryMarkov ChainsThe Stable Matching TheoremZeroOne MatricesArithmetic CombinatoricsThe Lovász Local LemmaApplying the Local Lemma

Chapters from Levin, Discrete Mathematics: An Open Introduction

Every section of the book, condensed into a lesson with its own practice problems.

3. Graph Theory

Problems and DefinitionsTreesPlanar GraphsEuler Trails and CircuitsColoringRelations and GraphsMatching in Bipartite GraphsChapter Summary

4. Counting

Pascal's Arithmetical TriangleCombining OutcomesNon-Disjoint OutcomesCombinations and PermutationsCounting MultisetsCombinatorial ProofsApplications to ProbabilityAdvanced Counting Using PIEChapter Summary

Chapters from OpenStax Contemporary Mathematics

Every section of the book, condensed into a lesson with its own practice problems.

12. Graph Theory

Graph BasicsGraph StructuresComparing GraphsNavigating GraphsEuler CircuitsEuler TrailsHamilton CyclesHamilton PathsTraveling Salesperson Problem

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Ander takke

＋ Arithmetic𝑥 Algebra△ Geometry∿ Trigonometryƒ Precalculusσ Statistics & Probability⊢ Discrete Math & Logic∫ Calculus⊞ Linear Algebraℕ Number Theoryẏ Differential Equations∇ Multivariable Calculusε Real Analysis∈ Set Theory & Logic𝔾 Abstract Algebra𝑃 Probability Theory≈ Numerical Methodsℂ Complex Analysis◎ Topologyμ Measure Theory‖·‖ Functional Analysisκ Differential Geometryπ₁ Algebraic Topology→ Category Theory∞ Frontiers