Combinatorics

by Joy Morris

Read here Read at LibreTextsPDF

Combinatorics is an upper-level introductory course in enumeration, graph theory, and design theory. The text focuses on combinations and arrangements of discrete structures. There are five major branches of combinatorics that we will touch on in this course: enumeration, graph theory, Ramsey Theory, design theory, and coding theory. We will focus on enumeration, graph theory, and design theory, but will briefly introduce the other two topics.

Description from LibreTexts.

Publisher
University of Lethbridge
Subjects
Mathematics, Combinatorics and Discrete Mathematics
Licence
CC BY-NC-SA, as LibreTexts states it. Non-commercial use only.
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. 1: Introduction
  7. 1: What is Combinatorics?
  8. 1.1: Enumeration
  9. 1.2: Graph Theory
  10. 1.3: Ramsey Theory
  11. 1.4: Design Theory
  12. 1.5: Coding Theory
  13. 1.6: Summary
  14. 2: Enumeration
  15. 2: Basic Counting Techniques
  16. 2.1: The Product Rule
  17. 2.2: The Sum Rule
  18. 2.3: Putting Them Together
  19. 2.4: Summing Up
  20. 2.5: Summary
  21. 3: Permutations, Combinations, and the Binomial Theorem
  22. 3.1: Permutations
  23. 3.2: Combinations
  24. 3.3: The Binomial Theorem
  25. 3.4: Summary
  26. 4: Bijections and Combinatorial Proofs
  27. 4.1: Counting via Bijections
  28. 4.2: Combinatorial Proofs
  29. 4.3: Summary
  30. 5: Counting with Repetitions
  31. 5.1: Unlimited Repetition
  32. 5.2: Sorting a Set that Contains Repetition
  33. 5.3: Summary
  34. 6: Induction and Recursion
  35. 6.1: Recursively-Defined Sequences
  36. 6.2: Basic Induction
  37. 6.3: More Advanced Induction
  38. 6.4: Summary
  39. 7: Generating Functions
  40. 7.1: What is a Generating Function?
  41. 7.2: The Generalized Binomial Theorem
  42. 7.3: Using Generating Functions To Count Things
  43. 7.4: Summary
  44. 8: Generating Functions and Recursion
  45. 8.1: Partial Fractions
  46. 8.2: Factoring Polynomials
  47. 8.3: Using Generating Functions to Solve Recursively-Defined Sequences
  48. 8.4: Summary
  49. 9: Some Important Recursively-Defined Sequences
  50. 9.1: Derangements
  51. 9.2: Catalan Numbers
  52. 9.3: Bell Numbers and Exponential Generating Functions
  53. 9.4: Summary
  54. 10: Other Basic Counting Techniques
  55. 10.1: The Pigeonhole Principle
  56. 10.2: Inclusion-Exclusion
  57. 10.3: Summary
  58. 3: Graph Theory
  59. 11: Basics of Graph Theory
  60. 11.1: Background
  61. 11.2: Basic Definitions, Terminology, and Notation
  62. 11.3: Deletion, Complete Graphs, and the Handshaking Lemma
  63. 11.4: Graph Isomorphisms
  64. 11.5: Summary
  65. 12: Moving Through Graphs
  66. 12.1: Directed Graphs
  67. 12.2: Walks and Connectedness
  68. 12.3: Paths and Cycles
  69. 12.4: Trees
  70. 12.5: Summary
  71. 13: Euler and Hamilton
  72. 13.1: Euler Tours and Trails
  73. 13.2: Hamilton Paths and Cycles
  74. 13.3: Summary
  75. 14: Graph Coloring
  76. 14.1: Edge Coloring
  77. 14.2: Ramsey Theory
  78. 14.3: Vertex Colouring
  79. 14.4: Summary
  80. 15: Planar Graphs
  81. 15.1: Planar Graphs
  82. 15.2: Euler’s Formula
  83. 15.3: Map Colouring
  84. 15.4: Summary
  85. 4: Design Theory
  86. 16: Latin Squares
  87. 16.1: Latin Squares and Sudokus
  88. 16.2: Mutually Orthogonal Latin Squares (MOLS)
  89. 16.3: Systems of Distinct Representatives
  90. 16.4: Summary
  91. 17: Designs
  92. 17.1: Balanced Incomplete Block Designs (BIBD)
  93. 17.2: Constructing Designs and Existence of Designs
  94. 17.3: Fisher’s Inequality
  95. 17.4: Summary
  96. 18: More Designs
  97. 18.1: Steiner and Kirkman Triple Systems
  98. 18.2: t-Designs
  99. 18.3: Affine Planes
  100. 18.4: Projective Planes
  101. 18.5: Summary
  102. 19: Designs and Codes
  103. 19.1: Introduction
  104. 19.2: Error-Correcting Codes
  105. 19.3: Using the Generator Matrix For Encoding
  106. 19.4: Using the Parity-Check Matrix For Decoding
  107. 19.5: Codes From Designs
  108. 19.6: Summary
  109. Back Matter
  110. Index
  111. List of Notation
  112. Appendix A: Solutions To Selected Exercises
  113. Detailed Licensing