WIXLIB

Facts are presented concisely and are listed so that they can be easily found and understood. Extensive crossreferences linking parts of the handbook are also provided.Readers who want to study a topic further can consult the resources listed.The material in the Handbook has been chosen for inclusion primarily because it isimportant and useful. Additional material has been added to ensure comprehensivenessso that readers encountering new terminology and concepts from discrete mathematicsin their explorations will be able to get help from this book.Examples are provided to illustrate some of the key definitions, facts, and algorithms.Some curious and entertaining facts and puzzles that some readers may find intriguingare also included.Each chapter of the book includes a list of references divided into a list of printedresources and a list of relevant websites.How This Book Was DevelopedThe organization and structure of the Handbook were developed by a team which included the chief editor, three associate editors, the project editor, and the editor fromCRC Press. This team put together a proposed table of contents which was then analyzed by members of a group of advisory editors, each an expert in one or more aspectsof discrete mathematics. These advisory editors suggested changes, including the coverage of additional important topics. Once the table of contents was fully developed, theindividual sections of the book were prepared by a group of more than 70 contributorsfrom industry and academia who understand how this material is used and why it isimportant. Contributors worked under the direction of the associate editors and chiefeditor, with these editors ensuring consistency of style and clarity and comprehensiveness in the presentation of material. Material was carefully reviewed by authors andour team of editors to ensure accuracy and consistency of style.The CRC Press Series on Discrete Mathematics and Its ApplicationsThis Handbook is designed to be a ready reference that covers many important distincttopics. People needing information in multiple areas of discrete and combinatorialmathematics need only have this one volume to obtain what they need or for pointersto where they can find out more information. Among the most valuable sources ofadditional information are the volumes in the CRC Press Series on Discrete Mathematicsand Its Applications. This series includes both Handbooks, which are ready references,and advanced Textbooks/Monographs. More detailed and comprehensive coverage inparticular topic areas can be found in these individual volumes:Handbooks The CRC Handbook of Combinatorial Designs Handbook of Discrete and Computational Geometry Handbook of Applied CryptographyTextbooks/Monographs Graph Theory and its Applications Algebraic Number Theory Quadraticsc 2000 by CRC Press LLC

Design Theory Frames and Resolvable Designs: Uses, Constructions, and Existence Network Reliability: Experiments with a Symbolic Algebra Environment Fundamental Number Theory with Applications Cryptography: Theory and Practice Introduction to Information Theory and Data Compression Combinatorial Algorithms: Generation, Enumeration, and SearchFeedbackTo see updates and to provide feedback and errata reports, please consult the Web pagefor this book. This page can be accessed by first going to the CRC website athttp://www.crcpress.comand then following the links to the Web page for this book.AcknowledgmentsFirst and foremost, we would like to thank the original CRC editor of this project,Wayne Yuhasz, who commissioned this project. We hope we have done justice to hisoriginal vision of what this book could be. We would also like to thank Bob Stern,who has served as the editor of this project for his continued support and enthusiasmfor this project. We would like to thank Nora Konopka for her assistance with manyaspects in the development of this project. Thanks also go to Susan Fox, for her helpwith production of this book at CRC Press.We would like to thank the many people who were involved with this project. First,we would like to thank the team of advisory editors who helped make this referencerelevant, useful, unique, and up-to-date. We also wish to thank all the people at thevarious institutions where we work, including the management of AT&T Laboratories fortheir support of this project and for providing a stimulating and interesting atmosphere.Project Editor John Michaels would like to thank his wife Lois and daughter Margaretfor their support and encouragement in the development of the Handbook. AssociateEditor Jonathan Gross would like to thank his wife Susan for her patient support,Associate Editor Jerrold Grossman would like to thank Suzanne Zeitman for her helpwith computer science materials and contacts, and Associate Editor Douglas Shier wouldlike to thank his wife Joan for her support and understanding throughout the project.c 2000 by CRC Press LLC

