Introduction to Combinatorics

What Is Combinatorics Anyway?Broadly speaking, combinatorics is the branch of mathematics dealingwith different ways of selecting objects from a set or arranging objects. Ittries to answer two major kinds of questions, namely, counting questions: how many ways can a selection or arrangement be chosen with a particular set of properties; and structural questions: does there exist a selection or arrangement of objects with a particular set of properties?The authors have presented a text for students at all levels of preparation.For some, this will be the first course where the students see several real proofs. Others will have a good background in linear algebra, will have completed the calculus stream, and will have started abstract algebra. The text starts by briefly discussing several examples of typical combinatorial problemsto give the reader a better idea of what the subject covers. The nextchapters explore enumerative ideas and also probability. It then moves on toenumerative functions and the relations between them, and generating functions and recurrences.,Important families of functions, or numbers and then theorems are presented. Brief introductions to computer algebra and group theory come next. Structures of particular interest in combinatorics: posets, graphs, codes, Latin squares, and experimental designs follow. Theauthors conclude with further discussion of the interaction between linear algebraand combinatorics.FeaturesTwo new chapters on probability and posets. Numerous new illustrations, exercises, and problems.More examples on current technology use A thorough focus on accuracyThree appendices: sets, induction and proof techniques, vectors and matrices, and biographies with historical notes, Flexible use of MapleTM and MathematicaTM

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 ParametersFisher’s Inequality Symmetric Balanced Incomplete Block DesignsNew Designs from OldDifference Methods Linear Alge

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