A Walk Through Combinatorics: An Introduction to Enumeration and Graph TheoryWorld Scientific, 2011 - 546 Seiten 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.Just as with the first two editions, 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 to the talented and hardworking 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, Eulerian and Hamiltonian cycles, and planar graphs.The selected advanced topics are: Ramsey theory, pattern avoidance, the probabilistic method, partially ordered sets, the theory of designs (new to this edition), enumeration under group action (new to this edition), generating functions of labeled and unlabeled structures 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.The Solution Manual is available upon request for all instructors who adopt this book as a course text. Please send your request to sales@wspc.com. |
Inhalt
Chapter 1 Seven Is More Than Six The PigeonHole Principle | 1 |
Chapter 2 One Step at a Time The Method of Mathematical Induction | 21 |
Chapter 3 There Are A Lot Of Them Elementary Counting Problems | 39 |
Chapter 4 No Matter How You Slice It The Binomial Theorem and Related Identities | 67 |
Chapter 5 Divide and Conquer Partitions | 93 |
Chapter 6 Not So Vicious Cycles Cycles in Permutations | 113 |
Chapter 7 You Shall Not Overcount The Sieve | 135 |
Chapter 8 A Function Is Worth Many Numbers Generating Functions | 149 |
Chapter 13 Does It Clique? Ramsey Theory | 293 |
Chapter 14 So Hard To Avoid Subsequence Conditions on Permutations | 313 |
Chapter 15 Who Knows What It Looks Like But It Exists The Probabilistic Method | 349 |
Chapter 16 At Least Some Order Partial Orders and Lattices | 381 |
Chapter 17 As Evenly As Possible Block Designs and Error Correcting Codes | 413 |
Chapter 18 Are They Really Different? Counting Unlabeled Structures | 447 |
Chapter 19 The Sooner The Better Combinatorial Algorithms | 481 |
Chapter 20 Does Many Mean More Than One? Computational Complexity | 509 |
Chapter 9 Dots and Lines The Origins of Graph Theory | 189 |
Chapter 10 Staying Connected Trees | 215 |
Chapter 11 Finding A Good Match Coloring and Matching | 247 |
Chapter 12 Do Not Cross Planar Graphs | 275 |
537 | |
541 | |
Andere Ausgaben - Alle anzeigen
Walk Through Combinatorics, A: An Introduction To Enumeration And Graph ... Miklos Bona Eingeschränkte Leseprobe - 2011 |
A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory Miklós Bóna Keine Leseprobe verfügbar - 2011 |
Häufige Begriffe und Wortgruppen
adjacency matrix adjacent algorithm antichain automorphism BIBD bijection bipartite graph blocks blue called Chapter choose claim codewords coefficient color complete graph compute connected contain defined definition degree denote digit directed graph eigenvalues elements entries equal exactly Example exists exponential generating function finite follows formula graph G Hamiltonian cycle implies induction hypothesis isomorphic k-element lattice least left-hand side Lemma Let G Let us assume matrix maximal element Möbius function monochromatic multiset Note NP-complete number of edges number of n-permutations number of vertices ordinary generating function pairs parameters path perfect matching Pigeon-hole Principle planar graph players polynomial poset positive integers previous exercise problem proof Prove real numbers recurrence relation right-hand side rooted sequence shows simple graph Solution sortable spanning tree square statement is true subgraph subsets teams Theorem tournament triangle Turing machine vertex set Walk Through Combinatorics