Introductory Combinatorics

by Brualdi, Richard A.

• ISBN13: 9780131814882
• ISBN10: 0131814885
• Edition: 3rd
• Format: Hardcover
• Copyright: 1999-01-01
• Publisher: Pearson College Div

Summary

Appropriate for an undergraduate junior/senior level mathematics course on combinatorics. This book emphasizes combinatorial ideas including the pigeon-hole principle, counting techniques, permutations and combinations, Polya counting, binomial coefficients, inclusion-exclusion principle, generating functions and recurrence relations, and combinatortial structures (matchings, designs, graphs).

Table of Contents

Preface	ix
Chapter 1. What is Combinatorics?	1	(26)
1.1 Example. Perfect covers of chessboards	4	(4)
1.2 Example. Cutting a cube	8	(2)
1.3 Example. Magic squares	10	(3)
1.4 Example. The 4-color problem	13	(1)
1.5 Example. The problem of the 36 officers	14	(2)
1.6 Example. Shortest-route problem	16	(2)
1.7 Example. The game of Nim	18	(3)
1.8 Exercises	21	(6)
Chapter 2. The Pigeonhole Principle	27	(18)
2.1 Pigeonhole principle: Simple form	27	(5)
2.2 Pigeonhole principle: Strong form	32	(4)
2.3 A theorem of Ramsey	36	(5)
2.4 Exercises	41	(4)
Chapter 3. Permutations and Combinations	45	(36)
3.1 Two basic counting principles	45	(8)
3.2 Permutations of sets	53	(7)
3.3 Combinations of sets	60	(4)
3.4 Permutations of multisets	64	(6)
3.5 Combinations of multisets	70	(5)
3.6 Exercises	75	(6)
Chapter 4. Generating Permutations and Combinations	81	(41)
4.1 Generating permutations	81	(6)
4.2 Inversions in permutations	87	(6)
4.3 Generating combinations	93	(16)
4.5 Partial orders and equivalence relations	109	(7)
4.6 Exercises	116	(6)
Chapter 5. The Binomial Coefficients	122	(37)
5.1 Pascal's formula	122	(5)
5.2 The binomial theorem	127	(3)
5.3 Identities	130	(7)
5.4 Unimodality of binomial coefficients	137	(6)
5.5 The multinomial theorem	143	(4)
5.6 Newton's binomial theorem	147	(2)
5.7 More on partially ordered sets	149	(3)
5.8 Exercises	152	(7)
Chapter 6. The Inclusion-Exclusion Principle and Applications	159	(31)
6.1 The inclusion-exclusion principle	159	(9)
6.2 Combinations with repetition	168	(4)
6.3 Derangements	172	(6)
6.4 Permutations with forbidden positions	178	(5)
6.5 Another forbidden position problem	183	(2)
6.6 Exercises	185	(5)
Chapter 7. Recurrence Relations and Generating Functions	190	(62)
7.1 Some number sequences	191	(11)
7.2 Linear homogeneous recurrence relations	202	(11)
7.3 Non-homogeneous recurrence relations	213	(7)
7.4 Generating functions	220	(7)
7.5 Recurrences and generating functions	227	(8)
7.6 A geometry example	235	(5)
7.7 Exponential generating functions	240	(6)
7.8 Exercises	246	(6)
Chapter 8. Special Counting Sequences	252	(42)
8.1 Catalan numbers	252	(9)
8.2 Difference sequences and Stirling numbers	261	(20)
8.3 Partition numbers	281	(4)
8.4 A geometric problem	285	(5)
8.5 Exercises	290	(4)
Chapter 9. Matchings in Bipartite Graphs	294	(43)
9.1 General problem formulation	295	(7)
9.2 Matchings	302	(17)
9.3 Systems of distinct representatives	319	(5)
9.4 Stable marriages	324	(8)
9.5 Exercises	332	(5)
Chapter 10. Combinatorial Designs	337	(63)
10.1 Modular arithmetic	337	(13)
10.2 Block designs	350	(12)
10.3 Steiner triple systems	362	(7)
10.4 Latin squares	369	(24)
10.5 Exercises	393	(7)
Chapter 11. Introduction to Graph Theory	400	(75)
11.1 Basic properties	401	(11)
11.2 Eulerian trails	412	(10)
11.3 Hamilton chains and cycles	422	(7)
11.4 Bipartite multigraphs	429	(7)
11.5 Trees	436	(7)
11.6 The Shannon switching game	443	(7)
11.7 More on trees	450	(13)
11.8 Exercises	463	(12)
Chapter 12. Digraphs and Networks	475	(26)
12.1 Digraphs	475	(13)
12.2 Networks	488	(8)
12.3 Exercises	496	(5)
Chapter 13. More on Graph Theory	501	(45)
13.1 Chromatic number	502	(12)
13.2 Plane and planar graphs	514	(5)
13.3 A 5-color theorem	519	(4)
13.4 Independence number and clique number	523	(10)
13.5 Connectivity	533	(7)
13.6 Exercises	540	(6)
Chapter 14. Polya Counting	546	(46)
14.1 Permutation and symmetry groups	547	(12)
14.2 Burnside's theorem	559	(7)
14.3 Polya's counting formula	566	(20)
14.4 Exercises	586	(6)
Answers and Hints to Exercises	592	(15)
Bibliography	607	(2)
Index	609