Introduction to Combinatorics
1st Edition
Published on 2. September 2010
Book
Hardback
396 pages
978-1-4398-0622-7 (ISBN)
Description
Accessible to undergraduate students, Introduction to Combinatorics presents approaches for solving counting and structural questions. It looks at how many ways a selection or arrangement can be chosen with a specific set of properties and determines if a selection or arrangement of objects exists that has a particular set of properties.
To give students a better idea of what the subject covers, the authors first discuss several examples of typical combinatorial problems. They also provide basic information on sets, proof techniques, enumeration, and graph theory-topics that appear frequently throughout the book. The next few chapters explore enumerative ideas, including the pigeonhole principle and inclusion/exclusion. The text then covers enumerative functions and the relations between them. It describes generating functions and recurrences, important families of functions, and the theorems of Polya and Redfield. The authors also present introductions to computer algebra and group theory, before considering structures of particular interest in combinatorics: graphs, codes, Latin squares, and experimental designs. The last chapter further illustrates the interaction between linear algebra and combinatorics. Exercises and problems of varying levels of difficulty are included at the end of each chapter.
Ideal for undergraduate students in mathematics taking an introductory course in combinatorics, this text explores the different ways of arranging objects and selecting objects from a set. It clearly explains how to solve the various problems that arise in this branch of mathematics.
To give students a better idea of what the subject covers, the authors first discuss several examples of typical combinatorial problems. They also provide basic information on sets, proof techniques, enumeration, and graph theory-topics that appear frequently throughout the book. The next few chapters explore enumerative ideas, including the pigeonhole principle and inclusion/exclusion. The text then covers enumerative functions and the relations between them. It describes generating functions and recurrences, important families of functions, and the theorems of Polya and Redfield. The authors also present introductions to computer algebra and group theory, before considering structures of particular interest in combinatorics: graphs, codes, Latin squares, and experimental designs. The last chapter further illustrates the interaction between linear algebra and combinatorics. Exercises and problems of varying levels of difficulty are included at the end of each chapter.
Ideal for undergraduate students in mathematics taking an introductory course in combinatorics, this text explores the different ways of arranging objects and selecting objects from a set. It clearly explains how to solve the various problems that arise in this branch of mathematics.
Reviews / Votes
... thoughtfully written, contain[s] plenty of material and exercises ... provides numerous fragments of Mathematica code and this is a nice touch. ...-MAA Reviews, February 2011
More details
Series
Language
English
Place of publication
Washington
United States
Target group
College/higher education
Advanced undergraduate and graduate students and researchers in mathematics and computer science.
Illustrations
154 s/w Abbildungen
79 in text boxes; 154 Illustrations, black and white
Dimensions
Height: 234 mm
Width: 159 mm
Weight
685 gr
ISBN-13
978-1-4398-0622-7 (9781439806227)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Walter D. Wallis | John C. George
Introduction to Combinatorics
Book
01/2017
2nd Edition
Chapman & Hall/CRC
€159.50
Shipment within 15-20 days
Additional editions
Walter D. Wallis | John C. George
Introduction to Combinatorics
E-Book
09/2010
Chapman & Hall/CRC
€81.49
Available for download
Persons
W.D. Wallis is Emeritus Professor of Mathematics at Southern Illinois University. His research interests include combinatorial designs, Latin squares, graph labeling, one-factorizations, and intelligent networks. Dr. Wallis is the author of Introduction to Combinatorial Designs, Second Edition (CRC Press, 2007).
J.C. George is an assistant professor of mathematics in the Division of Mathematics and Natural Sciences at Gordon College in Barnesville, Georgia. His research interests include one-factorizations, graph products, and the relationships of algebraic structures to combinatorial objects.
J.C. George is an assistant professor of mathematics in the Division of Mathematics and Natural Sciences at Gordon College in Barnesville, Georgia. His research interests include one-factorizations, graph products, and the relationships of algebraic structures to combinatorial objects.
Content
Introduction
Some Combinatorial Examples
Sets, Relations and Proof Techniques
Two Principles of Enumeration
Graphs
Systems of Distinct Representatives
Fundamentals of Enumeration
Permutations and Combinations
Applications of P(n, k) and (n k)
Permutations and Combinations of Multisets
Applications and Subtle Errors
Algorithms
The Pigeonhole Principle and Ramsey's Theorem
The Pigeonhole Principle
Applications of the Pigeonhole Principle
Ramsey's Theorem - the Graphical Case
Ramsey Multiplicity
Sum-Free Sets
Bounds on Ramsey Numbers
The General Form of Ramsey's Theorem
The Principle of Inclusion and Exclusion
Unions of Events
The 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
Introduction
Catalan Numbers
Stirling Numbers of the Second Kind
Bell Numbers
Stirling Numbers of the First Kind
Computer Algebra and Other Electronic Systems
Symmetries and the Polya-Redfield Method
Introduction
Basics of Groups
Permutations and Colorings
An Important Counting Theorem
Polya and Redfield's Theorem
Introduction to Graph Theory
Degrees
Paths and Cycles in Graphs
Maps and Graph Coloring
Further Graph Theory
Euler Walks and Circuits
Application of Euler Circuits to Mazes
Hamilton Cycles
Trees
Spanning Trees
Coding Theory
Errors; Noise
The Venn Diagram Code
Binary Codes; Weight; Distance
Linear Codes
Hamming Codes
Codes and the Hat Problem
Variable-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 Designs
New Designs from Old
Difference Method
Linear Algebra Methods in Combinatorics
Recurrences Revisited
State Graphs and the Transfer Matrix Method
Kasteleyn's Permanent Method
Appendix 1: Sets; Proof Techniques
Appendix 2: Matrices and Vectors
Appendix 3: Some Combinatorial People
Solutions to Set A Exercises
Hints for Problems
Solutions to Problems
References
Index
Exercises and Problems appear at the end of each chapter.
Some Combinatorial Examples
Sets, Relations and Proof Techniques
Two Principles of Enumeration
Graphs
Systems of Distinct Representatives
Fundamentals of Enumeration
Permutations and Combinations
Applications of P(n, k) and (n k)
Permutations and Combinations of Multisets
Applications and Subtle Errors
Algorithms
The Pigeonhole Principle and Ramsey's Theorem
The Pigeonhole Principle
Applications of the Pigeonhole Principle
Ramsey's Theorem - the Graphical Case
Ramsey Multiplicity
Sum-Free Sets
Bounds on Ramsey Numbers
The General Form of Ramsey's Theorem
The Principle of Inclusion and Exclusion
Unions of Events
The 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
Introduction
Catalan Numbers
Stirling Numbers of the Second Kind
Bell Numbers
Stirling Numbers of the First Kind
Computer Algebra and Other Electronic Systems
Symmetries and the Polya-Redfield Method
Introduction
Basics of Groups
Permutations and Colorings
An Important Counting Theorem
Polya and Redfield's Theorem
Introduction to Graph Theory
Degrees
Paths and Cycles in Graphs
Maps and Graph Coloring
Further Graph Theory
Euler Walks and Circuits
Application of Euler Circuits to Mazes
Hamilton Cycles
Trees
Spanning Trees
Coding Theory
Errors; Noise
The Venn Diagram Code
Binary Codes; Weight; Distance
Linear Codes
Hamming Codes
Codes and the Hat Problem
Variable-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 Designs
New Designs from Old
Difference Method
Linear Algebra Methods in Combinatorics
Recurrences Revisited
State Graphs and the Transfer Matrix Method
Kasteleyn's Permanent Method
Appendix 1: Sets; Proof Techniques
Appendix 2: Matrices and Vectors
Appendix 3: Some Combinatorial People
Solutions to Set A Exercises
Hints for Problems
Solutions to Problems
References
Index
Exercises and Problems appear at the end of each chapter.