ADVISORY EDITORIAL BOARDAndrew Odlyzko — Chief Advisory EditorAT&T LaboratoriesStephen F. AltschulNational Institutes of HealthFrank HararyNew Mexico State UniversityGeorge E. AndrewsPennsylvania State UniversityAlan HoffmanIBMFrancis T. BoeschStevens Institute of TechnologyBernard KorteRheinische Friedrich-Wilhems-Univ.Ernie BrickellCertcoJeffrey C. LagariasAT&T LaboratoriesFan R. K. ChungUniv. of California at San DiegoCarl PomeranceUniversity of GeorgiaCharles J. ColbournUniversity of VermontFred S. RobertsRutgers UniversityStan DevittWaterloo Maple SoftwarePierre RosenstiehlCentre d’Analyse et de Math. Soc.Zvi GalilColumbia UniversityFrancis SullivanIDAKeith GeddesUniversity of WaterlooJ. H. Van LintEindhoven University of TechnologyRonald L. GrahamUniv. of California at San DiegoScott VanstoneUniversity of WaterlooRalph P. GrimaldiRose-Hulman Inst. of TechnologyPeter WinklerBell Laboratoriesc 2000 by CRC Press LLC

CONTRIBUTORSRavindra K. AhujaUniversity of FloridaMukesh Dalali2 TechnologiesNancy M. AmatoTexas A&M UniversityTamal K. DeyIndian Institute of Technology KharagpurGeorge E. AndrewsPennsylvania State UniversityJeffrey H. DinitzUniversity of VermontR. B. BapatIndian Statistical InstituteMichael DoobUniversity of ManitobaJoseph R. BarrSPSSThomas A. DowlingOhio State UniversityLowell W. BeinekePurdue University — Fort WayneS. E. ElmaghrabyNorth Carolina State UniversityEdward A. BenderUniversity of California at San DiegoSusanna S. EppDePaul UniversityKaroly BezdekCornell UniversityJoan FeigenbaumAT&T LaboratoriesJoel V. BrawleyClemson UniversityW. Randolph FranklinRensselaer Polytechnic InstituteGraham BrightwellLondon School of EconomicsWilliam GasarchUniversity of MarylandStefan A. BurrCity College of New YorkBart E. GoddardTexas A&M UniversityLisa CarboneHarvard UniversityCharles H. GoldbergTrenton State CollegeJianer ChenTexas A&M UniversityBruce L. GoldenUniversity of MarylandSunil ChopraNorthwestern UniversityJon F. GranthamIDACharles J. ColbournUniversity of VermontRalph P. GrimaldiRose-Hulman Inst. of TechnologyThomas CormenDartmouth CollegeJonathan L. GrossColumbia Universityc 2000 by CRC Press LLC

Jerrold W. GrossmanOakland UniversityEsmond NgLawrence Berkeley National Lab.Andreas GyarfasHungarian Academy of SciencesBeth NovickClemson UniversityS. Louis HakimiUniversity of California at DavisJames B. OrlinMassachusetts Inst. of TechnologyLane HemaspaandraUniversity of RochesterJames G. OxleyLouisiana State UniversityPatrick JailletUniversity of Texas at AustinJános PachCity College CUNY, andHungarian Academy of SciencesBharat K. KakuAmerican UniversitySampath KannanUniversity of PennsylvaniaVictor J. KatzUniv. of the District of ColumbiaDina KravetsSarnoff CorporationVidyadhar G. KulkarniUniversity of North CarolinaLawrence M. LeemisThe College of William and MaryBennet ManvelColorado State UniversityStephen B. MaurerSwarthmore CollegeAlfred J. MenezesUniversity of WaterlooMichael Mesterton-GibbonsFlorida State UniversityJohn G. MichaelsSUNY BrockportMilena MihailGeorgia Institute of TechnologyVictor S. MillerCenter for CommunicationsResearch — IDAc 2000 by CRC Press LLC Edward W. PackelLake Forest CollegeUri PeledUniversity of Illinois at ChicagoBarry PeytonOak Ridge National LaboratoryCarl PomeranceUniversity of GeorgiaViera Krnanova ProulxNortheastern UniversityRobert G. RieperWilliam Patterson UniversityDavid RileyUniversity of WisconsinKenneth H. RosenAT&T LaboratoriesBruce E. SaganMichigan State UniversityAarto SalomaaUniversity of Turku, FinlandEdward R. ScheinermanJohns Hopkins UniversityJeff ShalitUniversity of WaterlooDouglas R. ShierClemson University

David Simchi-LeviNorthwestern UniversityPaul C. van OorschotEntrust TechnologiesPaul K. StockmeyerThe College of William and MaryDouglas B. WestUniversity of Illinois at ChampaignUrbanaIleana StreinuSmith CollegeAlan C. TuckerSUNY Stony BrookPeter R. TurnerUnited States Naval Academyc 2000 by CRC Press LLC Arthur T. WhiteWestern Michigan UniversityJay YellenFlorida Institute of Technology

