## A Walk Through Combinatorics: An Introduction to Enumeration and Graph TheoryThis is a textbook for an introductory combinatorics course that can take up 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. Just as with the first edition, the new edition walks the reader through the classic parts of combinatorial enumeration and graph theory, while also discussing some recent progress in the area: on the one hand, providing material that will help students learn the basic techniques, and on the other hand, showing that some questions at the forefront of research are comprehensible and accessible for the talented and hard-working undergraduate. The basic topics discussed are: the twelvefold way, cycles in permutations, the formula of inclusion and exclusion, the notion of graphs and trees, matchings and Eulerian and Hamiltonian cycles. The selected advanced topics are: Ramsey theory, pattern avoidance, the probabilistic method, partially ordered sets, and algorithms and complexity. As the goal of the book is to encourage students to learn more combinatorics, every effort has been made to provide them with a not only useful, but also enjoyable and engaging reading. |

### What people are saying - Write a review

User Review - Flag as inappropriate

superb book.....................

### Contents

Basic Methods | 1 |

One Step at a Time The Method of Mathematical Induction | 19 |

Enumerative Combinatorics | 37 |

No Matter How You Slice It The Binomial Theorem | 65 |

Divide and Conquer Partitions | 89 |

Not So Vicious Cycles Cycles in Permutations | 109 |

You Shall Not Overcount The Sieve | 131 |

Functions | 164 |

Do Not Cross Planar Graphs | 269 |

Horizons | 287 |

So Hard To Avoid Subsequence Conditions on Permutations | 307 |

Who Knows What It Looks Like But It Exists | 345 |

Exercises | 363 |

At Least Some Order Partial Orders and Lattices | 375 |

The Sooner The Better Combinatorial Algorithms | 407 |

Does Many Mean More Than One? Computational Complexity | 433 |

Graph Theory | 183 |

Staying Connected Trees | 209 |

Finding A Good Match Coloring and Matching | 241 |

### Other editions - View all

A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory Mikl髎 B髇a Limited preview - 2011 |

A Walk Through Combinatorics: An Introduction to Enumeration and Graph ... Mikl贸s B贸na Limited preview - 2006 |

A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory Mikl Ba Limited preview - 2002 |

### Common terms and phrases

adjacency matrix algorithm antichain bijection bipartite graph block blue called Chapter choose claim Combinatorics complete graph compute contain defined definition degree denote diagonal digit directed graph edges of G elements endpoints entries equal exactly Example exponential generating function Ferrers shape finite formula graph G Hamiltonian cycle implies induction hypothesis lattice paths least left-hand side Lemma length Let G Let us assume matrix MergeSort Mobius function monochromatic multiset n-permutations Note NP-complete number of edges number of partitions number of vertices ordinary generating function pair perfect matching permutation Pigeon-hole Principle planar graph players polyhedron polynomial poset positive integers previous exercise problem Prove Ramsey theory real numbers recurrence relation right-hand side sequence shown in Figure shows simple graph smallest Solution sortable spanning tree statement is true step subgraph subsets teams Theorem tournament triangle Turing machine vertex vertex set vertices of G