A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory

by Bona, Miklos

• ISBN13: 9789814335232
• ISBN10: 9814335231
• Edition: 3rd
• Format: Hardcover
• Copyright: 2011-06-30
• Publisher: World Scientific Pub Co Inc

Summary

This is a textbook for an introductory combinatorics course lasting one or two semesters. An extensive list of problems, ranging from routine exercises to research questions, is included. In each section, there are also exercises that contain material not explicitly discussed in the preceding text, so as to provide instructors with extra choices if they want to shift the emphasis of their course.

Author Biography

Mikls Bna received his Ph.D. at Massachusetts institute of Technology. He is a Professor of Mathematics at the University of Florida, where he has been inducted into the Academy of Distinguished Teaching Scholars. His research has been supported by the National Science Foundation, the National Security Agency, and the Howard Hughes Medical institute. Mikls Bna has received teaching awards at the University of Florida and at the University of Pennsylvania. He is one of the Editor-in-Chiefs of the Electronic Journal of Combinatorics.

Table of Contents

Foreword	p. vii
Preface	p. ix
Acknowledgments	p. xi
Basic Methods
Seven Is More Than Six. The Pigeon-Hole Principle	p. 1
The Basic Pigeon-Hole Principle	p. 1
The Generalized Pigeon-Hole Principle	p. 3
Exercises	p. 9
Supplementary Exercises	p. 11
Solutions to Exercises	p. 13
One Step at a Time. The Method of Mathematical Induction	p. 21
Weak Induction	p. 21
Strong Induction	p. 26
Exercises	p. 28
Supplementary Exercises	p. 30
Solutions to Exercises	p. 31
Enumerative Combinatorics
There Are A Lot Of Them. Elementary Counting Problems	p. 39
Permutations	p. 39
Strings over a Finite Alphabet	p. 42
Choice Problems	p. 45
Exercises	p. 49
Supplementary Exercises	p. 53
Solutions to Exercises	p. 55
No Matter How You Slice It. The Binomial Theorem and Related Identities	p. 67
The Binomial Theorem	p. 67
The Multinomial Theorem	p. 72
When the Exponent Is Not a Positive Integer	p. 74
Exercises	p. 76
Supplementary Exercises	p. 79
Solutions to Exercises	p. 82
Divide and Conquer. Partitions	p. 93
Compositions	p. 93
Set Partitions	p. 95
Integer Partitions	p. 98
Exercises	p. 105
Supplementary Exercises	p. 106
Solutions to Exercises	p. 108
Not So Vicious Cycles. Cycles in Permutations	p. 113
Cycles in Permutations	p. 114
Permutations with Restricted Cycle Structure	p. 120
Exercises	p. 124
Supplementary Exercises	p. 126
Solutions to Exercises	p. 129
You Shall Not Overcount. The Sieve	p. 135
Enumerating The Elements of Intersecting Sets	p. 135
Applications of the Sieve Formula	p. 138
Exercises	p. 142
Supplementary Exercises	p. 143
Solutions to Exercises	p. 144
A Function Is Worth Many Numbers. Generating Functions	p. 149
Ordinary Generating Functions	p. 149
Recurrence Relations and Generating Functions	p. 149
Products of Generating Functions	p. 156
Compositions of Generating Functions	p. 163
Exponential Generating Functions	p. 166
Recurrence Relations and Exponential Generating Functions	p. 166
Products of Exponential Generating Functions	p. 168
Compositions of Exponential Generating Functions	p. 171
Exercises	p. 174
Supplementary Exercises	p. 176
Solutions to Exercises	p. 178
Graph Theory
Dots and Lines. The Origins of Graph Theory	p. 189
The Notion of Graphs. Eulerian Trails	p. 189
Hamiltonian Cycles	p. 194
Directed Graphs	p. 196
The Notion of Isomorphisms	p. 199
Exercises	p. 202
Supplementary Exercises	p. 205
Solutions to Exercises	p. 208
Staying Connected. Trees	p. 215
Minimally Connected Graphs	p. 215
Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm	p. 221
Graphs and Matrices	p. 225
Adjacency Matrices of Graphs	p. 225
The Number of Spanning Trees of a Graph	p. 228
Exercises	p. 233
Supplementary Exercises	p. 236
Solutions to Exercises	p. 238
Finding A Good Match. Coloring and Matching	p. 247
Introduction	p. 247
Bipartite Graphs	p. 249
Matchings in Bipartite Graphs	p. 254
More Than Two Color	p. 260
Matchings in Graphs That Are Not Bipartite	p. 262
Exercises	p. 266
Supplementary Exercises	p. 267
Solutions to Exercises	p. 269
Do Not Cross. Planar Graphs	p. 275
Euler's Theorem for Planar Graphs	p. 275
Polyhedra	p. 278
Coloring Maps	p. 285
Exercises	p. 287
Supplementary Exercises	p. 288
Solutions to Exercises	p. 290
Horizons
Does It Clique? Ramsey Theory	p. 293
Ramsey Theory for Finite Graphs	p. 293
Generalizations of the Ramsey Theorem	p. 298
Exercises	p. 304
Supplementary Exercises	p. 305
Solutions to Exercises	p. 307
So Hard To Avoid. Subsequence Conditions on Permutations	p. 313
Pattern Avoidance	p. 313
Stack Sortable Permutations	p. 322
Exercises	p. 334
Supplementary Exercises	p. 335
Solutions to Exercises	p. 338
Who Knows What It Looks Like, But It Exists. The Probabilistic Method	p. 349
The Notion of Probability	p. 349
Non-constructive Proofs	p. 352
Independent Events	p. 355
The Notion of Independence and Bayes' Theorem	p. 355
More Than Two Events	p. 359
Expected Values	p. 360
Linearity of Expectation	p. 361
Existence Proofs Using Expectation	p. 364
Conditional Expectation	p. 365
Exercises	p. 367
Supplementary Exercises	p. 370
Solutions to Exercises	p. 373
At Least Some Order. Partial Orders and Lattices	p. 381
The Notion of Partially Ordered Sets	p. 381
The Möbius Function of a Poset	p. 387
Lattices	p. 394
Exercises	p. 401
Supplementary Exercises	p. 403
Solutions to Exercises	p. 406
As Evenly As Possible. Block Designs and Error Correcting Codes	p. 413
Introduction	p. 413
Moto-cross Races	p. 413
Incompatible Computer Programs	p. 415
Balanced Incomplete Block Designs	p. 417
New Designs From Old	p. 419
Existence of Certain BIBDs	p. 424
A Derived Design of a Projective Plane	p. 426
Codes and Designs	p. 427
Coding Theory	p. 427
Error Correcting Codes	p. 427
Formal Definitions on Codes	p. 429
Exercises	p. 436
Supplementary Exercises	p. 438
Solutions to Exercises	p. 440
Are They Really Different? Counting Unlabeled Structures	p. 447
Enumeration Under Group Action	p. 447
Introduction	p. 447
Groups	p. 448
Permutation Groups	p. 450
Counting Unlabeled Trees	p. 457
Counting Rooted Non-plane 1-2 trees	p. 457
Counting Rooted Non-plane Trees	p. 460
Counting Unrooted Trees	p. 463
Exercises	p. 469
Supplementary Exercises	p. 472
Solutions to Exercises	p. 474
The Sooner The Better Combinatorial Algorithms	p. 481
In Lieu of Definitions	p. 481
The Halting Problem	p. 482
Sorting Algorithms	p. 483
BubbleSort	p. 483
MergeSort	p. 486
Comparing the Growth of Functions	p. 490
Algorithms on Graphs	p. 491
Minimum-cost Spanning Trees, Revisited	p. 491
Finding the Shortest Path	p. 495
Exercises	p. 500
Supplementary Exercises	p. 502
Solutions to Exercises	p. 503
Does Many Mean More Than One? Computational Complexity	p. 509
Turing Machines	p. 509
Complexity Classes	p. 512
The Class P	p. 512
The Class NP	p. 514
NP-complete Problems	p. 521
Other Complexity Classes	p. 526
Exercises	p. 529
Supplementary Exercises	p. 531
Solutions to Exercises	p. 532
Bibliography	p. 537
Index	p. 541
Table of Contents provided by Ingram. All Rights Reserved.