Applied Combinatorics and Problem Solving (MATH 3340) has a formal prerequisite of Mathematical Reasoning (MATH 3000). The catalog description is: "Covers topics that include basic counting techniques, generating functions, recurrence relations, and applications." These descriptions are based on the ETSU 2019-20 Undergraduate Catalog.

Copies of the classnotes are on the internet in PDF format as given below. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes and supplements have not been classroom tested (and so may have some typographical errors).

• Preface.
• Chapter 1. The Mathematics of Choice.
• Chapter 2. The Combinatorics of Finite Functions.
• Chapter 3. Pólya's Theory of Enumeration.
• Chapter 4. Generating Functions.
• Chapter 5. Enumeration in Graphs.
• Chapter 6. Codes and Designs.
• Appendices.

Preface. Preface notes

Chapter 1. The Mathematics of Choice.

• Section 1.1. The Fundamental Counting Principle. Section 1.1 notes
• Supplement. Proofs of Theorems in Section 1.1. Beamer file of Section 1.1 proofs
• Supplement. Printout of the Proofs of Theorems in Section 1.1. Print file of Section 1.1 proofs
• Section 1.2. Pascal's Triangle. Section 1.2 notes
• Supplement. Proofs of Theorems in Section 1.2. Beamer file of Section 1.2 proofs
• Supplement. Printout of the Proofs of Theorems in Section 1.2. Print file of Section 1.2 proofs
• Section 1.3. Elementary Probability. Section 1.3 notes
• Supplement. Proofs of Theorems in Section 1.3. Beamer file of Section 1.3 proofs
• Supplement. Printout of the Proofs of Theorems in Section 1.3. Print file of Section 1.3 proofs
• Section 1.4. Error-Correcting Codes.
• Section 1.5. Combinatorial Identities. Section 1.5 notes
• Section 1.6. Four Ways to Choose.
• Section 1.7. The Binomial and Multinomial Theorems.
• Section 1.8. Partitions.
• Section 1.9. Elementary Symmetric Functions.
• Section 1.10. Combinatorial Algorithms.
• Study Guide 1.

Chapter 2. The Combinatorics of Finite Functions.

• Section 2.1. Stirling Numbers of the Second Kind.
• Section 2.2. Bells, Balls, and Urns.
• Section 2.3. The Principle of Inclusion and Exclusion.
• Section 2.4. Disjoint Cycles.
• Section 2.5. Stirling Numbers of the First Kind.
• Study Guide 2.

Chapter 3. Pólya's Theory of Enumeration.

• Section 3.1. Function Composition.
• Section 3.2. Permutation Groups.
• Section 3.3. Burnside's Lemma.
• Section 3.4. Symmetry Groups.
• Section 3.5. Color Patterns.
• Section 3.6. Pólya's Theorem.
• Section 3.7. The Cycle Index Polynomial.
• Study Guide 3.

Chapter 4. Generating Functions.

• Section 4.1. Difference Sequances.
• Section 4.2. Ordinary Generating Functions.
• Section 4.3. Applications of Generating Functions.
• Section 4.4. Exponential Generating Functions.
• Section 4.5. Recursive Techniques.
• Study Guide 4.

Chapter 5. Enumeration in Graphs.

• Section 5.1. The Pigeonhole Principle.
• Section 5.2. Edge Colorings and Ramsey Theory.
• Section 5.3. Chromatic Polynomials.
• Section 5.4. Planar Graphs.
• Section 5.5. Matching Problems.
• Section 5.6. Oriented Graphs.
• Section 5.7. Graph Partitions.
• Study Guide 5.

Chapter 6. Codes and Design.

• Section 6.1. Linear Codes.
• Section 6.2. Decoding Algorithms.
• Section 6.3. Latin Squares.
• Section 6.4. Balanced Incomplete Block Designs.
• Study Guide 6.

Appendices.

• Appendix A1. Symmetric Polynomials.
• Appendix A2. Sorting Algorithms.
• Appendix A3. Matrix Theory.

Return to Bob Gardner's home page