COMBINAT & GRAPH THERO I
COMBINAT & GRAPH THERO I MATH 681
U of L
Popular in Course
Popular in Mathematics (M)
This 36 page Class Notes was uploaded by Rafaela Bruen on Friday October 23, 2015. The Class Notes belongs to MATH 681 at University of Louisville taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/228343/math-681-university-of-louisville in Mathematics (M) at University of Louisville.
Reviews for COMBINAT & GRAPH THERO I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/23/15
MATH 681 Notes Combinatorics and Graph Theory 1 1 Recurrence relations continued 11 Linear homogeneous recurrences solved with exponential generating func tions We saw that we could apporach a recurrence with ordinary generating functions What if instead we used exponential generating functions with x 2200 an7 Let s try it with the Fibonacci nubmers in particular for discovery purposes 00 it 00 it ZFTL2H ZltFn1 0 n0 As before we ll manipulate these until we get several copies of x but not all of our manipulations will be algebraic 2mm 20ml Fog 0 n0 CO CO 00 d2 n2 d n1 mn F 77 F if F i Z n2dx2 n2 Z n1dx n1lZ nnl n0 n0 n0 d2 00 x d 00 x 00 x 321 2an t 2an n2 n1 n0 d2 00 x d 00 x 00 x 7 F ii F i F i alng 711 l lanj 711 71 WW fg I M So our exponential generating function is surprisingly the solution to a di erentz39al equation We have been skirting differential equation all along with recurrence relations such phrases as linear homogeneous initial conditions characteristic polynomial and order k are more than a little evocative of DE terminology and here we have a direct relationship between a recurrence and a differential equation In fact note that this linear homogeneous differential equation has the same order and characteristic polynomial as the associated LHRR and even to a certain point the same initial conditions O F0 1 and f 0 F1 1 Solving the differential equation f x f x x is a matter of identifying its characterstic polynomial x2 7 r 7 1 and then its roots r Thus we know the exponential generating function x keg gm 5196 Since O follows that k t 1 and since Ho 1 it follows that Lfk z 1 This is a system we ve solved before to give k 57165 and Z 51355 so 575612gm 5x51i2x5m m 10 10 5 Page 1 of 4 October 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 and note that we can get individual coefficients using power series expansions 1035 7516551 T w 75 1655wa 00 177 00 n0 n0 57 517 5n 5 51 Snzn Zl10lt2gt10lt2gtl n0 We could do the same thing with an arbitrary recurrence relation If we let x 2200 an where ank clank71 0201 er aka then i n n anki l ClanJrkil 62ank71 titan iM8 n 0 00 k nk 0 kil nk71 00 n d m d m m Emmi 61217 6217 0 dm nk 0 dm 1nk71l 0 ml TL 71 r L dk 00 mn dkil 00 mn 00 mn 7 aici aic If dmk k 71 ldmk l 21 71 kg 71 n r L 7 dk 00 mn dkil 00 mn 00 mn mganmwmgwwwgw NW 61fk 1m c2100 z ck71f ltzgt are so the exponential generating function for any linear homogeneous recurrence relation is the associ ated linear homogeneous differential equation Note also that the initial conditions from the LHRR map to initial conditions for the LHDE straightforwardly f0 a0 f 0 a1 f 0 a2 and so forth 12 Linear homogeneous recurrences with repeated roots Recall our original LHRR solution methodology nd the distinct roots r1 r2 7 of the charac teristic polynomial identify every solution as a linear combination of the sequences TEL determine necessary coefficients for a particular solution However this method relies on the presumption that the characteristic polynomial has k distinct nonzero roots This is frequently the case and even though the roots may be irrational or even complex this is not intrinsically problematic as irra tional and complex values are subject to the same arithmetic manipulations as any other type of number The only problem we can have is if there are not k distinct roots or if roots are zero The Fundamental Theorem of Algebra guarantees us k roots but some could be identical or zero Zero is not a problem In order for a LHRR to have order k the coefficient ck must be nonzero otherwise an would not depend on mkk so it could be considered as a lower order LHRR Thus the constant coefficient in the characteristic polynomial is nonzero so zero is not a root of the polynomial Page 2 of 4 October 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 The repeated root case is subtler though It s not much of a problem in the ordinary generating function or exponential generating function regimes though since it simply requires that we know how to deal with repeated roots in the denominator of a partial fraction decomposition or the characteristic polynomial of a differential equation In fact we could use either or both of these methods to answer this question preperatory to nding an answer which does not use generating functions Question 1 Find the general form of a sequence satisfying the recurrence relation an Alanil 7 40 Answer 1 We might approach this using an ordinary generating function the methods we determined last week indicate that this would have generating function T1112 where Px is a linear function determined by the initial conditions Using known partial fraction rules we would decompose this as m for k and 6 determined by Px which we 172x2 could then conuert back to x k 2m l 2 n 1 235n Em limp n0 n0 n0 so the general form of a sequence satisfying the aforementioned recurrence relation is a linear combination of the completely expected 2 and the somewhat more surprising We might do the same thing with an exponential generating function If gx were an exponential generating function for a sequence satisfying an 4an1 74an2 then we would know based on the deriuation aboue that gquotx 4gx7gx which would have characteristic polynomial x274x4 which has 2 as a root with multiplicity 2 leading to di erential equation solutions e2m and xezm As before we can pull indiuidual coe cients out of this with ease gx kezm lxezm 00 00 n1 7 2 n7 2 n 7 k 0 2 nl Z 0 2 nl n n 00 x l 00 n 1x 1 k 2L 7 2 00 x l 00 nx 7 n7 7 n 7 22 nl 2 2 nl n0 n1 kigni 2n 0 nl 2n0 nl 00 n 2 k2 712 1 2 nl n0 We can justify this in our original blissfully generating function free regime We start with a useful lemma Lemma 1 If a polynomial Px has a root x of multiplicity q then Px has x as a root of multiplicity at least q 7 1 Inductiuely it follows that Pix has x as a root for all 0 g i q 7 1 Page 3 of 4 October 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Proof This is a relatively inductive straightforward application of the product rule Pm m 7 rqpz for some polynomial Then Pm WE rq 1p rVia90 96 rq 1lqp p l Since P z can be factored into a product of m 7 r 1 and a polynomial P z has r as a root of multiplicity at least q El Theorem 1 If the characteristic polynomial of the linear homogeneous recurrence relation an clan1 ckan4 has root r with multiplicity q then r nrn 7 1r 7 1n 7 2 n 7 q 7 1rn all satisfy the recurrence relation Proof Since the characteristic polynomial has root r with multiplicity q we know that Pm zk 7 clmk l 7 02 7 7 ck has a zero of multiplicity k at r Likewise for any n Pnm z kPz m 7 clmn l 7 7 ckmn k has r as a zero of multiplicity k By the lemma above it follows that P79 has r as a zero for 0 g i g n Note that this derivative can be shown to be 135 710171 n7i1z 7cln71n72 n7in7 ckn7kn7k71 n7k7i1z so if we let an nn 71n 7 2 n 7 i 1r then we know that 0 P590 an 7 clanil 7 cganig 7 7 ckan4 which is equivalent to the satisfaction criteria for the LHRR so these expressions do in fact satisfy the LHRR Note that r and nr satisfying this LHRR guarantee that any linear combination a bnr will satisfy it including nn 7 1 allows us to isolate a quadratic component nn 7 1n 7 2 allows isolation of a cubic component and so forth In fact r nr nn 7 1r nn 7 1 n 7 q 7 1 is not the conventional basis for this space of sequences but rather the more easy to write r nr n2r nq 1r Page 4 of 4 October 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 1 Generating functions continued 11 Exponential generating functions and setpartitions At this point we ve come up with good generating function discussions based on 3 of the 4 rows of our twelvefold way Will our integer partition tricks work with exponential generating functions to give us rules for putting distinct balls into indistinct boxes aka set partitions Recall that for the integer partition problem our series of sequential procedures was to rst select the number of boxes with one ball then the number of boxes with 2 balls then the number of boxes with 3 balls etc Would that work in this case Let s try it Question 1 Find an exponential generating function for the number of ways to distribute n balls among unlabeled boxes Answer 1 An exponential generating function for the number of ways to select boxes with 1 ball in is easy there is only one way to ll zero boxes one way to ll one box etc so the generating function would be 71 x2 00 x H a 1 2x 1 Z n 5 n0 Filling boxes with two balls gets harder however there is one way to set up zero boxes with two balls each one way to set up one box three ways to set up two boxes and fteen ways to set up six etc This ends up being ugly pretty fast and doesn t lend itself to computation Howeuer since we already know this statistic these are the Bell numbers we shouldn t have to go home empty handed we can actually work out what the generating function is Recall that 7 7 kii 4n B 25mm ZEZH k1 k1 i0 So the generating function we seek is the heinous expression 00 n 00 k 71k7ik4n 7 i Z n ZBnm ZZZ W 95 n0 n0 k1 i0 This is actually pretty easy We can nd the generating function for Sn k from the known generating function for len k 0 1 E kxsm mi em 7 1k n1 n0 00 n x k x e 71 2501 mm 7k n0 and since Bn 220 Snk and we can include the zero terms when k gt n to get Bn Page 1 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory 1 220 Sn7 k then 00 51 i 1k 7 5L1 T 7 5 k0 As far as Iknow there is no from rstprinciplesquot argument to deriue this same elegant and simple form 12 Proving binomial identities With generating functions We can prove binomial identities with generating functions7 if we know the GFs of the various binomial expressions For instance7 here s one from the last problem set Question 2 Prove that n27 Answer 2 If we can show that the generating functions 2200 m and 220 n2nilm are equal then we re done since two GFs are equivalent if and only if they re equal in all coe icients 00 n 00 00 name n0 i0 i0 n0 Z Z n7i i 00 00 4 n i E iml lt gtn i0 n7i Z 00 i1 1 m E i lt1 7 z i0 There is a fairly straightforward simpli cation of 20 inl Note that since 20 yi di ereintiating both sides with respect to y giues Zioiyiil mill2 so 22Oiyi1 132 Thus 2 00 n 4 n n 71 3 17 17235 n0 i0 1 Page 2 of 9 September 247 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Now let s look at 220 n2nilm l a 13 Other strange and wonderful generating function variants We ve been producing generating functions for individual values of k as n varies ln ways this seems a bit arti cial surely a two parameter enumeration statistic should have a single generating function which differentiates along both parameters We can do that by using another variable along with m eg a variable y whose exponent indicates the number of boxes used Question 3 How could we produce a function such that the coe icient of xnyr represents the number of ways to distribute n identical balls among r distinct boxes with no more than one ball per box Answer 3 We of course know pre emptiuely that the answer is ZTgtO Zngt0 xnyr ZOO x Dry But how could we deriue this from some sort of assembly proceduref2 Consider a procedure for lling a single box this procedure uses one box and one ball in one way and one box and no balls in one way so its generating function is 1m0y11x1y1 yzy We may use anywhere from zero to an arbitrarily high number of boxes so we add together the results of performing this rpocedure any number of times ie39 yy0 yy1 yy2 w 1 i y 3024 By and large we do not actually use multivariable generating functions7 although in algebraic combinatorics they are used to record the number of permutations or partitions with very speci c characteristics 2 Recurrence relations We might ask a number of not obviously related questions 0 How many ways are there to cover a 1 x n checkerboard with dominoes and with checkers Page 3 of 9 September 247 2009 MATH 681 Notes Combinatorics and Graph Theory 1 o How many bitstrings of length n 7 1 do not have 00 as a substring o How many permutations 7139 of the numbers 1 2 n have all 7 1 We might notice idly that these three situations are equinumerous If we experiment a bit more we nd that for successive values of n we get a familiar looking sequence 11235813 This is the Fibonacci sequence which we ve surely encountered before The Fibonacci sequence is the simplest interesting example we have of a recurrence relation it is given by the recursive formula F7 Fn Fn1 We can exhibit why this formula models the counts above Now as to solving recurrence relations the Fibonacci sequence is of an unusual type where Fn is a linear combination of prior E De nition 1 A sequence an is given by a linear homogeneous recurrence relation of order k if an Clan71 6272 63an73 Chan7k fOr all 71 Z k 21 Linear homogeneous recurrences solved with linear algebra The solution method for linear homogeneous equations falls out of three useful propositions two of which we present immediately and solve easily Proposition 1 If an and bn are giuen by the same LHRR then so is the linear combination qan rbn In other words linear combinations of an LHRR s solutions are themselues solutions Proof Given the LHRR an clan1 czar egan3 1 ckan4 satis ed by the sequences an and bn it follows that an Clan71 6272 63an73 39 39 39 Chan7k fOr 71 Z k and bn Clbn71 62bn72 63bn73 Ckbn7k fOr 71 Z k Multiplying the rst equation by q on both sides and the second by r and adding the results qan Tbn qclan71 qCZan72 qckan7h Tclbn71 TCan72 TCkbn7k fOr 71 Z k 61qan71 Tbn71 62qan72 Tbn72 Ckqan7k Tbn7k fOr n 2 k so that qan rbn satis es the aforementioned LHRR D Proposition 2 A sequence is uniquely determined by an LHRR of order k and the initial ualues a07a17a27 7ak7139 Proof Consider two sequences an and bn which both satisfy the LHRR an c1 an1 czar Cganig ckank Clearly if a0 7 be or a1 7 1 or so forth up to ak1 7 bk1 then the sequences differing in at least one element are de nitionally distinct In contrast if a0 0 a1 b1 and so forth up to ak1 bk1 then there is a simpler inductive argument that the two sequences are equivalent We shall inductively show that an bn for all n The base cases n O k 7 1 are all part of our original presumed equalities Then for the Page 4 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory 1 unductive step in proving that an I we may assume that ai bi for i lt n and in particular we can assert equality between the linear combinations as such Clanil 62an72 CSanii Ckanik Clbnil 62bn72 CSbnii Ckbnik and thus since the LHRR gives the left and right sides of this equation to be an and bn respectively it follows that an 1 El These two propositions shed a great deal of light on the nature of a LHRR s solution set the rst proposition tells us that it is a vector space since it is closed under lienar combinations and the second proposition although it is not immediately obvious at present actually tells us the dimensions of the vector space Theorem 1 For a giuen LHRR of order k there are sequences e2 eh e271 such that any sequence an satisfying the LHRR may be expressed as a linear combination of the sequences 61 Proof Let 59 be the sequence known to be unique from the proposition above satisfying the LHRR with e8 1 and e eg e271 0 Likewise let ei be given by the initial conditions el 1 and e5 e eiil O and so forth such that each e2 is given by eZ 1 ande0for0 j ki1andj7 i Now given a sequence an satisfying the LHRR let us construct a sequence bn according to the rule bn egao e1La1 1 efflakA Since bn is a linear combination of sequences satisfying the LHRR it satis es the LHRR And furthermore we can note he egao elm 5341 1ao 0a1 01 a0 b1 69 elai elfilakii 0 1a1 01 a1 bkil egilao elclai 5lak71 0a0 0a1 1ak1 bkil So since an and bn both satisfy the same k order LHRR and have equal terms for the rst k elements they are equivalent Thus an is expressible as a linear combination of the ell sequences D The above argument further shows that any nontrivial lienar combination of the ell sequences is nonzero which in linear algebraic terms means that the sequences ell are linearly independent Since they form both an independent set and a spanning set for the set of solutions to the LHRR we can assert that the above mentioned set of sequences is not only a spanning set for the space of LHRR satisfying sequences but is in fact a basis for this space so the space has dimension Furthermore linear algebraic knowledge about vector spaces tells us that once we know the dimension k of a space any set of k linearly independent vectors will be a basis of the space Thus we have a new goal to nd closed form expressions for k linearly independent sequences satisfying a LHRR of order k We have a proposition which will aid us immeasurably in this task Page 5 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Proposition 3 For a nonzero number 7 an r is a solution to the LHRR an clanil 62an7263an73 ckan7k i r is a root of the polynomial called the characteristic polynomial m 7c1xk 17c2m 7C3mk 77ckm Proof Suppose an r We shall show equivalency between an satisfying the LHRR an clan102ang03an3 ckan4 and r satisfying rk7clrk 1 702rk 27 rk 7 7ckr 0 This is actually extremely simple algebraic manipulation Supposing an satis es the LHRR an Clan71 62an72 CSan73 Ckan7k r clrnil CZTnTZ CngTS ckrnik Tn7krk Clrn7krk71 62Tn7krk72 63Tn7krk73 Ckrn7l TO k Clrk71 Czrkizcgrkismcwo pk 7 clrkil 7 CZTkTZ 7 cger3 7 7 ckro 0 The converse follows by performing the same process in reverse D In the case where the characteristic polynomial has k distinct roots this is sufficient to completely determine the space of sequences satisfying the recurrence relation and then Via algebra on the initial condition nd a closed form for a particular sequence We can see how this procedure would work using the Fibonacci nubmers as an example Question 4 What is a closed form for the sequence giuen by F0 1 F1 1 and Fn Fnil Fnig Answer 4 We shall start by nding two linearly independent solutions to the second order LHRR an an1 aTkg It has solutions of the form an r when r is a root of the characteristic polynomial m2 7 m 7 1 We know this polynomial has roots li so that the aboue LHRR has 2 2 TL 7L and an These are linearly independent so this easy to nd solutions an lt set of 2 linearly independent solutions to the linear homogeneous recurrence relation is a basis to the solution space so that Fn is a linear combination of them Thus there are some k and t such that n n 17 5 1 5 Fnk7 7 We may determine k and l by ensuring the linear combination yields the correct initial conditions 0 0 1F0klt1 T ggt llt1T 5gt kl 1 1 1F1lt17T 5gt 127 lt17T 5gtklt172 5gt5 This system of equations can be solued comparatiuely easily arithmetically messily to giue k 5365 and l Lia5 so the closed form for Fibonacci numbers is 57 17 5 5 1 5 Fn7lt7gt 7w Page 6 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory 1 The same line of arguments will work on any linear homogeneous recurrence relation as long as its characteristic polynomial has distinct roots 22 Linear homogeneous recurrences solved with ordinary generating functions We can justify the same result if we like by building an ordinary generating function for the Fibonacci numbers Suppose fz 2200 an Then what can we say about fm and can it give us a closed form for coefficients in its power series representation We may begin by noting that F7 Fn Fn for all n 2 0 Since this equality holds for all n 2 0 it can be phrased as an equality of power series 00 00 ZFn2mn ZltFn1 Fnn n0 n0 And we can now manipulate these algebraically until we get several copies of fm CO CO ZFn2mn ZltFn1 Fnn n0 n0 CO CO 00 m2 2 Fn2xn m2 2 Fn1xn m2 2 Fnzn n0 n0 n0 CO CO 00 Z Fn2zn2 m 2 Fn1xn1 m2 2 Fnzn n0 n0 n0 CO CO 00 Z Fnzn m 2 Fnzn m2 2 Fnzn n2 n1 n0 00 00 00 Zan 7 Flz 7 F0 m Fnzn 7 zFO m2 Zan n0 n0 n0 7 Flz 7 F0 7 zFO 17m7z2fx Flz F0 7xF0 7F1xFo7mFoi 1 mi 17x7m2 T17z7x2 A digression we could have gotten this same generating function using traditional generating function production methods on one of the combinatorial objects enumerated by the Fibonacci numbers Question 5 Determine a generating function for the number of ways to couer a 1Xn checkerboard with dominoes and checkers Answer 5 We could lay down zero objects which would su ice to couer zero squares in one way this possibility will contribute 1m0 1 towards the generating function If we lay down a single object that object could be a checker couering a single square in one way or a domino couering two squares in one way Thus the prospect of laying down a single object can be represented as 1m1 1m2 71 2 If we lay down two objects we can enumerate the possible results of doing so by multiplying the generating function for a single placement by itself that is x 22 Likewise Page 7 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory 1 if we place i objects we can represent the generating function representing the number of ways to couer squares with this as x xzy Since we could plausible place any nubmer of objects our generating function results from adding together all these cases 1 122223 m which is notably equiualent to our aboue generating function for the Fibonacci numbers If we were to apply our ordinary generating function producing methodology as above to an arbi trary LHRR the same procedure would work albeit with some messy generalities So if we let fz 2200 anz with an satisfying an LHRR of order k then 00 00 Z ankn ZltClank71 52ank72 Ckann 0 n0 00 00 00 00 k n 7 k n k n k n m ankm 7 clm ank1m cgm ank2m ckm anz n0 n0 n0 n0 00 00 00 00 Z ankmnk clm Z an wlml kil c2m2 Z ankgmnk 2 Ckmk Z and 0 n0 00 00 00 00 Z and clm Z and 622 2 and ckmk Z and nk nk71 nk72 n0 co k71 co k72 00 k7 00 E and 7 and clm E and 7 clm E and cgmz E and 7 cgmz E and ckmk E and n0 n0 n0 n0 n0 n0 n0 k71 k72 k7 7 Z and clzfx 7 clm Z and c2x2fm 7 c2m2 Z and 0 n0 n0 1671 1672 1673 k 7 n 2 n k71 17c1m77ckz anz 7c1m an7c2m anz 77ck1m a0 n0 n0 n0 1671 1672 1673 7 Zn and 7 clm Zn an 7 622 Zn and 7 7 ck1zk lag Jew 17c1x7c2m277ckxk Note that the numerator of the above expression consists of several nite sums built from the values a0 ak1 which is to say the initial conditions The denominator of the function is not quite the characteristic polynomial but it is in fact a polynomial equivalent to the generating polynomial with coefficients in opposite order the roots of this polynomial are the reciprocals of the roots of the characteristic polynomial The takehome lesson here is that the generating function of a linear homogeneous recurrence relation of order k will always be a rational function whose denominator has degree k And of course we have a way to evaluate individual coefficients in a rational generating function by making use of partial fractions and we can do so to rediscover the closed form for the Fibonacci Page 8 of 9 September 24 2009 MATH 681 Notes Combinatorics and Graph Theory I numbers 1 5 7 5 1 7 m 7 2 127 57 5 757 5 10 7 10 fly5m 1 ilg m 1 57 5 5 10 10 17 1 5 1 2 m 1 2 from which the coef cients can be grabbed 7 and they agree with our result from the previous section Page 9 of 9 September 247 2009 MATH 681 Notes Combinatorics and Graph Theory 1 1 Equivalence classes of symmetries This de nition is probably familiar but it s useful for discussing classi cation under symmetry De nition 1 A set R of ordered pairs from S x S is called a relation on S two elements a and b are said to be related under R written aRb if a b E R A relation R is said to be reflexiue if for all a E S aRa R is symmetric if for all ab E S if aRb then bRa R is transitiue if for all a b c in S such that aRb and bRc it follows that aRc A relation which is re exive symmetric and transitive is known as an equivalence relation This lends itself to our previous investigation of symmetry as such Proposition 1 For S a set of n element objects and G a permutation group consisting ofpermu tations of length n there is a natural relation RC induced by letting a 7ra 6 RC for all a E S and 7139 E G Then RC is an equivalence relation on S Proof Since G is a permutation group the identity element e E G By the de nition of RC it is true that for all a E S aRGea or since ea a aRGa Thus RC is re exive Now consider a and b from S such that aRGb By the de nition of Ra this is true because there is a permutation 7r 6 G such that b 7ra By the de nition of a symmetry group 7r 1 is also in G and since it is the inverse of7r it follows that a 7r 1b Since 7r 1 6 G and b E S bRGIr lb or in other words bRGa Thus RC is symmetric Lastly consider a b and c in S such that aRGb and bRGc By the de nition of RC there is 7139 E G such that b 7ra and a E G such that c 01 Thus c o7ra aira By closure of the permutation group 77139 E G and since a E S it follows that aRG07ra or in other words aRGc Thus RC is transitive D This is very useful for our investigation of symmetry because if G represents some collection of symmetries then aRGb if and only if a and I represent different orientations of the same object We thus want to collect elements of S into subsets based on their equivalencies In fact doing so is an established way of identifying an equivalence relation Proposition 2 The equiualence relations on S are in a one to one correspondence with the set partitions of S Proof A set partition of S necessariily induces an equivalence relation let aRb iff a and b are in the same partition it is fairly easy to show that this relation de nition satis es the equivalence conditions Conversely if we have an equivalence relation R we may de ne a set partition by letting a and b be in the same partition if and only if aRb The equivalence conditions guarantee that this is a well de ned procedure we would only run into inconsistencies if a were required not to be in the same partition as itself forbidden by re exivity or if different established members of a single partition gave different membership status to an element based on their relations forbidden by symmetry and transitivity D Note as a corollary that the number of equivalence relations on a set of size n is the Bell number B since that is the number of set partitions Page 1 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 De nition 2 The set partitions induced by an equivalence relation are known as its equivalence classes The set of equivalence classes of S under the permutation relation R0 are denoted SG ln abstract algebra parlance the set of equivalence relations under RC would be called the orbits of S under the group action of G we shall not use that notation here but it may be of interest to those using this from an abstract algebraic standpoint This framework allows us to see why some of our symmetry reduction methods worked before on several examples we worked previously G and S were such that whenever 7r 7 a 7m 7 0a so that each element a was a member of an equivalence class of size exactly 1G1 so that lSGl This sort of equivalence would still be correct if we overcoun 7 lSl in a certain manner Take for instance our old example problem of a vebead necklace in black and white If we counted only elements of S each equivalence class would contain different numbers of elements the necklace BBBBB would be in a class by itself while BBBBW BBBWB BBWBB BWBBB and WBBBB would be in an equivalence class together However there is an argument to be made that each equivalence class contains 10 images of a class representative eg the class BBBBB might be thoguht to contain the 10 elements 5BBBBB rBBBBB and so forth for every permutation in D5 likewise the 5 element class could be thoguht to contain each element twice for instance BBBBW might be counted both as 5BBBBW and as fr4BBBBW If we were to count in this highly unconventional manner we would nd not 32 but 80 elements of S and then lSllD5l would be 8 as hoped But how do we codify such an unusual overcounting method We shall actually do so via expansion of the product lSGl 11 Burnsidels Lemma SG is the set of equivalence classes of S under permutations in G G is a permutation group We can somewhat trivially represent lSGl 1G1 as the nubmer of pairs of a class A and permutation lSGl 1G1 Z 1 CESGWEG If we arbitrarily choose an element 0 from each equivalence class C then by unique invertability of permutations for any pair C 7139 there is exactly one element y of S such that 7ry zc namely the value y 7r 1mc We may thus write the number 1 in an astonishingly ungainly fashion lSGl lGl Z Z My 7ry MN CESGWEG which if we make use of an indicator function can be made more ungainly too but ripe for sum rearrangement De nition 3 The indicator function 1p where P is a logical proposition is de ned as 1 if P is true 1P i i 0 if P is false Then we may rewrite the above equation as the triple sum lSGllGl Z ZineHfZZ 2 1121 CeSG weGyeS yes weG CeSG Page 2 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Noting that 7ry will never equal mo unless y is in the same equivalence class as C we may see that the innermost sum of our nal formulation here has all zero terms except when C is the equivalence class containing y Armed with this knowledge we may denote the equivalence class conaining y as y and remove one of our sums lSGl lGl Z Z lireFem yeSreG Since y and zltygt are in the same equivalence class for all y there is at least one permutation mapping y to we may arbitrarily choose one and call it 0y so then we can write the above as lSGl lGl Z Z 1wltygtcryltygt yes W60 lSGl 1G1 Z Z 1mltygty G 165 UJIWE yESW EG W EGyES ireG This together with a new de nition will give us a powerful and e icient new counting method De nition 4 The number of inuariants of the permutation 7r ouer S denoted lnv7r is equal to the number of y E S such that 7ry y Then our calculations above give us Lemma 1 Burnside s Lemma For a set S acted upon by the permutation group G 1 lSGl 3 2 mm l l W60 We may see how this works with several examples both old and new Question 1 How many 5 bead necklaces can be made with two colors of beads What about with n colors of beads Answer 1 Let S 1 25 so S consists of 5 tuples of the numbers 1 and 2 The above question asks what lSD5 is We shall use Burnside s Lemma to answer this question considering the 10 elements of D5 in turn By de nition the identity permutation 5 satis es ex X for any 5 tuple X Thus lnve lSl 25 A single rotation maps the rst bead to the second position the second to the third and so forth In order for X to be inuariant under this rotation it must be the case that 1 2 2 3 3 m4 m4 5 and 5 1 In other words all 5 elements of the 5 tuple must be the same We may select one of the two ualues and assign it to all ue elements thus lnvr l12l 21 Page 3 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory I The double triple and quadruple rotations are similar for instance for X to be inuariant under r2 it is necessary that x1 x3 x5 x2 x4 again necessitating the same ualue in all positions of the 5 tuple Thus InVr2 InVr3 InVr4 21 Any reflection of the necklace will have the same features xing a single element swapping its neighbors with each other and swapping the two elements at distance 2 with each other Thus in order for X to be inuariant under for example the reflection f 54321 we would have x1 x5 and x2 x4 so we have 5 choices we choose one ualue for both x1 and x5 one for x2 and x4 and one for x3 There are thus 123 23 inuariants under f and likewise under the other 4 reflections Putting these into Burnside s Lemma we see that 25421523 S D 8 i 5i 0 And if we had n instead of 2 colors we would simply haue a number other than 2 as the base of all our exponents n54n15n3 10 Note that as a completely friuolous corollary we are assured that n5 5n3 4n is diuisible by 10 for all integer n since the aboue quantity must be an integer SDsi We might also for example use this same line of argument on 3 dimensional rotations Question 2 How many distinct ways are there to color a the faces of a cube with n colors if cubes are considered to be equiualent if one can be rotated to giue the other Answer 2 A cube has 6faces so the underlying set S is de ned by 1 2 n6 Now we must nd the inuariants of the 24 permutations in the octahedral chiral symmetry group O in order to determine the number of equiualence classes in 50 As always euery element ofS is inuariant under the identity 5 so InVe 5 n6 The three 90 rotations around the uarious faces of the cube could be denoted rm ry and rz from an inuariant identi cation standpoint these three are identical and we might denote an arbitrary face axis rotation as rf also including the inuerse rotations r3 r3 and r2 A 90 rotation about a pair of faces xes the two faces being used as axes but rotates the lateral faces around so that eahc is mapped to its neighbor Thus in order for a coloring to be inuariant under such a rotation the 4 lateral faces must be the same color Thus an inuariant of rf is de ned by a choice of three colors one for each of the two xed faces and one for the 4 lateral faces collectiuely Thus InVrf Invr us In contrast the 180 rotation about a face to face axis will x the two faces being used as axes and reorient the 4 lateral faces not so that each is cycled with its neighbors but so that each is swapped with the opposite face Thus an inuariant under r is determined by a choice of four colors one for each of the xed faces and one for each of the two pairs of opposite lateral faces so that Invr n4 Mouing on to the edge to edge rotations all of them are identical as pertains to inuariant identi cation so we shall identify them collectiuely as r5 r5 leaues no faces xed and is self inuerse so it simple swaps 5 pairs of faces In order to be inuariant under re a cube must be colored so that each pair of swapped faces in monochromatic thus an inuariant of re is determined by a choice of three colors one for each pair of swapped faces Thus IHVT5 n Page 4 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Finally our vertex to vertex rotations which are again identical as pertains to invariant identi cation can be denoted as rv and rv These rotate the three faces incident on each end of the axis into each other s positions so in order to be invariant under either rv or r2 a cube coloring must color all faces incident on the north pole the same color and all faces incident on the south pole the same color thus an invariant is determined by two color choices and thus lnvrv lnvr n2 Assembling all these facts under Burnside s Lemma noting that rf re and rv are standing in for three six and four di erent axis choices respectively we nd that n6 6n3 3n4 6n3 8n2 7 n6 3n4 12n3 8n2 SO ii 0 24 12 The Cycle Index One notable feature of the above analysis is that what ends up mattering in nding the invariants of a permutation is its number of permutations To that end we produce a quantity called the cycle structure De nition 5 If 7139 can be expressed as a product of disjoint cycles of length k1 k2 k3 k then 7139 is said to have cycle structure Cyc7r 1 me zk T To illustrate cycle structure we may look at for instance the 12 permutations in D6 name We may more succinctly describe D8 based on cycle structure CycD8 Z Cyc7r 613 2x 3z z 4x 2 WED8 which is a comfortable shorthand for saying that D8 consists of one permutation which has 6 xed points 2 permutations which consist of 3 swaps 3 permutations which consist of 2 swaps and 2 xed points 4 permutations which consist of 2 3 cycles and 2 permutations which are 6 cycles There are some easy to observe facts about the cycle structure for individual permutations and for permutation groups Page 5 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Proposition 3 If7r is a permutation of length n then Cyc7r z mimi Proof If 7139 decomposes into cycles 0102 CT then each number in 12 n appears in exactly one Ci Thus 01 02 CH n By the above decomposition we know the cycle structure of 7139 to be z cl m czz ca m CT Thus hangout31 mica mlcll102llcn an CM 95101135102951031 39 mica D And as an easy corollary of this result Proposition 4 For any permutation group G CycG m1 Proof Since 1 1 for all n the previous result shows that for any 7139 Cyc7r m1 Cyc7r ma 1 1 Thus CyCGm1 Z Cy07rm1 1 W W60 W60 E An extension of these concepts gives a concise variant of Burnside s lemma Proposition 5 IfS 1 2 k then lnv7r Cyc7r mik39 Proof Let 7139 have cycle decomposition into 010203 0 We shall show that a vector x is invariant under 7139 if and only if for ij in the same cycle z mi By the de nition of the cycle form ifi and j are in the same cycle of 7139 seerated by a distance of t then 7rl is a permutation mapping i to j However since x is invariant under 7139 7rx x and applying 7139 multiple times will yield 7rlx x and thus since 7rl permutes the ith element to the jth position it must be the case that l 72 Since this holds for all i and j within a single cycle of 7139 it follows that for C i1i2i3 no it must be the case that m1 m2 zip we shall de ne the expression 0 to be equal to this value Then x is uniquely determined by a selection of the r tuple momzcz zc the invariants of 7139 are thus bijectively mapped to the set 1 2 kT so lnv7r k7 However it can also be easily seen that Cyc7r kkkkr mik mik Clmc2 CT proving the statement of this proposition D Using this idea of the variant we get an easy formulation of a particular case of Burnside s lemma in the context of cycle structure Lemma 2 Burnside s lemma for unrestricted colorings For S 1 2 3 M ifG is a group of length n permutations then 096G 7k lSGl W Page 6 of 6 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 1 The InclusionExclusion Principle Our next step in developing the twelvefold way will deal with the surjective functions We ll build these through the use of inclusion exclusion In its most basic form inclusion exclusion is a way of counting the membership of a union of sets For two sets it is easy to cinvince yourself that lA U Bl lAl l lBl 7 lA Bl With a little bit more doing we can show that lAUBUCl lAl l lBl 7 lA Bl 7 lA Cl 7 lB Cl l lA B Cl We add and subtract certain slices of sets until all overcounts and undercounts are eliminated We can use these simple small versions of the inclusion exclusion principle in a simple example Question 1 How many members of 123 105 have nontrivial factors in common with 105 Answer 1 105 3 5 7 so a nubmer shares factors with 105 if and only if it is divisible by 3 5 or 7 Let A B and C be the members of 123 105 divisible by 3 5 and 7 respectively Clearly lAl 35 lBl 21 and lCl 15 Furthermore A O B consists of those numbers divisible by both and 5 ie divisible by 15 Likewise A O C and B O C contain multiples of 21 and 35 respectively so lA Bl 7 lA Cl 5 and lB Cl 3 Finally A O B O C consists only of the nubmer 105 so it has 1 member total Thus lAUBUCl352115777573157 There are 3 simple presentations of the inclusion exclusion principle which you should be able to convince yourself are equivalent lAloAgomoAnllA1llA2llAnl 7lAmA2l7lAmAgl77lAmAnl7lA2 A3l77lAn1 Anl lAl Ag A3llAl Ag A4llA 2 An1 Anl 7llA1 A2 Anl All those ellipses are a bit unhappy so one of the following forms is a bit more explicit if a bit less readable V L lA10A200AnlZ71i 1 Z A i1 lSliS 12n 73965 which can be simpli ed a bit further by choosing a set rst and then worrying about its size lAlLJAgUmUA l Z 41514 Aj S 12n5 73965 This form is also the easiest in which to prove the inclusion exclusion principle Page 1 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 11 Proof of InclusionExclusion Proposition 1 For nite sets 1411427 An lAlUAgUmUAnl 4151 HA 5 12mn5 765 Proof We prove this by induction on n For n 17 it is trivial 11411 2 41314 Aa39 03g1 73965 For our inductive step7 we will take it as given that AlUA2UUA L1 1lsl71 5 12mn615 73965 and thereby nd 1A1 U A2 U U Anl 1A1UUAnl A1UA2UUAn1UAnl 1A1UA2UUAL1lAnl71A1UA2UWUAW1WAnl lAlUA2UUAn71llAnl61A1OATUA2 AnUUAn1 Anl 2 MW 0A we Z 711 014ij 5 12n615 73965 5 12n6157 73965 2 MW 0A wme 2 MW 0A m4 5 12n615 73965 5 12n6157 73965 2 MW DA lAnli 2 MW 1 A 5 12n615 73965 5 12n6157 765Un z 41514 m z w n A 5 12mn615 765 5 12mn61 765Un MW M 2 MW 0A 5 12mn615 765 5 12mnn65 73965 2 MW 0A 5 12mn5 765 12 Applications of InclusionExclusion While nding members of a collection of sets union is a useful context in which to use inclusion exclusion7 it s more commonly used for nding sets of numbers which lack several properties That Page 2 of 7 September 17 2009 MATH 681 Notes Combinatorics and Graph Theory 1 is if we have a set X and we want to remove from it all elements of subsets A1 A2 etc the subtractive principle says that our count will be leilAlUAzUmUAnl Xlt Z Ulsl Aj SQ12n jes This is particularly useful in cases where the sizes of A are all the same and where the sizes of each Ai Ag are all the same etc If an intersection ofj sets has size aj then we can simplify this to n I n 1X1 lt71gt1ai A classic problem along these lines is the so called derangement problem Question 2 A permutation of the set 1 2 n is known as a derangement if every element is in a position not equal to its value that is if for every value ofi the nubmeri does not appear in the ith position How many derangements are there of 1 2 n2 Answer 2 Let X be the set of all permutations of 1 2n we know an enumeration statistic that counts this and can say with con dence that le nl However this is massively overcounting the derangements since not every permutation is a derangement We need to exclude all those permutations with 1 in the rst position 2 in the second position etc We may de ne sets of these undesirables let A consist of all permutations of 1 2 n which place i in the ith position Then the set of derangements will be X 7 A1 U A2 U U An whose size we should be able to nd by inclusion exclusion We can simplify the inclusion exclusion however by making use of the fact that the sets A are in a certain sense symmetrical there is nothing particularly special about a particular numberi or ith position so we would expect all the A to be the same size and likewise all the A Aj to be the same size and so forth This will in fact be the case A consists of those permutations withi in the ith position and free selections for other positions so elements of Ai are determined by permuting the remaining n 7 1 elements and thus n 7 1 regardless of whati is Likewise A O Ag consists of permutations with the positions ofi andj determined so its elements are determined by permutations on n 7 2 elements thus Ai Ajl n 7 2l39 by a similar argumentt he intersection ofi di erent sets consists of permutations withi elements xed in place so they are determined by permutations among the remaining n 7i elements of which there are n 7 Thus in the formulation of the inclusion exclusing principle given above ai n 7 i and we thus have nl n nl le7lA1UA2U UAnl leZ71iltgtn7il nlZ71iWn7il 24 5 i1 i1 i 0 An interesting footnote to the derangement problem is the question of derangement probability what is the probability that a random permutation of length n is a derangement Taking the ratio of derangements to permutations we have a probability of moms 1 i n i Zlt71Y 39 i0 which is equal to the nth partial sum ofthe extremely rapidly converging in nite series 2071 which converges to e l Thus for any moderately large n even n 6 is an excellent approxima tion the probability that a permutation is a derangement is very close to 1 8 Page 3 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 And nally we can bring inclusion exclusion into play in addressing twelvefold path enumeration statistics Question 3 How many 6 element strings of 1s 2s 3s and 4s contain at least one 1 at least one 2 at least one 3 and at least one 4 Answer 3 There are 46 6 element strings in total This will be our set X in the aboue template We wish to exclude any string which lacks 1s we can call the set of such strings A1 likewise let us identify A2 A3 and A4 as containing those strings without 2s 3s and 4s respectiuely Since Aj consists of those strings lacking js each element of the string msut be a number other than j of which there are 5 possibilities regardless of whatj is Thus lAjl 36 for all j Likewise Ai Aj consists of strings lacking bothi and j so there would be only 2 possibilites for each element and lAi Ajl 26 regardless of what distinct ualuesi andj are Likewise lAi Alj Akl 16 and lAl A2 A3 A4l 0 which is unsurprising since there are no strings of 1 2 3 and 4 which have none of 1 2 3 or 4 in them Using the formulation aboue we will nd that a1 36 a2 26 a3 16 and a4 06 Thus 7 lxi A1 UAZUA3UA4l 467 936 3267 lt3gt1G 3306 1560 A string of numbers in which each number has to appear at least once corresponds to one of our twelvefold way boxes Strings have order and we are considering distinct elements of the string as distinguishable so we are considering the rst row the requirement to have every element appear at least once is the third row so we are lling in cell 3 here Generalizing the above argument we can ask the following question formally Question 4 How many ways are there to put k labeled balls in n boxes such that each box contains at least one ballf2 Answer 4 Let X consist of the set of all ways of putting k balls in n boxes so that le nk by known enumeration statistics let A consist of those ways which leaue boxi empty Then the quantity described aboue is lX 7 A1 U A2 U U Let a be de ned as Fig65 AjH for 5 i We shall see that the actual membership of S is irreleuant IfS hasi members then ai consists of the intersection ofi di erent Aj so this number counts those distributions which leauei speci c boxes empty Thus a counts distributions ofk balls among the n 7i boxes which are not predestined to be empty there are n 7 such distributions 4 k so ai n 7 i Using the inclusion exclusion principle it thus follows that lX7A1oA2o uAnM le171iltgtai nk171iltlgt n7ik 71ilt7gt n7ik 139 So rejoice We have a new entry in our table Page 4 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Choosing k el ts from a set of size n Free choice No repeats Each el t at least once Ordered choice distinguished el ts n 1 2071 n 7 Unordered ch01ce distinguished el ts 1 i i i i 1 if n 2 k Ordered ch01ce und1st1ngu1shed el ts 7 7 0 if n lt k i i i i 1 if n 2 k Unordered ch01ce und1st1ngu1shed el ts 7 7 0 if n lt k As a bonus we now have a statement which is combinatorially trivial but arithmetically quite non obvious n For k lt n 271ilt7gtn 7N 0 Z i0 13 TWO freebies cells 7 and 9 the Stirling and Bell numbers It turns out that the division principle will give us cell 9 of the twelvefold way based on cell 3 Cell 3 recall enumerates the number of ways to put numbered balls in numbered boxes so that no box is empty Now since every box has at least one uniquely identi ed ball within any permutation of the boxes results in a different con guration note that this is not true when boxes can be empty since swapping two empty boxes will result in a different permutation Thus the situations enumerated in cell 3 can be organized into groups of nl up to permutation equivalence each of these groups corresponds to a placement of numbered balls into unlabeled boxes which is what cell 9 counts Thus by the division principle the enumeration statistic for cell 9 is SLOPW l n i W Note that this gives us another combinatorially straightforward proof of an arithmetically difficult result It is far from obvious from an artihmentic point of view that 2071i n 7ik should be divisible by nl but since we have found a set enumerated by their quotient it must be an integer The above formula for the contents of cell 9 is regarded as sufficiently fundamental that it is given a name These are known as Stirling numbers of the second kind and denoted as such Skni1iltgtn 7 0k 39 i0 Thus for instance cell 3 is canonically written as nlSk Let us consider the contents of cell 7 now This counts the number of ways of putting k labeled balls into n unlabeled boxes permitting some of the boxes to be empty This is easily determined by breaking down into cases Any number of boxes between 0 and n 7 1 can be empty so that any number of boxes between 1 and n can be used If we consider the case where exactly i boxes are used then we are distributing k balls between i boxes which can be done in Ski ways Adding together the cases corresponding to different values of i we get that cell 7 consists of Sk 1 Sk 2 Skn 21Ski We may now assert a nearly complete list of twelvefold way enumerations Page 5 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Choosing k el ts from a set of size 71 Free choice No repeats Each el t at least once Ordered choice distinguished el ts n 1 kl nlSk n 201711 n 7 Unordered ch01ce distinguished el ts 1 1 if gt k Ordered choice undistinguished el ts ELI Ski 0 f n 2 k Skn 2071l7n 7 1 n 39 i i i i 1 if n 2 k Unordered ch01ce und1st1ngu1shed el ts 7 7 0 if n lt k Note that the Stirling numbers can also be thought of as enumerating the ways that a set of size k can be partitioned into n nonempty subsets For instance 54 2 7 corresponds to the fact that 1 2 3 4 can be partitioned into two sets as 1 2 34 2 134 3 1 2 4 4 123 12 34 13 24 or 14 23 A question sometimes worth asking is how many ways a set of size n can be partitioned regardless of how many parts the partition is into This can easily be answered as ELI Sni This quantity is known as the Bell number denoted B For instance B3 S3 1 S3 2 S33 1 3 1 5 corresponding to the ve ways to partition 123 123 12 3 13 3 123 and 1 2 3 2 Using the Twelvefold Way 21 Partition numbers What about cells 10 and 12 Even though we lack the means at present to come up with a good formula for them it s worth discussing what cells 10 and 12 measure The numbers on the third row are often known as set partitions since as seen above the Stirling numbers can be considered as the number of ways to partition a set Here we are not looking at distinguishable elements so while we are still performing partitions instead of partitioning a set into smaller sets we are partitioning an integer into smaller integers Let us denote by pnk the number of ways of expressing k as an unordered sum of n nonzero numbers This will be our cell 12 statistic For example 1938 5 because there are 5 such partitions 8611521431422332 Using a similar argument to that giving the relationship between cells 7 and 9 we can come up with a formula for cell 10 as well this cell counts the nubmer of partitions of k into 71 parts some of which may be zero There are ways to have i nonzero terms in the partition so ranging over all possible values of i we see that the statistic in cell 10 will be 191k p2k pnk In addition we have an analogue of the Bell numbers to answer the question how many ways can 71 be broken down into a sum of any number of nonzero integers This is denoted pn and is clearly equal to p1n p2n 1 pnn For instance it is easy to see that p5 7 by brute force listing of every partition 54132311221211111111 Page 6 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 22 Slight variations on known distributions We are now equipped to answer a variety of problems using the tools we developed here These are slight variations on established results Question 5 How many ways are there to distribute 25 identical coins among a captain rst mate and 6 pirates if each person receiues at least 2 coins the rst mate gets 3 and the captain 4 Answer 5 We can start with some pre emptiue distribution we must hand out 4 coins to the captain 5 to the mate and 2 to each of the sailors so 19 of our coins are spoken for and we might as well giue them out immediately We are left with 6 coins to be freely distributed among 8 indiuiduals This statistic we know to be 871 Note that this problem would have been a lot harder if we d asked about distinguishable coins There are still many problems that are dif cult Notice that we could phrase the question above another way to wit Question 6 How many non negatiue integer solutions are there to the linear equation x1x2x3x4x5x6x7x8 25 if each x gt 2 and furthermore x1 2 4 and x2 2 3 Answer 6 This is the same question as aboue merely abstracted Another likely question might be probabalistic Question 7 15 balls are randomly distributed among 6 boxes What is the probability that no box is empty Answer 7 Note that we said nothing about box or ball distinguishability but we have a good idea of the process in question drop a ball in a random box drop another ball in a random box etc The standard probability calculation of diuiding the desired set size by the size of the total set of possibilities has an implicit assumpion namely that euery member of the euent space has identical probability We might run into trouble using for instance unlabeled balls or boxes for this for instance putting two balls randomly into four boxes the two possibilities 1100 and 2000 are not equally likely 1100 occurs with probability while 2000 occurs with probability 1 Compare to the labeled balls and boxes paradigm where each of the 16 possible con gurations is equally likely Thus in dealing with a probabalistic question we usually will want a distinct balls into distinct boxes statistic Here we are looking at the probability that a random selection from among 615 possible con gurations is one of the 515 6 con gurations in which euery box has at 6S156 7 302899156560 N 615 r W 064439 least one ball so the probability is Page 7 of 7 September 1 2009 MATH 681 Notes Combinatorics and Graph Theory 1 1 Recurrence relations continued yet again One last lousy class of recurrences we should be able to solve 11 Systems of recurrence relations Sometimes multiple recurrences working in tandem are more effective than a single recurrence Let s see how such a thing might be of assistance Question 1 Let an represent the number of strings from 0 1 2 of length n with an euen number of 0s Find a recurrence for an it would be a lot easier to do it with the exponential generating function Ze memem 53x 5 00 n n n 2 Zn0 3 to get an 3 21 But armed with that knowledge let s look at how we might tackle it as a recurrence Answer 1 Note that recurrences are not actually the best way to solue this particular problem j x 7 We introduce an auxiliary sequence bn which counts the bitstrings of length n with an odd number of zeroes Now we know an 2alnil l bnil bn anil anil and a0 1 and b0 0 This uniquely determines an but soluing it might be tricky We can have recourse to either OGFs or EGFs to solue it depending whether you prefer algebra or di erential equations Let s suppose we use an OGF letting 2200 anx and gx 2200 bnx Then the rst equation in the recurrence can be simpli ed to 7 a0 xgx the second will become gx 7 b0 2xgx Collecting terms we ll get the system xg x 1 W 19235 MWE 17 2x so soluing for in terms of itself 52 1 ih 3 172 172 andthus 2 172 WWWW so 1 align which expanded for coe icients giues 13 n 1095 T95 0 n 00 xquot 00 w n0 an and g Zn0 brim we could interpret the system of recurrence relations as a system of di erential equations fQE 21 990 990 1 2990 If we were to use EGFs with the recurrence then using Z Page 1 of 3 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 n 2 1 n or if we let the uector u be we have the equation 17 1 2 u The general solution to a system 17 A17 will be 17 Z hieAimUi where i and 11739 are the eigenualues and eigenuectors of A In this particular case the matrix has eigenvalues 3 and 1 with respectiue uectors 1 1 and 1 71 so 1 1 h 63m 1 h em 7 3m 1m 7 1 2 he H 1 25 Lil new 7 kgewl so an M3 1 kg and bn M3 7 k2 the initial ualues will let us solue for 1 and k2 Ci Both the OGF and EGF methods will work for any system of two linear simultaneous recurrences with three or more both can work but the EGF method with a linear algebra computer system to calculate eigenvectors is the most effective 12 Catalan numbers Before we depart from recurrences entirely we ll address one last speci c recurrence which is not of a form we ve seen before Recall that in the rst week we noticed that there were 5 ways to build a binary tree with 3 nodes 5 ways to nest 3 pairs of parentheses and 5 ways to arrange 3 up steps and 3 down steps in a way that never drops below the initial point we furthermore saw that all these structures would have identical counts thanks to bijections between the different structures Let us denote the number of ways to put n nodes in a binary tree or nest n pairs of parentheses or climb up n steps and down n without dropping below the starting point as the Catalan number C We just saw that C3 5 fairly easy exhaustive counting can tell us that CO 1 C1 1 and C2 2 We might want to see how to get further Question 2 What is C472 And is there a non brute force way to get itf2 Answer 2 Let us consider the number of ways to arrange 4 nodes in a binary tree One node is the root node and o to the left and right of it are two possibly empty trees with 5 nodes among them There will be 4 simple cases which we can enumerate easily If the left tree is empty 0 nodes all 5 nodes are on the right The left tree can only be arranged one way while the right tree can be arranged in C3 5 ways If the left tree has a single node it can be arranged exactly one way while the right tree has 2 nodes and can thus be arranged in C2 2 ways Finally we have two cases which are the mirror image of the aboue accounting for 2 and 5 ar rangements We thus have Cng C1C2 C2C1 CgCo 14 possible arrangements The above is easily generalized to give a simple recurrence relation de ning C 71 Cn1 Zcicnii Co 1 i0 from which we can compute Catalan numbers fairly easily eg C5 42 C6 132 But this isn t a closed form and since it isn t a standard recurrencerelation form we don t have the means to turn it into one But from this recurrence we can acquire some valuable information Question 3 What is the ordinary generating function Z Cnm co n0 Page 2 of 3 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Answer 3 Note that the right side of the aboue recurrence shows up rather unexpectedly upon multilying a pwoer series by itself 0001022Cgm3Co01022033 0000 0001 010090 0002 0101 0200952 01 0290 03902 or more concisely f 90 i 00 we gt z So 7 1 0 Using the quadratic formula it follows that 1 j 1 7 4x M 3 z Note that is unde ned which is a danger of formal power series but at the uery least we would like Co to be equal to limmao which only happens if 1 7 V2541 This can give a closed form if we re comfortable with the concept of binomials with non integral n Proposition 1 Euen when r is not a positiue integer it is true that 00 r 1 7 71 lt x Z n0 where rr71r7rin1l Proof Let fz 1 my and consider the power series representation fz 220 anm By f 0 2 the construction of the power series a0 f0 a1 f 0 a2 and so forth and in general 0 Using the power rule and chain rule n times 1 dn r 1 rin 71 5lrr1r2rn11 1m elm rr71772rin1 nl El an7 n So if we were to use this expansion of a binomial 7 7 12 ML 2 7 1 2200 IrL2 495 2m 2301 IrL2 4n 2m 7 220 mew 2m 2 74 m 2 71 1gt wmmew Page 3 of 3 October 15 2009 MATH 681 Notes Combinatorics and Graph Theory 1 1 Generating functions continued 11 Generating functions and partitions We can make use of generating functions to answer some questions a bit more restrictive than we ve done so far Question 1 Find a generating function for the number of ways to distribute n balls among 5 boxes if the rst box can contain any number of balls the second box contains an odd number of balls and the third contains a multiple of 5 less than 15 Answer 1 The procedure for lling the rst box is known to be represented by the gf 1xx2 x3 The second howeuer would be xx3x5x7 x1x2x4x6 1722 and the third would be 1 x5 x10 In total we would haue Which is not tremendously amenable to simpli cation but we could actually do it with partial fractions this one was done with computer assistance 3 33 1 777776 52 43 34 2526 7 8 21735 41735 41 zzzzzzz 90 3 271 33 1 The three terms at the beginning of this expansion expand to 220 1 x 7 ix 7 17x 3 33 71 quot So for x gt 8 the coe icient of x is n 1 7 T 7 Note that we could ve phrased this another way Question 2 Find a generating function for the number of nonnegatiue integer solutions to x1 1 2x2 1 5x3 n with 5x3 lt 30 which means we can now produce generating functions 7 if not simple answers 7 to the number of ways to divide any n into linear combinations Here s one such question which has a certain amount of everyday relevance x1 1 5x2 10 1 25x4 1 50x5 100x6 n A nonnegative integer solution to this is equivalent to a way of making change for n cents in standard American change including the half dollar and dollar coin The generating function for this can be worked out to be 1 17 x17 x517 x1017 x2517 x5017 x100 Trying to actually calculate this even with partial fractions is not recommended However using partial sums and computer algebra systems we can nd values for individual entries Question 3 How many ways are there to make change for a dollarf2 Answer 3 From the aboue we can get an approximation su icient for worikng out the rst hundred terms of the sequence 1z2 1001510 10011020 10012550751001501001100 which giues us a 600th degree polynomial 1 x x2 x3 x4 2x5 1 293x100 1 x600 We can thus see that there are 295 ways to make change for a dollar Page 1 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory 1 This all brings us towards integer partitions Above the question was really how to divide n into 1s 5s 10s 25s 50s and 100s If we look at integer partitions we can see that we re really dividing a number up into several value classes eg we recall that p5 7 with the partitions 5 4 1 32 311 21111 221 and 11111 lfwe allow xi to represent the number of is used in a partition we can see that these partitions are in a one to one correspondence with solutions to x1 1 2x2 1 3x3 1 4x4 1 5x5 5 whcih would be the x5 coef cient of the generating funcuon 17x17x217x317x417x539 This gets more troublesome if we wanted a generating function for arbitrary partition numbers but we can at least present a symbolic form if not an actual formula 1 1 oopn 2 1121314W Uli li And speci c formulas good enough for nding speci c coef cients can be produced by using partial products and partial sums Some other neat partition problems Question 4 How many ways are there to express n as a sum of distinct integersf2 Answer 4 This is pleasantly enough an easier question than the unrestricted partition Instead of counting the number of each ualuei that appears with the expression 1xlx21x31 W we instead have each number either appearing once or not at all so the expression to represent this selection is 1 1 xi Thus our total generating function is 00 1 x1 x21 x31 4 H1 xi i1 and the answer to the question aboue is the coe icient of x which does not have a closed form but is amenable to fairly easy symbolic calculation Question 5 How many ways are there to express n as a sum of integers no greater than k Answer 5 Here instead of an in nite number of sub processes we only need k of them so we have for once a generating function which is a nite product 1 lt17 zgtlt1e W17 W17 z4gtlt17 M Now we modify this slightly in a way that will be useful for us in actually returning to our permu tation statistics Question 6 How many ways are there to express n as sum of integers no greater than k one of which is k itself Answer 6 This is as aboue except instead of the kth process being 1 xk ka g we have xk ka 1fk so the total generating function is mk 17 z17 zz17 x317 x417 M Page 2 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory 1 This will actually bring us to the purpose of creating a generating function for the one statistic which we handwaved when building the twelvefold way We could note by observation that the number of ways to partition 71 into nonzero parts of which the largest is k is equal to the number of ways to partition 71 into k nonzero parts as in this example for n 8 and k 3 311111lt gt611 32111lt gt521 3221lt gt431 3311lt gt422 332lt gt332 To exhibit this relationship we have recourse to a visual technique for presenting partitions De nition 1 The Ferrers diagram for the partition a1 a2 a3 ak for a1 2 a2 2 a3 2 2 ak gt 0 consists of k left justi ed rows of equally spaced dots with a dots in the ith row for each i For instance here we have a Ferrers diagram for 3 2 2 1 An alternative to the Ferrers diagram is a gure drawn with boxes instead of dots Such a gure is called a Young diagram and can be conventionally drawn in one of two styles with the largest row on top in what is known as the English style shown below on the left or on bottom which is French style shown below on the right Any of these visualizations will work equally well There are several useful geometrically determined properties of Ferrers diagrams listed without proof below the proofs are largely straightforward results of the de nition of the Ferrers diagram Assuming a Ferrers diagram is associated with the partition a1 a2 ak for a1 2 a2 2 a3 2 2 ak gt O we have two particularly useful geometric properties 0 The Ferrers diagram has a height of k ie a total of k rows 0 The diagram has a width of a1 ie a total of a1 columns 0 A Ferrers diagram uniquely determines and is uniquely determined by a partition Thus we may conclude that pkn is the number of Ferrers diagrams with n dots of height k in Question 5 we determined the number of Ferrers diagrams of width k and above we hinted that these might be the same quantity In fact we can nd an explicit bijection Page 3 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory 1 De nition 2 The transpose or conjugate of a Ferrers diagram is a diagram produced by exchanging the rows and columns of the diagram Alternatively the conjugate of a partition a1a2a3 ak with al gag Zak gt0isapartition b1b2b3ba1 wherebi aj The second de nition above is a direct de nition of a partition conjugate without appeal to geo metric intuition Below is an exhibit of conjugation applied to a Ferrers diagram or alternatively to the associated partition 9 0 a o a o 39 39 o o o o o o 3221 431 Note that two successive conjugations return the original Ferrers diagram note also that distinct diagrams have distinct conjugates Since conjugation swaps height and width conjugation illus trates that partitions into k parts and partitions with one part of size k and other parts of size k are in fact equinumerous and since we had a generating function for the latter we can use it for the former giving us a generating function for 19km gpknmn 17 z17 m2 7 31 m4 j j 1 7 mk In addition if we were to conjugate a partition with a maximum entry of k we would get a partition with a maximum length of k this would correspond to a twelvefold way statistic without surjection which we know to be p0n p1n p2n pkn which gives us the not entirely obvious algebraic identity k i 1 m lt17zgtlt17z2gtlt1ez3gtlt17z4gtlt1ezkgt 1lt17zgtlt17z2gtlt17z3gtlt17z4gtlt17zigt 12 Exponential generating functions So far we ve looked at algebraic representations for distribution of indistinct objects and we ve used that to shed a great deal of light on two rows of our twelvefold way Can we do the same for distinct objects Suppose we have two processes for distributing n distinct objects we can think of them as sequences a0 a1 a2 a3 and b0 b1 b2 b3 We might ask what the sequence is for distributing 71 objects using one or the other but not both of these processes this would be a0 0 a1 1 a2 2 There are plenty of algebraic structures where this would be simple addition How about distribution using these processes alternatingly When the objects were indistinguish able recall that this was a0b0a0b1 a1b0a0b2 albl agbo However here we must not Page 4 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory 1 only decide how many objects to deal with using process A and how many using process B but in addition which objects we deal with using each process If we incorporate this information then we have 1 a1 1 1 a2 2a1b1 1 2 a3 3a1b2 3a2b1 1 b3 The way to dispose of n objects will end up being aobn TjalbWA 1 aibni 1 anbo This is actually fairly sensible We can split our n objects up as i dealt with using process A and n 7i using process B in ways then there are ai ways to place the i selected objects with process A and bn 39 ways to place the selected objects with process B But now we ask what useful algebraic object has this property that multiplying two associated with the sequences a0 a1 and b0 b1 gives a product associated with the sequence a0b0a0b1 a1b0a0b2 2a1b1 agbo The answer is a surprising tweak on the generating functions we have seen to date De nition 3 If an enumerates a number of ways to place select or otherwise arrange n distinct objects then fx 220 21 is called the exponential generating function for an Now note that multiplication of two generating functions in fact produces the desired result 00 a 00 b lt nlmgt n0 n0 n M8 aObn a1 bnil anbO n nmtniaimtmtmult H o 348 nl nl nl x Mad 7101 71a1bn71 Wanbo H 71 aObn albnil who 3 0 71 774 So this allows us to construct generating functions from several independent distribution procedures for distinct items As in the case of the ordinary generating function let s start by trying this out with a statistic we already know 3 H o 3 48 n Question 7 Find an exponential generating function to enumerate the ways to place n distinct balls in r boxes so that no box contains more than one ball Answer 7 Let us start by noting that the enumeration statistic for such a placement is known to be n16 and we will judge our procedure a success if it yields tihs expression as coe cients The generating funciton for putting balls in a single box will be 1 ltgt 1 We may either place no balls in it in only one way or place the only labeled ball we have on hand in it in only one way The concatenation of r such procedures can be performed by multiplying this quantity by itself r times so our exponential generating function here would be 1xr If we use the binomial theorem on this we would get that the generating function is 20 howeuer in an exponential generating function we look at coe cients not of x but of it is thus expedient to rewrite this form as 20 We can also nd ways to symbolically express and answer questions which would have been insanely difficult before Page 5 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory 1 Question 8 If we have 5 boxes each of which can contain no more than 5 balls how many ways are there to distribute n labeled balls among themf2 Answer 8 Each box can be lled with either zero balls in one way 1 ball in one way 2 balls in one way or 5 balls in one way thus this procedure has generating function x0 x1 x2 x3 x2 x3 1lt gt1ltigt1ltigt1lt gt 1 And concatenation of the three procedures giues x2 x3 3 9 9 13 7 17 5 1 1 1 ii137273i475i6i7i879 lt26gt 2244242424216 x2 x3 x4 x5 x6 x7 x8 x9 1 3x 9 27 78E 1 2105 1 510a 1050 1680 1680 The coe icients on for n from 0 to 9 giues the number of ways to distribute n distinct balls or n gt 9 of course such a distribution is impossible so there are zero ways to do so Of course the real fun comes when our functions are series instead of polynomials As is often the case we ll start with a question to which we already know the answer Question 9 Find an exponential generating function to enumerate the ways to place n distinct balls in r boxes if each box can contain any number of balls Answer 9 As before we know this enumeration statistic and it is r so we have a reasonable expectation of getting that expression appearing in the coe icients of the generating function The procedure for lling one box is as we saw in the previous examples the sum of monomials indicating that we can puti labeled balls in the box in exactly one way that is So adding up all such monomials we get that the exponential generating function associated with putting balls into a single box is x2 x3 x4 x5 1ig g which is a series we can describe succinctly with a function 7 this is the well known Taylor series for em so the exponential generating function for the procedure of putting n distinct balls in a single box freely is e Since we have r boxes to ll the generating function for lling all x of them is the product ofr copies of this generating function that is em e Re expressing this as a series we see that the generating function for this entire procedure is 00 n 00 n xx x 671 Tn 2 nl 2 nl n0 n0 which meets our expectations We ve lled in two cells of row 1 of the twelvefold way Let s try to do the third 7 which we originally needed inclusion exclusion to handle Question 10 Find an exponential generating function to enumerate the ways to place n distinct balls in r boxes if each box must contain at least one ball Answer 10 The procedure for lling one box is the sum of the same terms as were used in the previous example but we now forbid the possibility of leauing the box empty so our exponential generating function associated with putting balls into a single box will be 2 3 4 5 x x x x w i i i i 7 1 x2645 e Page 6 of 7 September 8 2009 MATH 681 Notes Combinatorics and Graph Theory I so the exponential generating function for the process of processing x boxes in this way is ex 7 1V Howeuer if we want to get this exponential generating function into a state where indiuidual coe cients can be calculated we ll need to expand this a bit further em 1 i WHW i0 Page 7 of 7 September 87 2009