Counting is often a choice of representation: the same objects can be described by subsets, recurrences, graphs or generating functions. Keller and Trotter provide a broad route across these descriptions. Stanley connects graph walks, trees and tableaux with algebra. Choose the broad route while learning basic counting arguments; choose the algebraic continuation when matrices and linear maps can help explain a combinatorial formula.
What to work on
Prove counting identities by a bijection or double count.
Use inclusion-exclusion with precisely defined events.
Encode counting sequences in ordinary generating functions.
Use degree counts, paths, cycles and trees in graph arguments.
A starting text
Applied Combinatorics, 2016 edition — Mitchel T. Keller and William T. Trotter. Read chapter 2, Strings, Sets, and Binomial Coefficients; chapter 5, Graph Theory; chapter 7, Inclusion-Exclusion; and chapter 8, Generating Functions. Chapter 9 continues to recurrence equations.
Choosing what to read
Explain what each side of a counting identity counts before simplifying algebra. For a recurrence, state the initial values and justify the decomposition producing it. Translate the recurrence into a generating function and recover several coefficients as a check. In graph theory, draw the small and disconnected cases before committing to a universal claim. Keep formal power series distinct from analytic convergence arguments; the calculation may require only coefficient identities, or it may need additional estimates.
Choose among bijections, inclusion-exclusion, recurrences and graph arguments.
How it reads
Broad introductory course in counting, graphs and generating functions.
What it expects
Proof-writing and elementary algebra.
What to keep in mind
Diagram-dependent exercises need the original pages; the existing extraction did not render every figure.
Practice
Practice page for this work at https://rellek.net/book-2016/s_strings_exercises.html: Public exercise text verified for counting and graphs. Public worked solutions not verified; graph figures were not rendered by the text extraction. Section 2.9 Exercises for counting; follow the Graph Theory chapter to section 5.9 Exercises, including exercise 6 on the edge count of a tree. Chapters 7-8 have their own exercise sets.
Complete public HTML text.
Edition, reading range and source
Read chapter 2, Strings, Sets, and Binomial Coefficients; chapter 5, Graph Theory; chapter 7, Inclusion-Exclusion; and chapter 8, Generating Functions. Chapter 9 continues to recurrence equations.
Connect adjacency-matrix powers with walk counts, then investigate the algebra behind trees and tableaux.
How it reads
Algebraic methods for enumerative questions, beginning with walks in graphs.
What it expects
Linear algebra; discrete mathematics.
What to keep in mind
The linked author draft is headed Topics in Algebraic Combinatorics; do not assume its pagination matches the published book.
Practice
Reconstruct the walk-counting proof of Theorem 1.1 and test it on a small graph as an editorial task. A Hints section is listed, but exercise-to-hint coverage was not audited.
MIT-hosted author draft, version of February 1, 2013; source title differs from the catalogue's published-book title.
Edition, reading range and source
In the linked 2013 draft, start with chapter 1, Walks in graphs, printed pp. 9-20. Chapter 9, The Matrix-Tree Theorem, and chapter 8, A glimpse of Young tableaux, are later branches.
Counting and graph exercises. Section 2.9 Exercises for counting; follow the Graph Theory chapter to section 5.9 Exercises, including exercise 6 on the edge count of a tree. Chapters 7-8 have their own exercise sets.. Public exercise text verified for counting and graphs. Public worked solutions not verified; graph figures were not rendered by the text extraction.
Try these before moving on
Try a proof or calculation before opening the hint. These solutions address the checks below, not the exercises in the linked textbooks.
Find an ordinary generating function for the number of binary strings of length n with no adjacent ones, starting with the empty string; derive its recurrence and initial values.
A hint
For n at least 2, partition strings by whether they end in 0 or in 01. Work with a formal power series so no analytic convergence assumption is needed.
Work through the solution
Let an count such strings. The empty string gives a0=1, and the strings 0,1 give a1=2. For n≥2, a valid string ending in 0 is obtained uniquely by appending 0 to a valid string of length n−1. A valid string ending in 1 must end in 01, and deleting that suffix gives a valid string of length n−2. These disjoint classes exhaust the strings, so an=an−1+an−2.
For the formal series A(x)=∑n≥0anxn, summing the recurrence from n=2 gives A−1−2x=x(A−1)+x2A. Thus
A(x)=1−x−x21+x.
The denominator has constant coefficient 1, hence is invertible as a formal power series. The first coefficients are 1,2,3,5,8, agreeing with the recurrence.
Abstract Algebra & Galois Theory — Review coefficient arithmetic in formal power series if manipulating generating functions is unfamiliar.
Already comfortable with this? Skip counting basics if you can give the double count and a valid inclusion-exclusion argument. Skip the generating-function and graph review only if you can derive the recurrence and tree proof without relying on memorized formulas.
A first introduction to counting and graph theory in a freely readable web format. Useful for building discrete proof techniques before specialized combinatorics.
Mitchel T. Keller and William T. Trotter · Textbook · Intermediate
Combines enumeration, graphs, posets and optimization. The breadth supports several course choices; the linked full HTML is the established 2016 edition.
A focused treatment of generating functions and counting. Read after elementary combinatorics; the authorized free edition is the second, not the commercial third.
Preparation: Combinatorics; power series and calculus.
Connects extremal graph theory, pseudorandomness and additive combinatorics. The full author manuscript differs slightly from the published edition; exercises and companion lectures support study.
Preparation: Undergraduate algebra, analysis and linear algebra.
Reinhard Diestel · Textbook · Advanced · English · Online text
The author offers free online viewing of the main text. Downloadable complete ebooks and exercise hints are separate paid editions; use the official page.
Covers core graph theory and routes toward structural results. Free browser viewing is not the same as a freely downloadable full PDF.
Preparation: Proof-writing; discrete mathematics.
Use: Bridge undergraduate graphs and graduate combinatorics.