10258_9789813148840_tp.indd 1 31/8/16 3:29 PM B1948 Governing Asia B1948_1-Aoki.indd 6 B1948_1-Aoki.indd 6 9/22/2014 4:24:57 PM 9/22/2014 4:24:57 PM This page intentionally left blank This page intentionally left blank This page intentionally left blank This page intentionally left blank 10258_9789813148840_tp.indd 2 31/8/16 3:29 PM Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE Library of Congress Cataloging-in-Publication Data Names: Bóna, Miklós. Title: A walk through combinatorics : an introduction to enumeration and graph theory / Miklós Bóna (University of Florida, USA). Description: 4th edition. | New Jersey : World Scientific, 2017. | Includes bibliographical references and index. Identifiers: LCCN 2016030119 | ISBN 9789813148840 (hardcover : alk. paper) Subjects: LCSH: Combinatorial analysis--Textbooks. | Combinatorial enumeration problems-- Textbooks. | Graph theory--Textbooks. Classification: LCC QA164 .B66 2017 | DDC 511/.6--dc23 LC record available at https://lccn.loc.gov/2016030119 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. Copyright © 2017 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. Printed in Singapore A Walk Through Combinatorics-4th Ed-epub.indd 1 29-08-16 4:48:49 PM July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page v To Linda To Mikike, Benny, and Vinnie v B1948 Governing Asia B1948_1-Aoki.indd 6 B1948_1-Aoki.indd 6 9/22/2014 4:24:57 PM 9/22/2014 4:24:57 PM This page intentionally left blank This page intentionally left blank This page intentionally left blank This page intentionally left blank July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page vii Foreword The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include. There is no more-or-less canonical corpus as in such other subjects as number theory and com- plex variable theory. Mikl´os B´ona has succeeded admirably in blending classic results that would be on anyone’s list for inclusion in a textbook, a sprinkling of more advanced topics that are essential for further study of combinatorics, and a taste of recent work bringing the reader to the frontiers of current research. All three items are conveyed in an engag- ing style, with many interesting examples and exercises. A worthy fea- ture of the book is the many exercises that come with complete solutions. There are also numerous exercises without solutions that can be assigned for homework. Some relatively advanced topics covered by B´ona include permutations with restricted cycle structure, the Matrix-Tree theorem, Ramsey theory (going well beyond the classical Ramsey’s theorem for graphs), the prob- abilistic method, and the M¨obius function of a partially ordered set. Any of these topics could be a springboard for a subsequent course or read- ing project which will further convince the student of the extraordinary richness, variety, depth, and applicability of combinatorics. The most un- usual topic covered by B´ona is pattern avoidance in permutations and the connection with stack sortable permutations. This is a relatively re- cent research area in which most of the work has been entirely elemen- tary. An undergraduate student eager to do some original research has a good chance of making a worthwhile contribution in the area of pattern avoidance. vii July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page viii viii A Walk Through Combinatorics I only wish that when I was a student beginning to learn combinatorics there was a textbook available as attractive as B´ona’s. Students today are fortunate to be able to sample the treasures available herein. Richard Stanley Cambridge, Massachusetts February 6, 2002 July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page ix Preface The best way to get to know Yosemite National Park is to walk through it, on many different paths. In the optimal case, the gorgeous sights provide ample compensation for our sore muscles. In this book, we intend to explain the basics of Combinatorics while walking through its beautiful results. Starting from our very first chapter, we will show numerous examples of what may be the most attractive feature of this field: that very simple tools can be very powerful at the same time. We will also show the other side of the coin, that is, that sometimes totally elementary-looking problems turn out to be unexpectedly deep, or even unknown. This book is meant to be a textbook for an introductory combinatorics course that can take one or two semesters. We included a very extensive list of exercises, ranging in difficulty from “routine” to “worthy of independent publication”. In each section, we included exercises that contain material not explicitly discussed in the text before. We chose to do this to provide instructors with some extra choices if they want to shift the emphasis of their course. It goes without saying that we covered the classics, that is, combinato- rial choice problems, and graph theory. We included some more elaborate concepts, such as Ramsey theory, the Probabilistic Method, and Pattern Avoidance (the latter is probably a first of its kind). While we realize that we can only skim the surface of these areas, we believe they are interesting enough to catch the attention of some students, even at first sight. Most undergraduate students enroll in at most one Combinatorics course during their studies, therefore it is important that they see as many captivating examples as possible. It is in this spirit that we included two new chapters in the second edition, on Algorithms, and on Computational Complexity. We believe that the best undergraduate students, those who will get to the ix July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page x x A Walk Through Combinatorics end of the book, should be acquainted with the extremely intriguing ques- tions that abound in these two areas. The third edition has two challenging new chapters, one on Block Designs and codes obtained from designs, and the other one on counting unlabeled structures. We wrote this book as we believe that combinatorics, researching it, teaching it, learning it, is always fun. We hope that at the end of the walk, readers will agree. **** Exercises that are thought to be significantly harder than average are marked by one or more + signs. An exercise with a single + sign is prob- ably at the level of a harder homework problem. The difficulty level of an exercise with more than one + sign may be comparable to an indepen- dent publication. An exercise that is thought to be significantly easier than average is marked by a - sign. We listened to the readers, and added new examples where the readers suggested. This fourth edition has about 240 new exercises. We placed three of them at the end of each section, under the header Quick Check. The majority of exercises are still at the end of the chapters. We provide Supplementary Exercises without solutions at the end of each chapter. These typically include, but are not limited to, the easi- est exercises in that chapter. A solution manual for the Supplementary Exercises is available for Instructors. Gainesville, FL August 2016 July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page xi Acknowledgments This book has been written while I was teaching Combinatorics at the University of Florida, and during my sabbatical at the University of Penn- sylvania in the Fall of 2005. I am certainly indebted to the books I used in my teaching during this time. These were “Introductory Combinatorics” by Kenneth Bogarth, “Enumerative Combinatorics I.-II” by Richard Stanley, “Matching Theory” by L´aszl´o Lov´asz and Michael D. Plummer, and “A Course in Combinatorics” by J. H. van Lint and R. M. Wilson. The two new chapters of the second edition were certainly influenced by the books of which I learned the theory of algorithms and computation, namely “Com- putational Complexity” by Christos Papadimitriou, “Introduction to the Theory of Computation” by Michael Sipser, who taught me the subject in person, “Algorithms and Complexity” by Herbert Wilf, and “Introduction to Algorithms” by Cormen, Leiserson, Rivest and Stein. Several exercises in the book come from my long history as a student mathematics competi- tion participant. This includes various national and international contests, as well as the long-term contest run by the Hungarian student journal K ¨OMAL, and the Russian student journal Kvant. I am grateful to my students who never stopped asking questions and showed which part of the material needed further explanation. Some of the presented material was part of my own research, sometimes in collaboration. I would like to say thanks to my co-authors, Andrew MacLennan, Bruce Sagan, Rodica Simion, Daniel Spielman, G´eza T´oth, and Dennis White. I am also indebted to my former advisor, Richard Stanley, who introduced me to the fascinating area of Pattern Avoidance, discussed in Chapter 14. I am deeply appreciative for the constructive suggestions of my col- leagues Vincent Vatter, Andrew Vince, Neil White, and Aleksandr Vayner. xi July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page xii xii A Walk Through Combinatorics A significant part of the first edition was written during the summer of 2001, when I enjoyed the hospitality of my parents, Mikl´os and Katalin B´ona, at the Lake Balaton in Hungary. My gratitude is extended to Joseph Sciacca for the cover page. If you do not know why a book entitled “A Walk Through Combinatorics” has such a cover page, you may figure it out when reading Chapter 10. After the publication of the first edition in 2002, several mathemati- cians contributed lists of typographical errors to be corrected. Particularly extensive lists were provided by Margaret Bayer, Richard Ehrenborg, John Hall, Hyeongkwan Ju, Sergey Kitaev, and Robert Robinson. I am thankful for their help in making the second edition better by communicating those lists to me, as well as for similar help from countless other contributors who will hopefully forgive that I do not list all of them here. The second edition was improved by a significant list of comments by Margaret Bayer, while the third edition was similarly helped by the remarks of Glenn Tesler. I am indebted to Thomas Zaslavsky for numerous conversations and suggestions that made the paperback version of the third edition better. The fourth edition was improved by suggestions made by Steven Sam. Most of all, I must thank my wife Linda, my first reader, who made it possible for me to spend long hours writing this book while she also had her hands full. See Exercise 3 of Chapter 15 for further explanation. July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page xiii Contents Foreword vii Preface ix Acknowledgments xi I. Basic Methods 1. Seven Is More Than Six. The Pigeon-Hole Principle 1 1.1 The Basic Pigeon-Hole Principle . . . . . . . . . . . . . . 1 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 The Generalized Pigeon-Hole Principle . . . . . . . . . . . 4 Quick Chek . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . 12 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 14 2. One Step at a Time. The Method of Mathematical Induction 23 2.1 Weak Induction . . . . . . . . . . . . . . . . . . . . . . . . 23 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . 29 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . 33 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 35 xiii July 28, 2016 17:25 ws-book9x6 A Walk Through Combinatorics book page xiv xiv A Walk Through Combinatorics II. Enumerative Combinatorics 3. There Are A Lot Of Them. Elementary Counting Problems 43 3.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . 43 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 Strings over a Finite Alphabet . . . . . . . . . . . . . . . . 46 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 Choice Problems . . . . . . . . . . . . . . . . . . . . . . . 50 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . 58 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 60 4. No Matter How You Slice It. The Binomial Theorem and Related Identities 73 4.1 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . 73 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2 The Multinomial Theorem . . . . . . . . . . . . . . . . . . 78 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3 When the Exponent Is Not a Positive Integer . . . . . . . 81 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . 87 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 90 5. Divide and Conquer. Partitions 101 5.1 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . 101 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2 Set Partitions . . . . . . . . . . . . . . . . . . . . . . . . . 103 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.3 Integer Partitions . . . . . . . . . . . . . . . . . . . . . . . 106 Quick Check . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . 115 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . 117 6. Not So Vicious Cycles. Cycles in Permutations 123 6.1 Cycles in Permutations . . . . . . . . . . . . . . . . . . . . 124