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

  • ISBN13:


  • ISBN10:


  • Edition: 3rd
  • Format: Hardcover
  • Copyright: 2011-06-30
  • Publisher: World Scientific Pub Co Inc
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $110.00 Save up to $54.80
  • eBook
    Add to Cart


Supplemental Materials

What is included with this book?

  • The eBook copy of this book is not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.


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

Forewordp. vii
Prefacep. ix
Acknowledgmentsp. xi
Basic Methods
Seven Is More Than Six. The Pigeon-Hole Principlep. 1
The Basic Pigeon-Hole Principlep. 1
The Generalized Pigeon-Hole Principlep. 3
Exercisesp. 9
Supplementary Exercisesp. 11
Solutions to Exercisesp. 13
One Step at a Time. The Method of Mathematical Inductionp. 21
Weak Inductionp. 21
Strong Inductionp. 26
Exercisesp. 28
Supplementary Exercisesp. 30
Solutions to Exercisesp. 31
Enumerative Combinatorics
There Are A Lot Of Them. Elementary Counting Problemsp. 39
Permutationsp. 39
Strings over a Finite Alphabetp. 42
Choice Problemsp. 45
Exercisesp. 49
Supplementary Exercisesp. 53
Solutions to Exercisesp. 55
No Matter How You Slice It. The Binomial Theorem and Related Identitiesp. 67
The Binomial Theoremp. 67
The Multinomial Theoremp. 72
When the Exponent Is Not a Positive Integerp. 74
Exercisesp. 76
Supplementary Exercisesp. 79
Solutions to Exercisesp. 82
Divide and Conquer. Partitionsp. 93
Compositionsp. 93
Set Partitionsp. 95
Integer Partitionsp. 98
Exercisesp. 105
Supplementary Exercisesp. 106
Solutions to Exercisesp. 108
Not So Vicious Cycles. Cycles in Permutationsp. 113
Cycles in Permutationsp. 114
Permutations with Restricted Cycle Structurep. 120
Exercisesp. 124
Supplementary Exercisesp. 126
Solutions to Exercisesp. 129
You Shall Not Overcount. The Sievep. 135
Enumerating The Elements of Intersecting Setsp. 135
Applications of the Sieve Formulap. 138
Exercisesp. 142
Supplementary Exercisesp. 143
Solutions to Exercisesp. 144
A Function Is Worth Many Numbers. Generating Functionsp. 149
Ordinary Generating Functionsp. 149
Recurrence Relations and Generating Functionsp. 149
Products of Generating Functionsp. 156
Compositions of Generating Functionsp. 163
Exponential Generating Functionsp. 166
Recurrence Relations and Exponential Generating Functionsp. 166
Products of Exponential Generating Functionsp. 168
Compositions of Exponential Generating Functionsp. 171
Exercisesp. 174
Supplementary Exercisesp. 176
Solutions to Exercisesp. 178
Graph Theory
Dots and Lines. The Origins of Graph Theoryp. 189
The Notion of Graphs. Eulerian Trailsp. 189
Hamiltonian Cyclesp. 194
Directed Graphsp. 196
The Notion of Isomorphismsp. 199
Exercisesp. 202
Supplementary Exercisesp. 205
Solutions to Exercisesp. 208
Staying Connected. Treesp. 215
Minimally Connected Graphsp. 215
Minimum-weight Spanning Trees. Kruskal's Greedy Algorithmp. 221
Graphs and Matricesp. 225
Adjacency Matrices of Graphsp. 225
The Number of Spanning Trees of a Graphp. 228
Exercisesp. 233
Supplementary Exercisesp. 236
Solutions to Exercisesp. 238
Finding A Good Match. Coloring and Matchingp. 247
Introductionp. 247
Bipartite Graphsp. 249
Matchings in Bipartite Graphsp. 254
More Than Two Colorp. 260
Matchings in Graphs That Are Not Bipartitep. 262
Exercisesp. 266
Supplementary Exercisesp. 267
Solutions to Exercisesp. 269
Do Not Cross. Planar Graphsp. 275
Euler's Theorem for Planar Graphsp. 275
Polyhedrap. 278
Coloring Mapsp. 285
Exercisesp. 287
Supplementary Exercisesp. 288
Solutions to Exercisesp. 290
Does It Clique? Ramsey Theoryp. 293
Ramsey Theory for Finite Graphsp. 293
Generalizations of the Ramsey Theoremp. 298
Exercisesp. 304
Supplementary Exercisesp. 305
Solutions to Exercisesp. 307
So Hard To Avoid. Subsequence Conditions on Permutationsp. 313
Pattern Avoidancep. 313
Stack Sortable Permutationsp. 322
Exercisesp. 334
Supplementary Exercisesp. 335
Solutions to Exercisesp. 338
Who Knows What It Looks Like, But It Exists. The Probabilistic Methodp. 349
The Notion of Probabilityp. 349
Non-constructive Proofsp. 352
Independent Eventsp. 355
The Notion of Independence and Bayes' Theoremp. 355
More Than Two Eventsp. 359
Expected Valuesp. 360
Linearity of Expectationp. 361
Existence Proofs Using Expectationp. 364
Conditional Expectationp. 365
Exercisesp. 367
Supplementary Exercisesp. 370
Solutions to Exercisesp. 373
At Least Some Order. Partial Orders and Latticesp. 381
The Notion of Partially Ordered Setsp. 381
The Möbius Function of a Posetp. 387
Latticesp. 394
Exercisesp. 401
Supplementary Exercisesp. 403
Solutions to Exercisesp. 406
As Evenly As Possible. Block Designs and Error Correcting Codesp. 413
Introductionp. 413
Moto-cross Racesp. 413
Incompatible Computer Programsp. 415
Balanced Incomplete Block Designsp. 417
New Designs From Oldp. 419
Existence of Certain BIBDsp. 424
A Derived Design of a Projective Planep. 426
Codes and Designsp. 427
Coding Theoryp. 427
Error Correcting Codesp. 427
Formal Definitions on Codesp. 429
Exercisesp. 436
Supplementary Exercisesp. 438
Solutions to Exercisesp. 440
Are They Really Different? Counting Unlabeled Structuresp. 447
Enumeration Under Group Actionp. 447
Introductionp. 447
Groupsp. 448
Permutation Groupsp. 450
Counting Unlabeled Treesp. 457
Counting Rooted Non-plane 1-2 treesp. 457
Counting Rooted Non-plane Treesp. 460
Counting Unrooted Treesp. 463
Exercisesp. 469
Supplementary Exercisesp. 472
Solutions to Exercisesp. 474
The Sooner The Better Combinatorial Algorithmsp. 481
In Lieu of Definitionsp. 481
The Halting Problemp. 482
Sorting Algorithmsp. 483
BubbleSortp. 483
MergeSortp. 486
Comparing the Growth of Functionsp. 490
Algorithms on Graphsp. 491
Minimum-cost Spanning Trees, Revisitedp. 491
Finding the Shortest Pathp. 495
Exercisesp. 500
Supplementary Exercisesp. 502
Solutions to Exercisesp. 503
Does Many Mean More Than One? Computational Complexityp. 509
Turing Machinesp. 509
Complexity Classesp. 512
The Class Pp. 512
The Class NPp. 514
NP-complete Problemsp. 521
Other Complexity Classesp. 526
Exercisesp. 529
Supplementary Exercisesp. 531
Solutions to Exercisesp. 532
Bibliographyp. 537
Indexp. 541
Table of Contents provided by Ingram. All Rights Reserved.

Rewards Program

Write a Review