BIOGRAPHIESVictor J. KatzNiels Henrik Abel (1802–1829), born in Norway, was self-taught and studied theworks of many mathematicians. When he was nineteen years old, he proved thatthere is no closed formula for solving the general fifth degree equation. He alsoworked in the areas of infinite series and elliptic functions and integrals. The termabelian group was coined in Abel’s honor in 1870 by Camille Jordan.Abraham ibn Ezra (1089–1164) was a Spanish-Jewish poet, philosopher, astrologer,and biblical commentator who was born in Tudela, but spent the latter part ofhis life as a wandering scholar in Italy, France, England, and Palestine. It was inan astrological text that ibn Ezra developed a method for calculating numbers ofcombinations, in connection with determining the number of possible conjunctions ofthe seven “planets” (including the sun and the moon). He gave a detailed argumentfor the cases n 7, k 2 to 7, of a rule which can easily be generalize to the modernn 1formula C(n, k) i k 1 C(i, k 1). Ibn Ezra also wrote a work on arithmetic inwhich he introduced the Hebrew-speaking community to the decimal place-valuesystem. He used the first nine letters of the Hebrew alphabet to represent the firstnine numbers, used a circle to represent zero, and demonstrated various algorithmsfor calculation in this system.Aristotle (384–322 B.C.E.) was the most famous student at Plato’s academy in Athens.After Plato’s death in 347 B.C.E., he was invited to the court of Philip II of Macedon to educate Philip’s son Alexander, who soon thereafter began his successfulconquest of the Mediterranean world. Aristotle himself returned to Athens, wherehe founded his own school, the Lyceum, and spent the remainder of his life writingand lecturing. He wrote on numerous subjects, but is perhaps best known for hisworks on logic, including the Prior Analytics and the Posterior Analytics. In theseworks, Aristotle developed the notion of logical argument, based on several explicitprinciples. In particular, he built his arguments out of syllogisms and concluded thatdemonstrations using his procedures were the only certain way of attaining scientificknowledge.Emil Artin (1898–1962) was born in Vienna and in 1921 received a Ph.D. from the University of Leipzig. He held a professorship at the University of Hamburg until 1937,when he came to the United States. In the U.S. he taught at the University of NotreDame, Indiana University, and Princeton. In 1958 he returned to the Universityof Hamburg. Artin’s mathematical contributions were in number theory, algebraictopology, linear algebra, and especially in many areas of abstract algebra.Charles Babbage (1792–1871) was an English mathematician best known for his invention of two of the earliest computing machines, the Difference Engine, designedto calculate polynomial functions, and the Analytical Engine, a general purpose calculating machine. The Difference Engine was designed to use the idea that the nthorder differences in nth degree polynomials were always constant and then to workbackwards from those differences to the original polynomial values. Although Babc 2000 by CRC Press LLC

