Introduction to Combinatorics

W.D. Wallis is Professor Emeritus of Southern Illiniois University. John C George is Asscoiate Professor at Gordon State College.

In Introduction to Combinatorics, Wallis (emer., Southern Illinois Univ.) and George (Gordon State College) present a well-thought-out compilation of topics covering elementary combinatorics. At the beginning, the authors present a thorough background on the fundamentals of combinatorics with topics such as permutations and combinations, the pigeonhole principle, and the principle of inclusion and exclusion. Later chapters are independent of one another and can be selected based on student and instructor interests. These topics include graph theory, coding theory, and balanced incomplete block designs. At the end of each chapter, there are exercises and problems. These vary in difficulty from straightforward practice to more involved proof problems. Solutions and/or hints are provided in the back of the book. In addition, three appendixes discuss proof techniques, matrices and vectors, and historical figures; these allow flexibility in covering the material in various ways that can be based on students’ backgrounds. Overall, this textbook is a highly readable work that will benefit and enlighten all those interested in learning about combinatorics. It will work in a traditional classroom setting and for independent study. Given the level of material, it is geared toward junior or senior level undergraduate students.--S. L. Sullivan, Catawba College

• Introduction Some Combinatorial ExamplesSets, Relations and Proof TechniquesTwo Principles of Enumeration Graphs Systems of Distinct Representatives Fundamentals of EnumerationPermutations and Combinations Applications of P(n, k) and (n k)□Permutations and Combinations of Multisets Applications and Subtle Errors Algorithms Probability Introduction Some Definitions and Easy Examples Events and ProbabilitiesThree Interesting Examples Probability Models Bernoulli Trials The Probabilities in PokerThe Wild Card Poker Paradox The Pigeonhole Principle and Ramsey’s TheoremThe Pigeonhole PrincipleApplications of the Pigeonhole Principle Ramsey’s Theorem — the Graphical Case Ramsey Multiplicity Sum-Free SetsBounds on Ramsey Numbers The General Form of Ramsey’s Theorem The Principle of Inclusion and Exclusion Unions of EventsThe Principle Combinations with Limited Repetitions Derangements Generating Functions and Recurrence Relations Generating Functions Recurrence Relations From Generating Function to Recurrence Exponential Generating Functions Catalan, Bell and Stirling Numbers IntroductionCatalan Numbers Stirling Numbers of the Second Kind Bell NumbersStirling Numbers of the First KindComputer Algebra and Other Electronic Systems Symmetries and the P´olya-Redfield MethodIntroduction Basics of GroupsPermutations and ColoringsAn Important Counting TheoremP´olya and Redfield’s Theorem Partially-Ordered SetsIntroduction Examples and DefinitionsBounds and lattices Isomorphism and Cartesian products Extremal set theory: Sperner’s and Dilworth’s theorems Introduction to Graph TheoryDegrees Paths and Cycles in Graphs Maps and Graph Coloring Further Graph Theory Euler Walks and Circuits Application of Euler Circuits to MazesHamilton Cycles TreesSpanning Trees Coding TheoryErrors; Noise The Venn Diagram CodeBinary Codes; Weight; Distance Linear CodesHamming CodesCodes and the Hat ProblemVariable-Length Codes and Data Compression Latin Squares Introduction Orthogonality Idempotent Latin Squares Partial Latin Squares and Subsquares Applications Balanced Incomplete Block Designs Design Parameters Fisher’s Inequality Symmetric Balanced Incomplete Block DesignsNew Designs from Old Difference Methods Linear Algebra Methods in Combinatorics Recurrences Revisited State Graphs and the Transfer Matrix Method Kasteleyn’s Permanent Method Appendix 1: Sets; Proof Techniques7Appendix 2: Matrices and Vectors Appendix 3: Some Combinatorial People