Progress in Computer Science No. 4 Edited by J. Bentley E. Coffman R. L, Graham D. Birkhauser Boston - Basel - StuttgartGeorge Polya Robert E. Tarjan Donald R. Woods Notes on Introductory Combinatorics WGoUd 1983 Birkhauser Boston - Basel - StuttgartAuthors: George Pélya Department of Mathematics Stanford University Stanford, California 94305, USA Robert E, Tarjan Bell Laboratories 600 Mountain Avenue Murray Hill, New Jersey 0/974, USA. Donald R. Woods Xerox Corporation 3333 Coyote Hill Road Palo Alto, California 94304, USA Library of Congress Cataloging in Publication Data Polya, George, 1887- Notes on introductory combinatorics. (Progress in computer science ; no. 4) Bibliography: p. 1, Combinatorial analysis. _I. Tarjan, Robert E. (Robert Endre), 1948- . IL. Woods, Donald R.. 1954- . IIL. Title. _ IV. Series. QA164.P635_ 1983 S116 83-15790 ISBN 0-8176-3123-2 ISBN 0-8176-3170-4 (pbk.) CIP-Kurztitelaufnahme der Deutschen Bibliothek Polya, George: Notes on introductory combinatorics / George Polya ; Robert E. Tarjan ; Donald RK. Woods, - Boston ; Basel ; Stuttgart : Birkhiuser, 1983. (Progress in computer science : No. 4) ISBN 3-7643-3170-4 (Basel, Stuttgart) brosch. ISBN 0-8176-3170-4 (Boston) brosch. ISBN 3-7643-3123-2 (Basel, Stuttgart) Pp. ISBN 0-8176-3123-2 (Boston) Pp. NE: Tarjan, Robert E.:, Woods, Donald R.:; GT Allrights reserved. No part of this publication may be reproduced, stored in aretrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without prior permission of the copyright owner. © Birkhituser Boston, Inc., 1983 ISBN 0-8176-3123-2 (hardcover); 0-8176-3170-4 (paperback) ISBN 3-7643-3123-2 (hardcover); 3-7643-3170-4 (paperback) Printed in USA 987654321Table of Contents Introduction. . . . 1... Combinations and Permutations . Generating Functions . ..... + Principle of Inclusion and Exclusion. . . Stirling Numbers . Pélya’s Theory of Counting . Outlook 2... 6 ee ee Midterm Examination . . . . . - Ramsey Theory . 2... ee ee eee ). Matchings (Stable Marriages) . . 2. . - . Matchings (Maximum Matchings). . . . . Network Flow . 2... 1. ee ee ee onian and Eulerian Paths . Planarity and the Four-Color Theorem . » Final Examination . Bibliography © 2. ee ee 32 41 55 95 116 + 128 » 135 + 152 « 157 . 169 - 182 191[2] Combinations and Permutations January 5. In his first lecture, Polya discussed in general terms what combinatorics is about: The study of counting various combinations or configurations, He started with a problem based on the mystical sign known, appropriately, as an “abracadabra”. The question is, how many different ways are there to spell out “abracadabra”, always going from one letter to an adjacent letter? Due to the way some letters (especially C and D) are found only in certain rows, it turns out the only ways to spell “abracadabra” start with the topmost ‘A’ and zig-zag down to the bottommost ‘A’. If we think of the letters as points, then any spelling of “abracadabra” the bottom. One such line is shown below. You can also think of this problem in terms of a network of streets in a city where all blocks are the same size. Then the problem becomes one of computing how many ways there are of getting from the northern corner to the southern corner in the minimum number (10) of blocks. (That 10 is the minimum can be seen from the fact that each block, in addition to taking us either east or west, takes usNotes on Introductory Combinatorics George Pélya Robert E. Tarjan Donald R. Woods In the winter of 1978, Professors George Pélya and Robert Tarjan teamed up at Stanford University to teach a course titled “Introduction to Combinatorics”. This book consists primarily of the Class notes and related material produced by Donald Woods as teaching assistant for the course. Among the topics covered in the notes are elementary sub jects such as combinations and permutations, mathematical tools such as generating functions and Pélya’s Theory of Counting, and specific problems such as Ramsey Theory, matchings, and Hamiltonian and Eulerian paths.PREFACE In the winter of 1978, Professor George Pélya and I jointly taught Stanford University’s introductory combinatorics course, This was a great opportunity for me, as I had known of Professor Pélya since having read his classic book, How to Solve It, as a teenager. Working with Polya, who was over ninety years old at the time, was every bit as rewarding as I] had hoped it would be. His creativity, intelligence, warmth and generosity of spirit, and wonderful gift for teaching continue to be an inspiration to me. Combinatorics is one of the branches of mathematics that play a crucial role in computer science, since digital computers manipulate discrete, finite objects. Combinatorics impinges on computing in two ways. First, the properties of graphs and other combinatorial ob jects lead directly to algorithms for solving graph-theoretic problems, which have widespread application in non-numerical as well as in numerical computing. Second, combinatorial methods provide many analytical tools that can be used for determining the worst-case and expected performance of computer algorithms. A knowledge of combinatorics will serve the computer scientist well. Combinatorics can be classified into three types: enumerative, existential, and constructive. Enumerative combinatorics deals with the counting of combinatorial objects. Existential combinatorics Studies the existence or nonexistence of combinatorial configurations. Constructive combinatorics deals with methods for actually finding Specific configurations (as opposed to merely demonstrating their existence theoretically). The first two-thirds of our course, taught by Professor Pélya, dealt with enumerative combinatorics, including combinations, generating functions, the principle of inclusion and exclusion, Stirling numbers, and Pélya’s own theory of counting. The last third of the course, taught by me, covered existential combinatorics, with an emphasis on algorithmic graph theory, and included matching, network flow, Hamiltonian and Eulerian paths, and planar graphs. Donald Woods, our teaching assistant, was not only invaluable in helping us give the course but also was able to prepare readable and comprehensive course notes, which he has edited to form the present book. Don did a masterful job in making sense out of ourramblings and adding observations and references of his own. Were I to teach the course again these notes would be indispensable. I hope you will enjoy them. Robert E. Tarjan Murray Hill, New Jersey May 3, 1983Introduction For the most part the notes that comprise this text differ only slightly from those provided to the students during the course. The notes have been merged into a single paper, a few sections have been made more detailed, and various corrigenda have been incorporated. The midterm and final examinations are included in their proper chronological places within the text (chapters 8 and 15), together with the solutions. The only information omitted from this book is that regarding the mechanics of the course—office hours, grading criteria, etc. Homework assignments are included, as they often led to further discussion in the notes. Lecture dates are included to give a feel for the pace at which material was covered, though it should be noted that much of the material in the notes was not actually presented in the lectures, being instead drawn from supplementary notes provided by the instructors or supplied by the author as the notes were written. A brief word of explanation regarding the dual instructorship of the course: Professor Pélya taught the first two-thirds of the course, reflected in chapters 2 through 7 of this book. Professor Tarjan taught the remainder of the course, as covered in chapters 9 through 14. Though there was no formal text for the course, a number of books were made available for reference. These books, along with additional texts used by the author in preparing the notes, are listed the bibliography. The [bracketed] abbreviations given there will be used when referring to one of Pélya’s books; the other texts will be referred to by their authors. Though all of the books contain relevant material, not all are specifically referenced in this book. In particular, all mentions of [Harary] refer to Graph Theory and not to A Seminar on Graph Theory. The author would like to thank Chris Van Wyk and Jim Boyce for their assistance in preparing the manuscript, Don Knuth and Ron Graham for encouraging the publication of the notes and, of course, Professors Pélya and Tarjan for providing ample source material.COMBINATIONS AND PERMUTATIONS 3 southward one-tenth the total southward distance between the two corners.) It was decided empirically (i.e, by taking a vote) that there were more than 100 paths, but there was disagreement over whether there were more than 1000, so Pélya proceeded to approach the problem by more formal methods. He began by emphasising an important maxim which you should always consider when working ‘on any problem: “If you cannot solve the proposed problem, solve first @ suitable related problem.” In this instance, the related problem is that of computing how many different paths there are from the northern corner to various other corners, still restricting ourselves to travelling only southeast and southwest. For starters, there is only one path to each of the corners on the northeast edge, namely the path consisting of travelling always southeast and never southwest. Similarly, there is only one path to each of the corners on the west edge. ote ues by corners involved. Now what about the corner marked with a #? Yuu could get by going one block southeast followed by one block southwest, or by going first southwest and then southeast. Similarly, 10 get to the corner marked *x, you could go southeast, then southwett twice, or4 NOTES ON INTRODUCTORY COMBINATORICS you could go southwest, then southeast, then southwest, or you could go southwest twice and then southeast. Moving down the diagonal in the manner and, by symmetry, the corresponding diagonal on the eastern side, we can fill in some more values. Had we tried to go much further like this, it would probably have gotten rather tiresome, so instead we came up with a general observation regarding an arbitrary corner, such as the one marked z above. If we know that there are x ways to get io the corner just northwest of z, and y ways to get to the corner northeast of z, then there are x+ ways to get to z, since to get there we must first get to either x or 3, after which there’s only one way to continue on to z. For instance, there are 3+3=6 paths to the corner marked *. This general rule provides us with an easy method to finish computing the number of paths to the southern corner. The first homework. assignment was to complete this computation. It comes as no surprise that everyone got it right. For the record, here it is.COMBINATIONS AND PERMUTATIONS 5 The numbers we've been computing are known as binomial coefficients, for reasons we'll get to eventually. The arrangement of the numbers, when cut off by any horizontal line so as to form a triangular pattern. is known as Pascal's triangle. (Pascal referred to it as “the arithmetical triangle") The numbers are uniquely defined by the boundary condition (the 1's along the edges) together with the recursion formula (each number not on the edge is the sum of the two above it). In addition to this recursion formula, which defines each number in terms of earlier ones, there is another way to look at the situation. Here's a small chunk of the street network we've been working with: oO Suppose we want to know the number of different paths (of minimum length) from the origin O to the starred corner. Each such path must consist of 5 blocks, of which exactly 3 go to the right (as seen from above). If we specify which 3 of the 5 blocks will go to the right, we uniquely specify the path. For instance, if we choose the 1®, 4th, and 5th blocks, we get this path: oC Conversely, each path from O to ® specifies a unique set of 3 blocks that go to the right. So the number of paths is the same as the number of ways of choosing 3,blocks out of the total 5. Euler's notation for this sort of thing is (3) OF, in general, (7), denoting the number of ways of choosing a subset of size r from a set of size n.6 NOTES ON INTRODUCTORY COMBINATORICS This is usually read “n-choose-r”. (Another name often heard to describe this value, but which recently has fallen out of favor, is that used by Jacob Bernoulli: the combinations of n elements taken r at a time.) Computing this value is the first problem of combinatorics. Next we come to some basic rules for working with multiple sets. The rules are fairly simple (as basic rules are wont to be), but are nevertheless very important (again as basic rules are wont to be). First off, suppose that out of a set of possibilities, A, it is possible to choose any one of m different elements. From another set, B, it is possible to choose any one of n elements. We wish to select an element from either A or B; we don't care which. Assuming A and B have no elements in common, there are m+n possible choices. Next. suppose the elements of A are a:. do..... a,,. and the elements of B are by, by, ..., by. We wish to select two elements, one from each set, in a specific order (say, first one from A and then one from B). This operation is known as the Cartesian product of the two sets, due to its relationship with the rectangular (Cartesian) coordinate system. For instance, if A has three elements and B has two, there are six possible pairs: (21,51), (412), (a2b1), (42,50), (@s,b1), and (a3,2). In general, there are m-n possibilities. Finally, take a more general case of the Cartesian product. Suppose that, having chosen aj, we then have a choice among a set of elements bj), b)z,.--, bine If we start by choosing az, we then have a choice from a different set: bo, bo2,..-+1 ban, and soon. In general, the possibilities for 6 differ depending upon our choice for @, but there are always n of them. As long as the number of possibilities for 6 is constant, the total number of pairs (a,,bj) is still men, We'll see an application of this in a moment. A permutation is an ordering of a set of objects. For instance, given the set of three numbers {1,2,3}, we could order them in any of 6 different ways: {1,2,3} {1,32}, {21,3}, {2.31}, {21,2} or {3,21}. The number of different permutations of n elements is denoted by Pj. Hence Ps = 6. We also see fairly easily that P) = 1 and Pp =2. At this point Pélya stated another important maxim: “The beginning of most discoveries is to recognise a pattern.” There is a pattern to the three numbers we've got so far; to make it more apparent, we can rewrite them as follows:COMBINATIONS AND PERMUTATIONS ed Pyetel Poa Quel +2 Py a Gul +263, We conjecture that P, = 1+2+3+...+n. This product is called n factorial and is usually written “n!”. Now we need to prove our conjecture. Well, suppose it's true that P, = n!. Then what would P,,, be? It is the number of ways of ordering n+1 objects. The n+1* object could be in any one of n+1 positions. Whichever of these positions we choose, the remaining n objects can be ordered in any of P, ways. Using the generalisation of the Cartesian Product rule, we conclude that the total number of ways we can order n+1 obiects is (n+1)sP,. Therefore, if P, 2 1+2+%« on, then Py = 1+2+3+...¢ne(n+l) = (n+l). But we know that Ps = 31, so taking n=3 we conclude that Py = 4. Knowing this, we can take n=4 and conclude that Ps = 5!, and so on. For any finite n, we can prove that P, = n! by starting at Py and chugging away for a while. This method of proof, which Polya describes as “a diabolic way of proving things”, is called mathematical induction. It is extremely useful since it saves you from having to figure out the formula you're proving. If you can make a “lucky guess” as to what the answer is, you may be able to prove it by induction. yr 10. Pélya began the lecture by reviewing the January the previous lecture. In doing so he brought out some points that hadn't been explicitly stated before. In particular, there's the formal definition of the binomial coefficients: Boundary condition: (5) = (") = 1 Recursion: (8) 40). th'and + integers, Ocren+1] Similarly, P, can be defined by boundary conditions and recursion: Boundary condition: P, = I!= 1 Recursion: P, = nie Py). If we apply this recursion formula with n=l, we find that P, = 1+Po. Hence we define Po = 0! = 1.8 NOTES ON INTRODUCTORY COMBINATORICS From here, we move on to look at something Pélya called a “variation”, a word you may immediately forget. It is defined as follows. Given a set of n objects, we wish to choose r of them in some order. That is. choosing the first obiect and then the second would be considered different from choosing the second and then the first. How many such variations are there? One approach is to Start by choosing some object to be the first one selected. There are n choices. For each choice, there are n-1 choices for the second object. Thus, by the product rule, there are n(n-1) choices for the first two objects together. For each such pair, there are (n-2) objects remaining from which to choose the third object. So there are n(n-1Xn-2) choices for the first three objects. Continuing in this manner, we find that there are n(n-1Xn-2) . . . (n-r+1) variations. We can often learn something by solving a problem in two different ways, so here's a second approach. We first choose the subset of r objects from among the n. We know there are 0 ways to do this. We then choose the ordering for the r objects. We know how many ways there are to do this, too; it's P,. So there are (")P, variations. But this answer must be the same as the one we got the other way. Therefore (7)P, = n(n-1Xn-2)...(n-r1). So we have learned something new: (n= 1Xn-2) ... (n-r+1 ¢) 2 Xn: 1, (n-r+1) (n=1+ 1 er 1. R(n=1Xn-2) . 1+2s3 (Note that, in the ¢ panding’ terme in nd form, the sum o! the numerator and denominator is always n+1; this can be a useful mnemonic for remembering what the last term in the numerator Is.) For example, the number that we computed for the first homework assignment is (,), which by this formula is (10+9+B+76)/(1+2+3e4+5) = (10+9+746)/(1+3+5) = (2+9+796)/3 = 2+9+7+2 = 252 It’s always a good idea to test out a formula on some special cases where we already know the answer, so let's look at (7) and (3), We have iH () = MnetXn=2) T+2e8e...en" which, since the numerator and denominator have all the same(COMBINATIONS AND PERMUTATIONS 9 factors, albeit in different orders, indeed equals 1. (5), however, Poses a bit of a problem, since the numerator has no factors. By defining the product of zero factors to be equal to | (just as 0! = 1) we find that (¢) = 1 as expected. Another way we can get this explicit form for the binomial coefficients is by using mathematical induction. We assume it’s true for small n (we can check this by hand) and then show that, if it’s true for n, it’s true for n+l. The first problem on the second homework assignment was to carry out this proof. Here it is: We assume that, for some value of n, ty MentMn2) (nara) if P+2eSe..er for all values of r. Substituting r-1 for r, we find (ty ancl (n-2) (n-r+2) re 1280... e (rel) ” By the definition of the binomial coefficients, we know that war (nora2) , nino Xn-9) (nora t) (el) 12-36 in-r+2) or , n(n-1Xn-2) - (r-1) ¢7 1+2+8 oe Bn=IYn-2) . (n-r42) + (r+ nor! erieaisie (r-l) or nt I)n(n-1X(n-2) (n-1+2) T+2¢36, or which is the formula we're trying to prove (with n+1 substituted for n). Hence, if the formula is true for n, it's true for n+l. This, combined with the fact that it’s true for n=1, means it is true for all finite n. (Actually, there's a minor flaw in this proof. To wit, Wa a cannot be used to compute (") or 0), la cannot be used te compute (1) or (), 2! involve coefficients outside the range Osrsn. However, we've already shown separately that these two special cases satisfy the formula, so we're all right.)10 NOTES ON INTRODUCTORY COMBINATORICS A more compact way to write the formula for the binomial coefficient can be derived by multiplying both the numerator and denominator by the factors (n-r), (n-r-1), and so on down to I. (*) = B@el n=2) (0: Dede ere Qe... slat alee) nt ri\(n-r)! Notice that, based on this formula, it is immediately apparent that C) =). This was to be expected, since by the method of its construction Pascal's triangle is clearly symmetric. Next, we consider n houses. They are built identically, because it's easier that way. But then, to make them look different, they are painted different colors: 7 of them are painted red, s of them yellow, and the remaining ¢ of them green. In how many ways can we assign the colors to the houses? We first choose which houses will be painted red; there are (") ways to make this choice. Whatever choice Sera fei, of which we ciwuse 3 iv be painted yellow; there are (".’) ways to do this. At this point we have No choices left to make, since all the rest must be green (that is, rrsttan), So what do we have? By the product rule, there are (CX'S’) ways to paint the houses, Using the formula we worked out a moment ago, we find n-r}t a * ny But n-r-set, and the (n-r)! factors cancel, leaving us with nt ristet’ which is, fortunately, symmetric with respect to r, s, and t. (The alternative to its being symmetric would be for it to be wrong, since the original problem was symmetric.) This sort of formula is called a _ multinomial coef nt,Generating functions are a general mathematical tool developed by de Moivre, Stirling, and Euler in the 18% century, and are used often in combinatorics. As usual, we start by taking a concrete example: In how many ways can you make change for a dollar? We'll assume that we're dealing with oniy five types of coins—pennies, nickels dimes, quarters, and half dollars. We first consider how many pennies to use. We could use one, or two, or three, etc., and of course we could use none. We can show these choices pictorially: bb] © OO GOO Similarly, we have an infinite number of choices as to how many nickels we use (although for almost all such choices we'll have more than a dollar already), and how many dimes, and so on: Lb] © ©© OO© [2] L] @ ©® O©®8 In giving change for a dollar, or for any other amount, we are effectively choosing exactly one ‘heap’ from each of the five rows. Within each row, we'll represent the fact that we are choosing a single element by writing the row as a summation: 2]+O+OO+OOO*-- Next, we represent the combining of the choices from the various rows by writing the product of the rows (the reason for all this will be seen shortly). 2] °12 NOTES ON INTRODUCTORY COMBINATORICS (Gye +O+O0O+000++) (2]+@+@O+QOO+:-?) (G @+@@+O@ QOO---” ) x ((0]+@) +@@ + OOS) +--- Now, why did we do this? Well, if we look at the infinite product we've created, we find that each term in the product is the product of five terms, one from each of the sums. Thus, each term of the Product corresponds to a different combination of coins. and if we look at all the terms of the product, we'll find they include al? such combinations. ° But we don’t want all combinations; we just want the ones that add up to a dollar. Pélya introduced the symbol x to represent 1¢. So, for example, OOO -#-#. GO = = 2" and [o]-#" Our product can now be written more mathematically as follows: (aes ae) oa ahs al a eg (Le xl 4 eM (14 84 Og wy (Let lg tO For example, one of the terms in the product will be xS+x*+x"+ | «x, which corresponds to the combination of coins that consists of 3 _ pennies, 1 nickel, 2 dimes, no quarters, and | half dollar. When the five terms, one from each infinite sum, are multiplied, the exponents add; this is just what we want, because it means the exponent (in our example it’s 78) is the total value of the selected coins. So for each combination of coins totalling one dollar, there will be a term in theGENERATING FUNCTIONS: 13 Product with an exponent of 100. If we combine terms that have the same exponent, we get something of the form Lt Eyx + Eqx? +--+ + Eyoox! +--+ January 12. All we need to do is find the coefficient Ejo9. But how do we do that? We could try multiplying out the infinite product, but this would probably take a while. Instead we use what we know about series, and in particular about geometric series. Consider a typical geometric series: 1 + x + x2 + x +--+. What does this series sum to? Pélya claimed it was obvious: the sum is S. That doesn’t sound like it helps much but, having given it a name, we can manipulate it mathematically. In particular, we can multiply $ by (1-x). S(l-x)= Le xexte xe =-xe- =x. SoS = Il-x). Similarly, 14 x2 4 x! 4 x! 4..e= lex), Our infinite product thus simplifies to the somewhat more compact form (21-2 XxX 1-2 X 1-2) * which we can turn back into a series in powers of x, even though we don’t yet know the coefficients numerically, as 3 Ex" 2, E,x". Such a summation, in either form, is called the generating function for the sequence Ep, Ey, E»,.... Rotlpevanrlctiosertte to be any closer to Su far su good, but we don computing Eioo than we were before. Once again we'll try first solving an easier related problem. In fact, we'll set up a sequence of problems leading to the one we're interested in.4 NOTES ON INTRODUCTORY COMBINATORICS a BAe 1 = n (xX 1-29) 2, Bet nO 1 Sox Taxi Kw” Z, Cn ! . z D,x" (aX 1X xX 1) eo ; = 5 Ea inxXi-x Ki-x "Ki-xKi-x) 0 We already know that A, = | for all n 2 0. What about B,? We take the second equation above and multiply both sides by 1-x°. The left side becomes 1/(1-x), which is series A. Ans" = (2X2 B,x") = (2 Byx") (2 Byx™*) nO m0 What does it mean for these two sums to be equal? Since they must be equal for all values of x, it means that the coefficients of x" must be equal for all n. On the left side the coefficient is simply A,. On the right side, the first summation contributes a term of B,x", and the second summation contributes -B,.5x" (coming from multiplying (-x*) by B,.5x""). Therefore Ag = By - Bus ars or, rearranging things, B, = An + Bas. By the sane reasoning we van abuGENERATING FUNCTIONS 15 Ch = Bat Caio nge Dye Cy + Dpgs 07% E, = Dy + Enso 9 175° For boundary Conditions, we know that none of the series has any terms with x" for n < 0, and so A,=B,=C,=D,=E,=0 for n <0. We also know that A,=1 for all n 20. Armed. with this information, we can compute B, for 7 2 0, making use of the recursion formula we've just worked out. Thus, Bo=Ao+B.s=1+001, By =A ,+B_4=1+001 Bs=Ag+Bo=1+1=2, etc. Once we've worked out some of the B's, we can start computing C's, and so on. Even so, working all the way out to Eioo by hand could be time-consuming, though it wouldn't take long using a computer. But we can save a lot of effort by observing we don't need até the intermediaie numbers. Tu vumpuie Eyo9 we need to know Exp, and to compute that we need Eo. We also need Diop, Dsp, and Do. To compute those, we also need to know Djs and Dzs, and so on. So if we plan ahead a little bit, we can compute only those elements we actually need. Pélya demonstrated the process by beginning to fill in a table with n= 0, 10, 20,..., 100. The second problem on the second homework assignment was to finish the computation and find Ejo9. (Pélya also provided as a hint that Ex) happens to be 50.) He failed to point out that some intermediate multiples of 5 would also be necessary, but everyone seemed to figure that out anyway. The following table shows the minimum number of entries that need to be filled in to get the final answer of 292. (Some of the entries, such as Bg, and Bogs, could be left out by observing (and proving) some simple patterns, such as B, = An+By-s = Ant(Anes+Breio) = 2+Breto for n 2 10, but we'll work them out anyway.) 5 10 15 90 95 89 85 40 AK HD 54 AO BS N75 RO BS 90 95 100 n o Br 12 3 4 5 6 7 8 9 10 It 12 13 14 15 16 17 18 19 2 2 Cc, 1 2 4 6 9 12 16 20 25 30% 42 49 5% 64 72 8! 10012 De 1s 49 121 249 E, ' ” 292 Here is a summary of some of the more useful rules regarding generating functions. Suppose we have two generating functions:16 NOTES ON INTRODUCTORY COMBINATORICS Ble) = ag + yx + age 4 eee aga HH Wx) = by + Bix + box? +++ + Dye Hoe Then: (1) B(x) = A(x) ao=bo, a)=b), dombo, etc. [2] lx)+Alx) = (agtbo) + (a,4b,)x +--+ (Gq tbyle™ +> (3) B(x) A(x) » (agby + aod) x + agbyx? +--+) + (@ybox + @1b)x2 + aybox? +--+) + (agbox® + anh, x9 + anboxt +--+) Peet = (abo) + (@qb,+2)bo)x + (Aoby+a4; +aqbo)x? + - + oH KH Qe EM ee, where ¢y is defined as = dob, + G)by.) + Cabp.g + +++ + Ondo. January 17. Generating functions worked well on the problem of changing a dollar; let's try applying them elsewhere. We'll start with something we already know about—binomial coefficients. Suppose we have a set of n objects {x,, Xo, ¥5,..., Xn}, and we wish to choose a subset of r objects. We either choose x, or we don't. As before, we'll represent this choice by a sum of the possibilities, (x,°+x,'), or simply (1+x,). Similarly we have (14x), (l4xs), and so on. We again represent the combination of choices by a product: (14x, 14x9X 14x5) ... (14xq). Each term of this product constitutes a selection of exactly one term from each of the n sums, which corresponds to a selection of some number (not necessarily r) of objects from the original set. For instance, if we choose the x, from the first sum and the 1 from each of the others, we get the term x,. The product comes out to Le my tg ey tt ey + XX + Ny Xy + Noy to + My HX KyXy + KypXoXy te + Kp open + XX grey... Xp The number of ways of choosing, say, two x's is the number of terms that contain exactly two x's. So let all the x; be equal, that is, letGENERATING FUNCTIONS 17 Hy = xy 2 xyes eq x, Then (LX Leg Lg). (tatg) = (142) 0 ag 4 aya + age? 4 + ag”, It’s clear that ao is 1; what about @,? It is equal to the number of terms in the product that contain exactly one x, which is therefore a <0. 5 a =). & a2 = the number of different subsets of size 2 = (2), and so on. For that matter, ap = 1 = (5). We can summarise all this in one handy equation: : (lex) = E(t, fo This is called the “binomial formula” (because 1+x is the “basic” polynomial of two terms); hence the name “binomial coefficients”. Pélya next brought up a third maxim: “/f you have a general formula, try it our on some special cases.” One special case is x = 1. This gives us Mae Mee + Oh which is the number of subsets of all sizes from a set of size n. This checks, since for each object we have two choices—either it is In the subset or it isn't. We have n such choices, and by the product rule the total number of possibilities is therefore the product of n 2's. Another interesting special case, which didn’t come up in the lecture, is that of x = -1: OF C= 4 C= COND, That this sum should be zero is obvious when n is odd, due to the symmetry of Pascal's triangle. When 1 is even, however, the above result is less obvious, so this identity is worth noting. Note in particular that, substituting the value n=0, we can deduce 0° must equal |. Let's consider the combinations of 2 objects with repetition taken r at a time, which we'll denote by R‘". We can also think of it as having n kinds of objects, with an unlimited supply of each, from18 NOTES ON INTRODUCTORY COMBINATORICS which we wish to select r objects. Let's find the generating function for this. Just as when we were looking at ways to break a dollar, we can have no x,'s, or one x, or two, or three, etc. and we'll write this as the sum 1+x,+x,%,+%)%|%,+ +++, and similarly for each x in the set. We take the product, (Dx +2) 4% XpRpH ++) § (Lt XoAMoNoAKoXoXot +) Oo. . © (Lae teptnttntntnt ++), So that, as usual, each term of the product corresponds to one of the possible selections. We're interested in the selections that include exactly r x's (not necessarily different x's), and we don’t want to distinguish among the x's, so we let x; = xo = +++ = x, = x, and get (Levande 6) Each term that selects exactly r x's contributes | to the coefficient of x", so that’s the coefficient we want. Well, we already know what the geometric series sums to, so what we've got is GLY Lee ROE, Let’s digress for a moment and examine a useful generalisation of binomial coefficients. Newton defined (*) for non-integer ot as (2) = eleteIXee-2) « . (oe=r4 iy 1e2sSe...e7 and claimed that, if kxl<1, tS A (tex) = EG! for all o. Newton didn’t actually prove this (rigorous proofs were not recognised as being necessary in his day), but Gauss proved it in 1812, We won't bother to show the proof here. Using this result, we find (yt = BGMGENERATING FUNCTIONS 19 Since R$” is the coefficient of x" in this sum, we find RM = CM-I ~ &nX-n-1X-n-2) ... (-n-r+l) ¢_ yy LeQeSe.er cy. Combining the r factors of -1 with the r terms in the numerator, we find that RO» Bnel (n+2) ... (ntr-1 if 1+Q+Se ler icra) - (nt r a perfectly ordinary binomial coefficient. As usual, we'll try to confirm this by proving it another way. Suppose we have n kinds of objects, x;, %2,...,%,. We select r objects, and set them down in order of increasing subscript, with “separation points” every time we come to a different kind of object. For example: XX Oxy XyXo%yOxye@ ... OXp~Xy. Even if we have no x, for some {, we'll include the separation point: 00x, 00x58 |. Oxy 1 Xp-1% Thus we always have r objects plus n-I separation points. Once we choose the positions of the separation points, we have completely determined the set being selected. Everything ahead of the first separation point consists of x,'s, everything between the first and second points is x2, and so forth. Thus there are as many subsets of size r (with repetition) as there are ways of selecting n-1 separation points from among r+n-1\ possible positions (without repetition). This number is, of course, ("*",'), which by the symmetry of binomial coefficients (é.., (")=(,",)) is equal to our earlier answer. AL this point Poiya assigned as “non-obiigatory nomework” two observations that had nothing at all to do with generating functions, but were simply things that people might find interesting20 NOTES ON INTRODUCTORY COMBINATORICS to investigate. Consider Pascal’s triangle, shown (in part) below. 1 5 18 18 5 1 1 6 15 26 15 6 1 1 7 21 35 35 2k 7 21 1 8 2 56 78 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 16 45 126 216 252 2186 128 45 16 1 (Please pardon us for not showing all of Pascal's triangle; infinite tables use up too much paper.) The first observation was that, for certain values of n, all of the values in row n (remembering that the top row is row 0) except the first and last elements are divisible by n. For instance, in row 7, we have 7, 21, and 35. Pélya pointed out that this happens whenever n is prime, and suggested it as a topic for further thought. Well, let's think about it. Why should (?) be divisible by p whenever p is prime and Ocrep? For the answer, look at the formuta for (°). te IXp-2) (poral pede deer Note the factor of p in the numerator. Since p is prime, it’s not going to cancel out against anything in the denominator unless it's another p. And the denominator won't include a factor of p unless r=. (At the other end, if r = 0, the numerator has zero factors, so the factor of p never occurs at all.) Hence for O ns “by22 NOTES ON INTRODUCTORY COMBINATORICS where all the a’s and 6's are integers, then: (1) If the a’s contain more factors of two than do the b's (this is not the same as the number of even numbers since, for example, 24 counts as 3 factors of two), then k is even, since not all of the twos in the numerator will be cancelled out. (2) If the a’s and 6's contain the same number of factors of two, then k is odd, since all of the twos will cancel, leaving a product of odd numbers in the numerator divided by another product of odd numbers in the denominator. (3) The 6's cannot contain more factors of two than do the a's, since k could not then be an integer. We hope that these assertions are intuitively obvious; rigorous proofs require too much number theory to be included here. At this point we're ready to state the main theorem we need for this analysis. It is this: If n is even and r is odd, then (7) is To prove this, first consider the case where n is even and r is odd. We have (%) » Bn=1Xn-2) (nore l) id 1e2eSe..er aH, (M-1Xn-2) (ner) r LeQeBe...e (rl) Reet (To justify this completely we must observe that, since r is odd and Osrsn, we know Osr-Isn-1.) Now let an, ag=("|), and bj=r. Since n is even and 7 is odd, regardless of what (") is (it's an integer; that's all that counts), the lemma says that @)@o/b, = (") must be even. Next we'll consider the tricky case—n and r both even. We again start with (- n(n-1Xn-2) ... (n-r+l) | saa ash 7 We observe that the factors (n-1), (n-3), ..., (n-r+1) are all odd, as are 1, 3, 5,...,(r-1). By the lemma, these factors can be ignored so far as the even/oddness of (7) is concerned. This leaves r/2 terms in both the numerator and denominator, ail of them even:GENERATING FUNCTIONS. 23 n(n-2){n-4) ._. (n-r+2) 2°4°Be.er | We divide each of the terms by two, which doesn’t affect the value of the number since there are the same number of terms in the numerator as in the denominator, and are left with sn(in-1(tn-2) ... (in-Hr+1) 1eQeSe.llegw 7 All we've done is throw away some factors that were odd (and therefore contained no factors of two), and divided out an equal number of twos from top and bottom, so by the lemma this new number is even if and only if the original number, (7), was even. But this new number is simply (2), Since, for k even, |k/2] = (k/2), we have proven the theorem for n and r both even. Next, suppose n and r are both odd. Then by our earlier reasoning we know (= 2 eh, Since n ra 7 are both odd, the lemma tells us that (7) is even if and only if ea Hy is even. But Pal 1 and r-1 are both even, so this is the case we've just shown: (1) is even if and only if une is even. Since, for k odd, [k/2] = ((k~1)/2), we have proven the “neorem for n and r both odd. Finally, suppose n is odd and r is even. Then we know n #1, so we can multiply (") by (n-r)n-r) to get (ty = Be. (eel). (rere Xn) r nr PeQeB3e..cer 2h nr Since n is odd fle ner is odd, the lemma tells us that (7) is even if and only if ° y As even, and the theorem quickly follows as in the other cases. We therefore have finished proving the theorem. So much for the hard part. Now let's use the theorem to get24 NOTES ON INTRODUCTORY COMBINATORICS our final result. First we make two observations regarding the binary representation of a number n: (1) n is even if and only if the last binary digit is a zero; (2) the binary representation of |n/2] is the same as that of n except the last digit is removed. So by our theorem, (°) is even if the last binary digits of n and r are 0 and 1, respectively. If they're not, then we look at [n/2] and Lri2}, If their last digits are 0 and 1, respectively, it means that (j7m) is even, so (7) is also even. Otherwise we look next at [[n/2/2] and |[r/2J/2], and so forth. But wait a moment; the last binary digits of [n/2] and |r/2J are simply the next-to-last digits of n and r, and the last digits of ULn/2y2) and [[r/2)2J are the third-to-last digits of n and r, etc. Thus (") is even if, in any digit position, the binary representations of n and r contain a 0 and 1, respectively. And what if they don’t? In that case we continue discarding digits off the ends of the two binary representations. and eventually are left with nothing but zeroes. Since «) = I, which is odd, (” ;) Must also be odd. For example, 4510 = 101101, and 20iq = 10100. Since the latter contains a 1 in the fifth digit from the right, whereas, athe corresponding digit in the first number is a 0, we know that & is even. On the other hand, since 1219 = 1100, which contains zeroes wherever 45 does, we know that (2) is odd. (Feel free to check these results; we did!) Okay, we're almost done (finally!). How many numbers in row n of Pascal’s triangle are odd? This is the same as asking how many numbers r between 0 and n (inclusive) have zeroes wherever n has zeroes in binary notation. How many such r are there? Well, r's binary representation has zeroes wherever n’s docs. Wherever 7 contains a 1, however, r can contain either a 1 or a 0. We don’t have to worry about making r larger than n since, even if we put I's in all such positions, all we get is n itself, and that’s the largest we can possibly make r. So, letting -(n) represent the number of I's in the binary representation of n, there are exactly V(n) binary digits in y that can be either 0 or I, and the rest of the digits must be 0. By the product rule we have “gh possible values for r, and therefore there are exactly that many odd numbers in row n of the triangle. There's a completely different approach to this problem. It involves looking at the pattern of even and odd numbers. If we represent an odd number by a * and an even number by a blank,GENERATING FUNCTIONS 25 then the top 64 rows of the triangle look like this: top 32 rows is dupiicaied on buii sides in the next 32 rows, with nothing but even numbers in between. You might like to give some thought to how you might go about (a) proving this replication pattern in general and (b) using it to prove that row n contains 2%” odd numbers. Enough already about Pascal's triangle! Let us proceed with the course notes. January 19. We wish to dissect a convex n-sided polygon into triangles by adding non-intersecting diagonals. In how many ways can this be done? For example, a convex quadrilateral can be dissected into triangles in either of two ways:26 NOTES ON INTRODUCTORY COMBINATORICS A pentagon can be dissected in any of five ways: We shall denote by D, the number of possible dissections of a convex n-sided polygon. We can easily work out the first few values by hand: Ds = 1, Dy = 2, Dy = 5, Dg = 14. At about this point it starts getting difficult, and there's no obvious pattern yet. (If we could find a pattern we might be able to prove it by induction.) Let's see if we can find a recursion formula. Take a polygon with n sides, Pick any side and call it the “base”. For instance, in the octagon drawn below (left), we've chosen the thick edge as the base Having selected a side to be the base, there must be (for any particular dissection) a unique triangle that includes the base (see below right). This triangle divides the original polygon into two smaller polygons. Suppose the polygon to the left of the triangle has k sides, Then the other polygon must have n+1-k sides, because the two together include all n of the original polygon’s sides, except for the base, and also the two dotted sides, for a total of n+1 sides. By definition, we know that there are Dy ways to dissect the k-sided polygon. Each such dissection can be combined with any of the Dyei-x possible dissections of the right-hand polygon. By the product rule, the original polygon has Dy*Dysi-. dissections that include this particular triangle at the base. Meanwhile, k can take ‘on various values, depending on what triangle actually includes the base. One particularly strange case that we'll have to watch out for is the one shown on the following page where, once the triangle 1s removed, we're left with only a single polygon of n-I sides.GENERATING FUNCTIONS 27 There is, of course, a similar special case with the dotted diagonal a up to the right instead of up to the left. By the rule of sums (way back on page 6 of these notes) we add the configurations for each base triangle and get Dp = Dp-y + DsDp.n + +++ + DaDnsi-n +°°* + Dp-2Ds + Dy. This would be sufficient if all we wanted to do was program a computer to evaluate D,, but from an aesthetic standpoint it’s not pleasing. Suppose we consider a single edge to be a polygon of 2 sides—up the edge and back along the same edge—and let Do = 1. Then our equation becomes somewhat more regular. Dy = DaDy1 + DsDpz + +++ + DgDngi-k + +++ + Dy-gDs + Dy.1Dz Now then, this chapter is supposed to be about generating functions (in spite of all that stuff about Pascal's triangle), so let's Make use of them. We'll define G(x) = Dox? + Dyx +--+ + Daxt ees. (Pélya describes this as “putting all the D's in a ‘bag’.”) Recalling the formula for products of generating functions, we take a look at the square of g. Cetey? = ( ED )-( 2 Dx!) . 3 3 D,D,x** ez Lek = DgDoxt + (DyDy+DgDo)x? +--+ + (DoDq-1+DsDy-2+-+D yy.) Do)x""' + +++ But from our recursion equation, we know