Introductory Combinatorics,9780121108304

Introductory Combinatorics

by
Edition: 3rd
ISBN13: 9780121108304
ISBN10: 0121108309
Format: Hardcover
Pub. Date: 2000-01-10
Publisher(s): Cengage Learning
Upgraded Edition: Click here!
  • Free Shipping Icon

    Free Shipping On Orders Over $59

    Free standard shipping on order over $59 to your home address. Marketplace purchases through third-party sellers are excluded from free shipping promotions.

List Price: $279.65

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $150.93

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.