bage received a grant from the British government to help in building the Engine, henever was able to complete one because of various difficulties in developing machineparts of sufficient accuracy. In addition, Babbage became interested in his moreadvanced Analytical Engine. This latter device was to consist of a store, in whichthe numerical variables were kept, and a mill, in which the operations were performed. The entire machine was to be controlled by instructions on punched cards.Unfortunately, although Babbage made numerous engineering drawings of sectionsof the Analytical Engine and gave a series of seminars in 1840 on its workings, hewas never able to build a working model.Paul Gustav Heinrich Bachmann (1837–1920) studied mathematics at the University of Berlin and at Göttingen. In 1862 he received a doctorate in group theory andheld positions at the universities at Breslau and Münster. He wrote several volumeson number theory, introducing the big-O notation in his 1892 book.John Backus (born 1924) received bachelor’s and master’s degrees in mathematicsfrom Columbia University. He led the group at IBM that developed FORTRAN.He was a developer of ALGOL, using the Backus-Naur form for the syntax of thelanguage. He received the National Medal of Science in 1974 and the Turing Awardin 1977.Abu-l-’Abbas Ahmad ibn Muhammad ibn al-Banna al-Marrakushi (1256–1321) was an Islamic mathematician who lived in Marrakech in what is now Morocco.Ibn al-Banna developed the first known proof of the basic combinatorial formulas,beginning by showing that the number of permutations of a set of n elements was n!and then developing in a careful manner the multiplicative formula to compute thevalues for the number of combinations of k objects in a set of n. Using these tworesults, he also showed how to calculate the number of permutations of k objects froma set of n. The formulas themselves had been known in the Islamic world for manyyears, in connection with specific problems like calculating the number of words ofa given length which could be formed from the letters of the Arabic alphabet. Ibnal-Banna’s main contribution, then, was to abstract the general idea of permutationsand combinations out of the various specific problem situations considered earlier.Thomas Bayes (1702–1761) an English Nonconformist, wrote an Introduction to theDoctrine of Fluxions in 1736 as a response to Berkeley’s Analyst with its severe criticism of the foundations of the calculus. He is best known, however, for attemptingto answer the basic question of statistical inference in his An Essay Towards Solvinga Problem in the Doctrine of Chances, published three years after his death. Thatbasic question is to determine the probability of an event, given empirical evidencethat it has occurred a certain number of times in a certain number of trials. To dothis, Bayes gave a straightforward definition of probability and then proved that fortwo events E and F , the probability of E given that F has happened is the quotient of the probability of both E and F happening divided by the probability of Falone. By using areas to model probability, he was then able to show that, if x is theprobability of an event happening in a single trial, if the event has happened p timesin n trials, and if 0 r s 1, then the probability that x is between r and s isgiven by the quotient of two integrals. Although in principle these integrals can becalculated, there has been a great debate since Bayes’ time about the circumstancesunder which his formula gives an appropriate answer.James Bernoulli (Jakob I) (1654–1705) was one of eight mathematicians in threegenerations of his family. He was born in Basel, Switzerland, studied theology inaddition to mathematics and astronomy, and entered the ministry. In 1682 be beganc 2000 by CRC Press LLC

to lecture at the University of Basil in natural philosophy and mechanics. He becameprofessor at the University of Basel in 1687, and remained there until his death. Hisresearch included the areas of the calculus of variations, probability, and analyticgeometry. His most well-known work is Ars Conjectandi, in which he describedresults in combinatorics and probability, including applications to gambling and thelaw of large numbers; this work also contained a reprint of the first formal treatisein probability, written in 1657 by Christiaan Huygens.Bhaskara (1114–1185), the most famous of medieval Indian mathematicians, gave acomplete algorithmic solution to the Pell equation Dx2 1 y 2 . That equation hadbeen studied by several earlier Indian mathematicians as well. Bhaskara served muchof his adult life as the head of the astronomical observatory at Ujjain, some 300 milesnortheast of Bombay, and became widely respected for his skills in astronomy and themechanical arts, as well as mathematics. Bhaskara’s mathematical contributions arechiefly found in two chapters, the Lilavati and the Bijaganita, of a major astronomicalwork, the Siddhāntasiromani. These include techniques of solving systems of linearequations with more unknowns than equations as well as the basic combinatorialformulas, although without any proofs.George Boole (1815–1864) was an English mathematician most famous for his workin logic. Born the son of a cobbler, he had to struggle to educate himself whilesupporting his family. But he was so successful in his self-education that he was ableto set up his own school before he was 20 and was asked to give lectures on the workof Isaac Newton. In 1849 he applied for and was appointed to the professorship inmathematics at Queen’s College, Cork, despite having no university degree. In 1847,Boole published a small book, The Mathematical Analysis of Logic, and seven yearslater expanded it into An Investigation of the Laws of Thought. In these books, Booleintroduced what is now called Boolean algebra as part of his aim to “investigate thefundamental laws of those operations of the mind by which reasoning is performed;to give expression to them in the symbolical language of a Calculus, and upon thisfoundation to establish the science of Logic and construct its method.” In additionto his work on logic, Boole wrote texts on differential equations and on differenceequations that were used in Great Britain until the end of the nineteenth century.William Burnside (1852–1927), born in London, graduated from Cambridge in 1875,and remained there as lecturer until 1885. He then went to the Royal Naval Collegeat Greenwich, where he stayed until he retired. Although he published much inapplied mathematics, probability, and elliptic functions, he is best known for hisextensive work in group theory (including the classic book Theory of Groups). Hisconjecture that groups of odd order are solvable was proved by Walter Feit and JohnThompson and published in 1963.Georg Ferdinand Ludwig Philip Cantor (1845–1918) was born in Russia to Danishparents, received a Ph.D. in number theory in 1867 at the University of Berlin, andin 1869 took a position at Halle University, where he remained until his retirement.He is regarded as a founder of set theory. He was interested in theology an

The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying. Direct all inquiries to CRC Press L