Combinatorics: AncientandModern TitlepageofAthanasiusKircher’sArsMagnaSciendiSiveCombinatoria(TheGreatArtof Knowledge,ortheCombinatorialArt)of1669. COMBINATORICS: ANCIENT AND MODERN Editedby robin wilson and john j. watkins 1 3 GreatClarendonStreet,Oxford,OX26DP, UnitedKingdom OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwide.Oxfordisaregisteredtrademarkof OxfordUniversityPressintheUKandincertainothercountries ©OxfordUniversityPress2013 Themoralrightsoftheauthorshavebeenasserted FirstEditionpublished2013 Impression:1 Allrightsreserved.Nopartofthispublicationmaybereproduced,storedin aretrievalsystem,ortransmitted,inanyformorbyanymeans,withoutthe priorpermissioninwritingofOxfordUniversityPress,orasexpresslypermitted bylaw,bylicenceorundertermsagreedwiththeappropriatereprographics rightsorganization.Enquiriesconcerningreproductionoutsidethescopeofthe aboveshouldbesenttotheRightsDepartment,OxfordUniversityPress,atthe addressabove Youmustnotcirculatethisworkinanyotherform andyoumustimposethissameconditiononanyacquirer BritishLibraryCataloguinginPublicationData Dataavailable ISBN 978–0–19–965659–2 Printedandboundby CPIGroup(UK)Ltd,Croydon,CR04YY LinkstothirdpartywebsitesareprovidedbyOxfordingoodfaithand forinformationonly.Oxforddisclaimsanyresponsibilityforthematerials containedinanythirdpartywebsitereferencedinthiswork. FOREWORD O ne of the most compelling instincts that human beings have is the irresistibleurgetolookforpatterns:thisisapparentfromtheearli- estattemptsofourancestorstounderstandtheworldaroundthem. Mathematicshasoftenbeendescribedasthescienceofpatterns,andperhaps morethananyothermathematicalfield,thisrepresentstheheartandsoulof combinatorics. In this masterful volume, the editors have brought together a wonderful andfar-rangingcollectionofchaptersbydistinguishedauthors.Theseaccounts surveythesubjectofcombinatorics,beginningwiththeearliestwrittenresults in the subject, continuing with its development in a variety of cultures, such as Indian, Chinese, Islamic, andJewish, andprogressing to theemergence of whatwenowthinkofasmoderncombinatorics.Fromtheintroductorychapter, ‘Two thousand years of combinatorics’, by Donald Knuth to Peter Cameron’s ‘A personal view of combinatorics’, the book covers a wide range of topics and offers to both the novice in the subject and to the experts a full plate of interestingfactsandviewpoints.Thisisthefirsttimethatsuchacompilation hasbeenattemptedand,intheopinionofthisreader,itsucceedsbrilliantly. RonaldGraham FormerPresidentoftheAmericanMathematicalSociety andtheMathematicalAssociationofAmerica foreword | v This page intentionally left blank PREFACE WhofirstpresentedPascal’striangle?(ItwasnotPascal.) WhofirstpresentedHamiltoniangraphs?(ItwasnotHamilton.) WhofirstpresentedSteinertriplesystems?(ItwasnotSteiner.) Misattributionsappearthroughoutthehistoryofmathematics,andcombina- torics has its share. Frequent errors in historical accuracy are perpetrated by thosewhowouldbeashamedtoallowsucherrorsintheirmathematicalwrit- ings:notableexamplesarethecommonassertionsthatEulerdrewafour-vertex graphtosolvetheKönigsbergbridgesproblemandthatDescartesdiscovered Euler’spolyhedronformula(theydidn’t). Today the history of mathematics is a well-studied and vibrant area of research,withbooksandscholarlyarticlespublishedonvariousaspectsofthe subject.Yet,thehistoryofcombinatoricsseemstohavebeenlargelyoverlooked: manycombinatorialistsseemuninterestedinthehistoryoftheirsubject,while historiansofmathematicshavetendedtobypassthefascinationsofcombina- torics.Itisourhopethatthisbook,writtenbynoteworthyexpertsinthearea, willgosomewaytoredressthis. Thisbookservestwopurposes: • It constitutes what is perhaps the first book-length survey of the history of combinatorics. • It assembles,for the first time in a single source,research on the history of combinatoricsthatwouldotherwisebeinaccessibletothegeneralreader. Thechaptershavebeencontributedbysixteenexperts,withtopicscorrespond- ingtotheirparticularareasofresearch.Someofthisresearchreceivesitsfirst airinghere,whileotherchaptersarebasedonworkthathasappearedelsewhere butislargelyunavailabletothosewithoutaccesstoresearchjournalsorlarge preface | vii universitylibraries.Inordertomakethebookeasiertoread,wehaveendeav- ouredtostandardizethestylethroughoutthebook,andwearegratefultothe authorsfortheirforbearancewithusasweproposedchangestotheirdraftsand imposedourstylisticconventions. The opening section is an introduction to two thousand years of combi- natorics, adapted with permission from a section of Volume 4 of Donald E. Knuth’scelebratedmulti-volumeworkTheArtofComputerProgramming.This is followed by seven chapters on early combinatorics, leading from Indian andChinesewritingsonpermutationstolate-Renaissancepublicationsonthe arithmeticaltriangle.Thenextsevenchapterstracethesubsequentstory,from Euler’scontributionstosuchwide-rangingtopicsaspartitions,polyhedra,and latinsquarestothe20th-centuryadvancesincombinatorialsettheory,enumer- ation,andgraphtheory.Thebookconcludeswithsomecombinatorialreflec- tionsbythedistinguishedcombinatorialistPeterJ.Cameron. Naturally,asthefirstbookofthiskind,thisvolumecannothopetobecom- prehensive,andyouwillnoticetopicsthataremissingoronlyminimallydis- cussed:theseincludecombinatorialoptimization,combinatorialidentities,and recreationalcombinatorics.Whilethesesubjects(andothers)wereconsidered forinclusionwefeltthatthenecessaryconstraintsofavolumeofmanageable scopeandsizeleft toolittleroom.Suchomissionsnotwithstanding,we hope thatasanoverviewofrecentandongoinghistoricalworkthisbookprovides usefulbackgroundinformationandinspirationforfutureresearch. As with many edited volumes, this book is not intended to be read from covertocover,althoughitcanbe.Rather,itisintendedtoserveasavaluable resource to a variety of audiences. We hope that combinatorialists with little ornoknowledgeaboutthedevelopmentoftheirsubjectwillfindthehistorical treatmentstimulating,andthatthespecialisthistorianofmathematicswillview itsassortedsurveysasanencouragementforfurtherresearchincombinatorics. For the more general reader, we hope that it provides an introduction to a fascinatingandtoolittleknownsubjectthatcontinuestostimulateandinspire theworkofscholarstoday. Finally, we’d like to express our thanks to Keith Mansfield, Viki Mortimer, and Clare Charles at Oxford University Press, and also to our host institu- tions, Pembroke College, Oxford University; The Open University, UK; and TheColoradoCollege,USA. TheEditors April2013 viii | preface CONTENTS PartI Introduction Twothousandyearsofcombinatorics 3 Donald E. Knuth PartII AncientCombinatorics 1. Indiancombinatorics 41 Takanori Kusuba and Kim Plofker 2. China 65 Andrea Bréard 3. Islamiccombinatorics 83 Ahmed Djebbar 4. Jewishcombinatorics 109 Victor J. Katz 5. Renaissancecombinatorics 123 Eberhard Knobloch 6. Theoriginsofmoderncombinatorics 147 Eberhard Knobloch 7. Thearithmeticaltriangle 167 A. W. F. Edwards PartIII ModernCombinatorics 8. Earlygraphtheory 183 Robin Wilson contents | ix