Introductory Combinatorics

by Bogart, Kenneth P.

• ISBN13: 9780121108304
• ISBN10: 0121108309
• Edition: 3rd
• Format: Hardcover
• Copyright: 2000-01-10
• Publisher: Cengage Learning

Summary

Focusing on the core material of value to students in a wide variety of fields, this book presents a broad comprehensive survey of modern combinatorics at an introductory level. The author begins with an introduction of concepts fundamental to all branches of combinatorics in the context of combinatorial enumeration. Chapter 2 is devoted to enumeration problems that involve counting the number of equivalence classes of an equivalence relation. Chapter 3 discusses somewhat less direct methods of enumeration, the principle of inclusion and exclusion and generating functions. The remainder of the book is devoted to a study of combinatorial structures.

Table of Contents

Preface	v
An Introduction to Enumeration
Section 1 Elementary Counting Principles	1	(13)
What Is Combinatorics?	1	(1)
The Sum Principle	1	(2)
The Product Principle	3	(1)
Ordered Pairs	4	(1)
Cartesian Product of Sets	4	(1)
The General Form of the Product Principle	4	(1)
Lists with Distinct Elements	5	(2)
Lists with Repeats Allowed	7	(1)
Stirling's Approximation for n!	7	(1)
Exercises	8	(6)
Section 2 Functions and the Pigeonhole Principle	14	(13)
Functions	14	(1)
Relations	15	(1)
Definition of Function	15	(1)
The Number of Functions	16	(1)
One-to-One Functions	16	(2)
Onto Functions and Bijections	18	(2)
The Extended Pigeonhole Principle	20	(1)
Ramsey Numbers	21	(1)
*Using Functions to Describe Ramsey Numbers	22	(1)
Exercises	23	(4)
Section 3 Subsets	27	(13)
The Number of Subsets of a Set	27	(1)
Binomial Coefficients	28	(1)
k-Element Subsets	29	(1)
Labelings with Two Labels	29	(1)
Pascal's Triangle	30	(3)
How Fast Does the Number of Subsets Grow?	33	(1)
Recursion and Iteration	34	(1)
Exercises	35	(5)
Section 4 Using Binomial Coefficients	40	(14)
The Binomial Theorem	40	(3)
Multinomial Coefficients	43	(2)
The Multinomial Theorem	45	(1)
Multinomial Coefficients from Binomial Coefficients	46	(1)
Lattice Paths	46	(4)
Exercises	50	(4)
Section 5 Mathematical Induction	54	(15)
The Principle of Induction	54	(1)
Proving That Formulas Work	54	(2)
Informal Induction Proofs	56	(1)
Inductive Definition	56	(2)
The General Sum Principle	58	(1)
An Application to Computing	59	(1)
Proving That a Recurrence Works	60	(1)
A Sample of the Strong Form of Mathematical Induction	61	(1)
Double Induction	62	(1)
*Ramsey Numbers	62	(2)
Exercises	64	(4)
Suggested Reading for Chapter 1	68	(1)
Equivalence Relations, Partitions, and Multisets
Section 1 Equivalence Relations	69	(14)
The Idea of Equivalence	69	(1)
Equivalence Relations	70	(1)
Circular Arrangements	70	(2)
Equivalence Classes	72	(1)
Counting Equivalence Classes	73	(1)
The Inverse Image Relation	74	(3)
The Number of Partitions with Specified Class Sizes	77	(2)
Exercises	79	(4)
Section 2 Distributions and Multisets	83	(16)
The Idea of a Distribution	83	(4)
Ordered Distributions	87	(2)
Distributing Identical Objects to Distinct Recipients	89	(3)
Ordered Compositions	92	(1)
Multisets	93	(1)
Broken Permutations of a Set	94	(2)
Exercises	96	(3)
Section 3 Partitions and Stirling Numbers	99	(11)
Partitions of an m-Element Set into n Classes	99	(1)
Stirling's Triangle of the Second Kind	99	(1)
The Inverse Image Partition of a Function	100	(1)
Onto Functions and Stirling Numbers	101	(1)
Stirling Numbers of the First Kind	101	(1)
Stirling Numbers of the Second Kind as Polynomial Coefficients	102	(2)
Stirling's Triangle of the First Kind	104	(1)
The Total Number of Partitions of a Set	105	(1)
Exercises	106	(4)
Section 4 Partitions of Integers	110	(9)
Distributing Identical Objects to Identical Recipients	110	(1)
Type Vector of a Partition and Decreasing Lists	110	(1)
The Number of Partitions of m into n Parts	111	(1)
Ferrers Diagrams	112	(1)
Conjugate Partitions	112	(2)
The Total Number of Partitions of m	114	(1)
Exercises	115	(3)
Suggested Reading for Chapter 2	118	(1)
Algebraic Counting Techniques
Section 1 The Principle of Inclusion and Exclusion	119	(19)
The Size of a Union of Three Overlapping Sets	119	(1)
The Number of Onto Functions	120	(2)
Counting Arrangements with or without Certain Properties	122	(1)
The Basic Counting Functions N≥ and N=	123	(1)
The Principle of Inclusion and Exclusion	124	(2)
Onto Functions and Stirling Numbers	126	(1)
Examples of Using the Principle of Inclusion and Exclusion	127	(4)
Derangements	131	(1)
*Level Sums and Inclusion--Exclusion Counting	131	(2)
*Examples of Level Sum Inclusion and Exclusion	133	(1)
Exercises	134	(4)
Section 2 The Concept of a Generating Function	138	(16)
Symbolic Series	138	(5)
Power Series	143	(1)
What Is a Generating Function?	144	(1)
The Product Principle for Generating Functions	145	(1)
The Generating Function for Multisets	146	(1)
Polynomial Generating Functions	147	(1)
Extending the Definition of Binomial Coefficients	148	(1)
The Extended Binomial Theorem	148	(1)
Exercises	149	(5)
Section 3 Applications to Partitions and Inclusion--Exclusion	154	(15)
Polya's Change-Making Example	154	(1)
Systems of Linear Recurrences from Products of Geometric Series	155	(3)
Generating Functions for Integer Partitions	158	(4)
Generating Functions Some-times Replace Inclusion--Exclusion	162	(1)
*Generating Functions and Inclusion--Exclusion on Level Sums	163	(2)
Exercises	165	(4)
Section 4 Recurrence Relations and Generating Functions	169	(15)
The Idea of a Recurrence Relation	169	(1)
How Generating Functions Are Relevant	170	(2)
Second-Order Linear Recurrence Relations	172	(5)
The Original Fibonacci Problem	177	(1)
General Techniques	178	(2)
Exercises	180	(4)
Section 5 Exponential Generating Functions	184	(16)
Indicator Functions	184	(1)
Exponential Generating Functions	184	(1)
Products of Exponential Generating Functions	185	(3)
The Exponential Generating Function for Onto Functions	188	(1)
The Product Principle for Exponential Generating Functions	189	(1)
Putting Lists Together and Preserving Order	190	(2)
Exponential Generating Functions for Words	192	(1)
Solving Recurrence Relations with Other Generating Functions	193	(1)
Using Calculus with Exponential Generating Functions	194	(2)
Exercises	196	(2)
Suggested Reading for Chapter 3	198	(2)
Graph Theory
Section 1 Eulerian Walks and the Idea of Graphs	200	(11)
The Concept of a Graph	200	(2)
Multigraphs and the Konigsberg Bridge Problem	202	(2)
Walks, Paths, and Connectivity	204	(2)
Eulerian Graphs	206	(2)
Exercises	208	(3)
Section 2 Trees	211	(15)
The Chemical Origins of Trees	211	(1)
Basic Facts about Trees	212	(3)
Spanning Trees	215	(2)
*The Number of Trees	217	(5)
Exercises	222	(4)
Section 3 Shortest Paths and Search Trees	226	(16)
Rooted Trees	226	(2)
Breadth-First Search Trees	228	(1)
Shortest Path Spanning Trees	229	(2)
Bridges	231	(1)
Depth-First Search	232	(1)
Depth-First Numbering	233	(1)
Finding Bridges	234	(1)
*An Efficient Bridge-Finding Algorithm for Computers	235	(1)
Backtracking	235	(2)
Decision Graphs	237	(1)
Exercises	238	(4)
Section 4 Isomorphism and Planarity	242	(10)
The Concept of Isomorphism	242	(1)
Checking Whether Two Graphs Are Isomorphic	243	(2)
Planarity	245	(1)
Euler's Formula	246	(1)
An Inequality to Check for Nonplanarity	246	(3)
Exercises	249	(3)
Section 5 Digraphs	252	(11)
Directed Graphs	252	(1)
Walks and Connectivity	253	(1)
Tournament Digraphs	253	(1)
Hamiltonian Paths	254	(1)
Transitive Closure	255	(1)
Reachability	256	(1)
Modifying Breadth-First Search for Strict Reachability	257	(1)
Orientable Graphs	258	(1)
Graphs without Bridges Are Orientable	258	(1)
Exercises	259	(4)
Section 6 Coloring	263	(14)
The Four-Color Theorem	263	(1)
Chromatic Number	263	(1)
Maps and Duals	264	(1)
The Five-Color Theorem	265	(3)
Kempe's Attempted Proof	268	(1)
Using Backtracking to Find a Coloring	269	(3)
Exercises	272	(5)
Section 7 Graphs and Matrices	277	(14)
Adjacency Matrix of a Graph	277	(1)
Matrix Powers and Walks	277	(2)
Connectivity and Transitive Closure	279	(1)
Boolean Operations	280	(1)
*The Matrix-Tree Theorem	281	(3)
*The Number of Eulerian Walks in a Digraph	284	(1)
Exercises	285	(5)
Suggested Reading for Chapter 4	290	(1)
Matching and Optimization
Section 1 Matching Theory	291	(23)
The Idea of Matching	291	(3)
Making a Bigger Matching	294	(1)
A Procedure for Finding Alternating Paths in Bipartite Graphs	295	(1)
Constructing Bigger Matchings	296	(1)
Testing for Maximum-Sized Matchings by Means of Vertex Covers	297	(2)
Hall's ``Marriage'' Theorem	299	(1)
Term Rank and Line Covers of Matrices	300	(1)
Permutation Matrices and the Birkhoff-von Neumann Theorem	301	(1)
*Finding Alternating Paths in Nonbipartite Graphs	302	(6)
Exercises	308	(6)
Section 2 The Greedy Algorithm	314	(14)
The SDR Problem with Representatives That Cost Money	314	(1)
The Greedy Method	314	(2)
The Greedy Algorithm	316	(1)
Matroids Make the Greedy Algorithm Work	316	(2)
How Much Time Does the Algorithm Take?	318	(2)
The Greedy Algorithm and Minimum-Cost Independent Sets	320	(1)
The Forest Matroid of a Graph	321	(1)
Minimum-Cost Spanning Trees	322	(2)
Exercises	324	(4)
Section 3 Network Flows	328	(17)
Transportation Networks	328	(1)
The Concept of Flow	328	(2)
Cuts in Networks	330	(2)
Flow-Augmenting Paths	332	(1)
The Labeling Algorithm for Finding Flow-Augmenting Paths	333	(3)
The Max-Flow Min-Cut Theorem	336	(1)
*More Efficient Algorithms	337	(3)
Exercises	340	(5)
Section 4 Flows, Connectivity, and Matching	345	(14)
Connectivity and Menger's Theorem	345	(3)
Flows, Matchings, and Systems of Distinct Representatives	348	(2)
Minimum-Cost SDRs	350	(2)
Minimum-Cost Matchings and Flows with Edge Costs	352	(1)
The Potential Algorithm for Finding Minimum-Cost Paths	353	(1)
Finding a Maximum Flow of Minimum Cost	354	(2)
Exercises	356	(2)
Suggested Reading for Chapter 5	358	(1)
Combinatorial Designs
Section 1 Latin Squares and Graeco-Latin Squares	359	(20)
How Latin Squares Are Used	359	(1)
Randomization for Statistical Purposes	360	(2)
Orthogonal Latin Squares	362	(1)
Euler's 36-Officers Problem	363	(1)
Congruence Modulo an Integer n	363	(2)
Using Arithmetic Modulo n to Construct Latin Squares	365	(2)
Orthogonality and Arithmetic Modulo n	367	(1)
Compositions of Orthogonal Latin Squares	368	(4)
Orthogonal Arrays and Latin Squares	372	(3)
*The Construction of a 10 by 10 Graeco-Latin Square	375	(2)
Exercises	377	(2)
Section 2 Block Designs	379	(12)
How Block Designs Are Used	379	(1)
Basic Relationships among the Parameters	380	(1)
The Incidence Matrix of a Design	381	(2)
An Example of a BIBD	383	(1)
Isomorphism of Designs	383	(1)
The Dual of a Design	384	(1)
Symmetric Designs	385	(2)
The Necessary Conditions Need Not Be Sufficient	387	(1)
Exercises	388	(3)
Section 3 Construction and Resolvability of Designs	391	(18)
A Problem That Requires a Big Design	391	(1)
Cyclic Designs	391	(4)
Resolvable Designs	395	(1)
∞-Cyclic Designs	396	(1)
Triple Systems	397	(1)
Kirkman's Schoolgirl Problem	398	(1)
Constructing New Designs from Old	399	(1)
Complementary Designs	400	(1)
Unions of Designs	401	(1)
Product Designs	402	(1)
Composition of Designs	402	(1)
*The Construction of Kirkman Triple Systems	403	(3)
Exercises	406	(3)
Section 4 Affine and Projective Planes	409	(15)
Affine Planes	409	(3)
Postulates for Affine Planes	412	(2)
The Concept of a Projective Plane	414	(3)
Basic Facts about Projective Planes	417	(1)
Projective Planes and Block Designs	418	(1)
Planes and Resolvable Designs	419	(1)
Planes and Orthogonal Latin Squares	420	(2)
Exercises	422	(2)
Section 5 Codes and Designs	424	(18)
The Concept of an Error-Correcting Code	424	(1)
Hamming Distance	425	(2)
Perfect Codes	427	(2)
Linear Codes	429	(2)
The Hamming Codes	431	(2)
Constructing Designs from Codes	433	(1)
Highly Balanced Designs	434	(1)
t-Designs	435	(1)
Codes and Latin Squares	436	(2)
Exercises	438	(2)
Suggested Reading for Chapter 6	440	(2)
Ordered Sets
Section 1 Partial Orderings	442	(16)
What Is an Ordering?	442	(2)
Linear Orderings	444	(1)
Maximal and Minimal Elements	445	(1)
The Diagram and Covering Graph	446	(3)
Ordered Sets as Transitive Closures of Digraphs	449	(1)
Trees as Ordered Sets	449	(1)
Weak Orderings	450	(1)
Interval Orders	451	(3)
Exercises	454	(4)
Section 2 Linear Extensions and Chains	458	(19)
The Idea of a Linear Extension	458	(1)
Dimension of an Ordered Set	459	(1)
Topological Sorting Algorithms	460	(1)
Chains in Ordered Sets	460	(2)
Chain Decompositions of Posets	462	(2)
Finding Chain Decompositions	464	(3)
Alternating Walks	467	(3)
Finding Alternating Walks	470	(1)
Exercises	471	(6)
Section 3 Lattices	477	(11)
What Is a Lattice?	477	(2)
The Partition Lattice	479	(2)
The Bond Lattice of a Graph	481	(1)
The Algebraic Description of Lattices	482	(2)
Exercises	484	(4)
Section 4 Boolean Algebras	488	(17)
The Idea of a Complement	488	(2)
Boolean Algebras	490	(1)
Boolean Algebras of Statements	491	(3)
Combinatorial Gate Networks	494	(2)
Boolean Polynomials	496	(1)
DeMorgan's Laws	496	(1)
Disjunctive Normal Form	497	(2)
All Finite Boolean Algebras Are Subset Lattices	499	(2)
Exercises	501	(4)
Section 5 Mobius Functions	505	(18)
A Review of Inclusion and Exclusion	505	(1)
The Zeta Matrix	506	(2)
The Mobius Matrix	508	(1)
The Mobius Function	509	(2)
Equations That Describe the Mobius Function	511	(2)
The Number-Theoretic Mobius Function	513	(2)
The Number of Connected Graphs	515	(2)
A General Method of Computing Mobius Functions of Lattices	517	(1)
The Mobius Function of the Partition Lattice	518	(1)
Exercises	519	(4)
Section 6 Products of Orderings	523	(9)
The Idea of a Product	523	(1)
Products of Ordered Sets and Mobius Functions	524	(2)
Products of Ordered Sets and Dimension	526	(2)
Width and Dimension of Ordered Sets	528	(1)
Exercises	529	(2)
Suggested Reading for Chapter 7	531	(1)
Enumeration under Group Action
Section 1 Permutation Groups	532	(13)
Permutations and Equivalence Relations	532	(3)
The Group Properties	535	(2)
Powers of Permutations	537	(1)
Permutation Groups	538	(1)
Associating a Permutation with a Geometric Motion	539	(1)
Abstract Groups	540	(2)
Exercises	542	(3)
Section 2 Groups Acting on Sets	545	(17)
Groups Acting on Sets	545	(2)
Orbits as Equivalence Classes	547	(1)
The Subgroup Fixing a Point and Cosets	548	(3)
The Size of a Subgroup	551	(1)
The Subgroup Generated by a Set	552	(1)
The Cycles of a Permutation	553	(4)
Exercises	557	(5)
Section 3 Polya's Enumeration Theorem	562	(19)
The Cauchy--Frobenius--Burnside Theorem	562	(2)
Enumerators of Colorings	564	(2)
Generating Functions for Orbits	566	(2)
Using the Orbit--Fixed Point Lemma	568	(2)
Orbits of Functions	570	(2)
The Orbit Enumerator for Functions	572	(1)
How Cycle Structure Interacts with Colorings	573	(2)
The Polya--Redfield Theorem	575	(3)
Exercises	578	(2)
Suggested Reading for Chapter 8	580	(1)
Answers to Exercises	581	(61)
Index	642