Combinatorics : Topics, Techniques, Algorithms
by Peter J. CameronFormat: Hardcover
Pub. Date: 1995-01-27
Publisher(s): Cambridge University Press
Other versions by this Author
-
This Item Qualifies for Free Shipping!*
*Excludes marketplace orders.
List Price: $73.45
Buy New
Arriving Soon. Will ship when available.
$69.95
Rent Textbook
Select for Price
Rent Digital
$92.16
Used Textbook
We're Sorry
Sold Out
Summary
Combinatorics is a subject of increasing importance, owing to its links with computer science, statistics and algebra. This is a textbook aimed at second-year undergraduates to beginning graduates. It stresses common techniques (such as generating functions and recursive construction) which underlie the great variety of subject matter and also stresses the fact that a constructive or algorithmic proof is more valuable than an existence proof. The book is divided into two parts, the second at a higher level and with a wider range than the first. Historical notes are included which give a wider perspective on the subject. More advanced topics are given as projects and there are a number of exercises, some with solutions given.
Table of Contents
| Preface | |
| What is Combinatorics? | p. 1 |
| Sample problems | |
| How to use this book | |
| What you need to know | |
| Exercises | |
| On numbers and counting | p. 7 |
| Natural numbers and arithmetic | |
| Induction | |
| Some useful functions | |
| Orders of magnitude | |
| Different ways of counting | |
| Double counting | |
| Appendix on set notation | |
| Exercises | |
| Subsets, partitions, permutations | p. 21 |
| Subsets | |
| Subsets of fixed size | |
| The Binomial Theorem and Pascal's Triangle | |
| Project: Congruences of binomial coefficients | |
| Permutations | |
| Estimates for factorials | |
| Selections | |
| Equivalence and order | |
| Project: Finite topologies | |
| Project: Cayley's Theorem on trees | |
| Bell numbers | |
| Generating combinatorial objects | |
| Exercises | |
| Recurrence relations and generating functions | p. 49 |
| Fibonacci numbers | |
| Aside on formal power series | |
| Linear recurrence relations with constant coefficients | |
| Derangements and involutions | |
| Catalan and Bell numbers | |
| Computing solutions to recurrence relations | |
| Project: Finite fields and QUICKSORT | |
| Exercises | |
| The Principle of Inclusion and Exclusion | p. 75 |
| PIE | |
| A generalisation | |
| Stirling numbers | |
| Project: Stirling numbers and exponentials | |
| Even and odd permutations | |
| Exercises | |
| Latin squares and SDRs | p. 87 |
| Latin squares | |
| Systems of distinct representatives | |
| How many Latin squares? | |
| Quasigroups | |
| Project: Quasigroups and groups | |
| Orthogonal Latin squares | |
| Exercises | |
| Extremal set theory | p. 99 |
| Intersecting families | |
| Sperner families | |
| The De Bruijn-Erdos Theorem | |
| Project: Regular families | |
| Exercises | |
| Steiner triple systems | p. 107 |
| Steiner systems | |
| A direct construction | |
| A recursive construction | |
| Packing and covering | |
| Project: Some special Steiner triple systems | |
| Project: Tournaments and Kirkman's schoolgirls | |
| Exercises | |
| Finite geometry | p. 123 |
| Linear algebra over finite fields | |
| Gaussian coefficients | |
| Projective geometry | |
| Axioms for projective geometry | |
| Projective planes | |
| Other kinds of geometry | |
| Project: Coordinates and configurations | |
| Project: Proof of the Bruck-Ryser Theorem | |
| Finite fields | |
| Exercises | |
| Ramsey's Theorem | p. 147 |
| The Pigeonhole Principle | |
| Some special cases | |
| Ramsey's Theorem | |
| Bounds for Ramsey numbers | |
| Applications | |
| The infinite version | |
| Exercises | |
| Graphs | p. 159 |
| Definitions | |
| Trees and forests | |
| Minimal spanning trees | |
| Eulerian graphs | |
| Hamiltonian graphs | |
| Project: Gray codes | |
| The Travelling Salesman | |
| Digraphs | |
| Networks | |
| Menger, Konig and Hall | |
| Diameter and girth | |
| Project: Moore graphs | |
| Exercises | |
| Posets, lattices and matroids | p. 187 |
| Posets and lattices | |
| Linear extensions of a poset | |
| Distributive lattices | |
| Aside on propositional logic | |
| Chains and antichains | |
| Products and dimension | |
| The Mobius function of a poset | |
| Matroids | |
| Project: Arrow's Theorem | |
| Exercises | |
| More on partitions and permutations | p. 209 |
| Partitions, diagrams and conjugacy classes | |
| Euler's Pentagonal Numbers Theorem | |
| Project: Jacobi's Identity | |
| Tableaux | |
| Symmetric polynomials | |
| Exercises | |
| Automorphism groups and permutation groups | p. 225 |
| Three definitions of a group | |
| Examples of groups | |
| Orbits and transitivity | |
| The Schreier-Sims algorithm | |
| Primitivity and multiple transitivity | |
| Examples | |
| Project: Cayley digraphs and Frucht's Theorem | |
| Exercises | |
| Enumeration under group action | p. 245 |
| The Orbit-counting Lemma | |
| An application | |
| Cycle index | |
| Examples | |
| Direct and wreath products | |
| Stirling numbers revisited | |
| Project: Cycle index and symmetric functions | |
| Exercises | |
| Designs | p. 257 |
| Definitions and examples | |
| To repeat or not to repeat | |
| Fisher's Inequality | |
| Designs from finite geometry | |
| Small designs | |
| Project: Hadamard matrices | |
| Exercises | |
| Error-correcting codes | p. 271 |
| Finding out a liar | |
| Definitions | |
| Probabilistic considerations | |
| Some bounds | |
| Linear codes; Hamming codes | |
| Perfect codes | |
| Linear codes and projective spaces | |
| Exercises | |
| Graph colourings | p. 291 |
| More on bipartite graphs | |
| Vertex colourings | |
| Project: Brooks' Theorem | |
| Perfect graphs | |
| Edge colourings | |
| Topological graph theory | |
| Project: The Five-colour Theorem | |
| Exercises | |
| The infinite | p. 307 |
| Counting infinite sets | |
| Konig's Infinity Lemma | |
| Posets and Zorn's Lemma | |
| Ramsey theory | |
| Systems of distinct representatives | |
| Free constructions | |
| The random graph | |
| Exercises | |
| Where to from here? | p. 325 |
| Computational complexity | |
| Some graph-theoretic topics | |
| Computer software | |
| Unsolved problems | |
| Further reading | |
| Answers to selected exercises | p. 339 |
| Bibliography | p. 343 |
| Index | p. 347 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
An electronic version of this book is available through VitalSource.
This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.
By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.
Digital License
You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.
More details can be found here.
A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.
Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.
Please view the compatibility matrix prior to purchase.