### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Combinatorics MATH 180

UCLA

GPA 3.55

### View Full Document

## 11

## 0

## Popular in Course

## Popular in Mathematics (M)

This 90 page Class Notes was uploaded by Kaylin Wehner on Friday September 4, 2015. The Class Notes belongs to MATH 180 at University of California - Los Angeles taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/177808/math-180-university-of-california-los-angeles in Mathematics (M) at University of California - Los Angeles.

## Similar to MATH 180 at UCLA

## Reviews for Combinatorics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/04/15

Lecture 1 7 March 30 We start our investigation into combinatorics by fo cusing on enumerative combinatoricsi This topic deals with the problem of answering how many77 We will start with a set S which is a collection of objects called elements and then we will determine the number of elements in our set denoted More information about the basics of set theory are found in the ap pendix of Applied Combinatoricsi We start with a few basic rules for counting Addition Rule 1f the set we are counting can be broken into disjoint pieces then the size of the set it the sum of the size of the pieces SUS Si Sj ifi9 j a SZSl i1 i1 Example A square with side length 4 is divided into 16 equal sqaures as shown below What is the total number of squares in the picture Solution We break the squares up according to size There are sixteen 1 X 1 squares nine 2 X w squares four 3 X 3 squares and one 4 X 4 square So by the addition rule there is a total of 16 9 4 1 30 squares Note here we must be careful about what is meant by disjoint Geometrically as squares the squares are not all disjoint one from another but we are not concerned with the geometry of the problem so when we talk about disjoint we mean not the same square So in our case when we broke up the squares into these sets by size theses sets are disjoint one from another Multiplication Rule Suppose we can describe the elements in our set us ing a procedure with m steps where at the ith step we have Ti choices available Where the number of choices is independent of our previous choices Then the size of the set is 7 17 2 quotrm It is important to realize that what we are counting using the multiplication rule is the number of choices that can be made In order to guarantee that we get the right count it is important that 1 every element in our set is realizable by at least one set of choices and 2 no two sets of choices gives us the same element An example of what can go wrong will be given in a later lecture Another important thing to note is that the number of choices is independent on the previous choices but not necessarily the choice that we have to make This is illustrated in the next example Example How many standard California license plates are possible A standard license plate has the form NLLLNNN where N is a number and L is a letter How many are possible if there is no repetition of numbers or letters Solution We can form the license plate one character at a time So we will use the multiplication rule where the decision at the ith stage is what character goes in the ith slot Since there are 10 possible numbers and 26 possible letters we have that the number of license plates is 10262626101010 175 760 000 When we add the restriction that that there is no rep etition of characters we again use the same principle as before Now the difference is that when we ll in the second number we only have nine options since we have already used one number when we ll in the third we only have eight options and when we ll in the fourth we only have seven Note that here we do not know which nine eight or seven choices are avail able because that depends on previous choices but the number of choices does not So the number when there is no repetition of numbers is 10262524987 78 624 000i Bijection Rule 1f the elements in S can be paired in a onetoone iiei bijective fashion then lSl We have already used the bijection rule when we did the multiplication rule since what we are doing is counting the number of choices which are paired onetoone with the elements One interesting thing is that it is possible to show that two sets have equal size by giving a bijection between the sets without ever knowing the size of the sets themselves Example How many subsets of 1 2 i i i n are there Solution We can pair a subset of with a binary word of length n a binary word is a word with the individual letters coming from 0 and 1 The way this is done is by taking a subset A and letting the ith letter of the binary word be 1 ifi is in A and 0 ifi is not in A For example for 1 2 3 we have 0 H 000 3 H 001 1lt gt100 139101 9010 239011 129110 1239111 Since there are 2 binary words it follows by the bi jection rule that the number of subsets is also 27 Rule of Counting in Two Ways If we count 5 in two different ways the results must be equali This is the basic idea behind many combinatorial proofs Namely we nd an appropriate set and count it in two different ways By then setting them equal we get some nontrivial relationshipsi Example Count the number of 957s in the diagram which has n rows and n 7 1 columns below we show the case n 4 in two different ways 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 Solution For our rst method we count along rowsi Each row has n 7 1 of the 957s and there are n rows so in total we have nn 7 1 total 957s For our second method we count using the diagonalsi In particular we have that there are n 123nn321ZZL i1 Equating these two ways of counting we have nn12i or i1 i1 Probability is counting Probability is a measurement of how likely an outcome is to occur If we are dealing with nitely many possible outcomes and each outcome is equally likely very common assumptionsl then the probability that a certain outcome occurs is the ratio of the outcomes with the desired result divided by the number of all possible outcomes Lecture 2 7 April 1 Example A domino is a tile of size 1 X 2 divided into two squaresi On each square are pips or dots7 the number of pips possible are0717 27 37 47 57 6 There are 28 possible domino pieces7 iiei7 7 7 7 7 i7 7 Two domino pieces t if we can arrange them so the two adjacent squares have the same number of pipsi So for example t do not t What 1s the probability that two dominos chosen at random will t Solution First let us count the total number of ways to pick two dominosi We can think of choos ing one domino and then a second one This can be done in 2827 756 ways But we have overcounted7 this is because the order that we pick domino pieces should not matter So for example right now we dis tinguish between the choice a and the 7 In essence we have counted ev ery pair twicei To correct for this we divide by 2 so that the number of ways to pick two domino pieces is 7562 378 Next let us count the number of pairs for which the dominos t We again think of picking a domino and then seeing how many domino pieces t with it There are two cases7 if we rst pick a domino of the form of which there are seven of this form then dom1nos which t with it are of the form y f 17 so there are six matchesi So in t 1 got 67 42 pairs In the second case we have a domino of the form where I y7 there are 21 such dominos and there are twelve dominos that can t with this type of domino7 namely7 for for 2 f y So in this case we got 2112 252 pa1rsi Combining we have 42 7 252 294 pairs that match7 but as before we have counted every pair twice and so there are 147 pairs of dominos that t Combining we have that the probability that two dominos chosen at random will t is 147378 7181 Given a set with n objects7 a permutation is an ordered arrangement of all n of the objects An 7 permutation is an ordered arrangement of 7 of the n objects An T combination is an unordered selection of 7 of the n objects We now count how many of each type of the fol lowing there are First off for a permutation by the multiplication rule we choose which object will be rst we have n choices7 then we choose which object will be second we now have n 7 1 choices7 and continue so on to the end So there are nn 71n 7 2 321 nl permutationsi The notation n17 read n factorial777 arises frequently in combinatorics and it is important to get a good handle on using it For example7 it is useful to be able to rewrite factorials7 iiei7 2n2l 2n22n12nli For convenience we will de ne 01 1 this helps to simplify a lot of notation Another useful fact for factorials is Stirling s approx imation which states that n n nlm 27rnlt7gt e This is useful when trying to get a handle on the size of an expression that involves factoriali For instance7 one object which has been extensively studied are the middle binomial coef cients see below which by Sterling7s approximation we have x47rn2n2n 1 7 2n 7 2n N n nlnl 27Tnnx27Tnn x7T7 L The method to count Tpermutations is the same as that of counting permutations We use the multipli cation principle but instead of going through it stages we stop at the Tth stage So we have that there are nltn71n72n7pi nn71n72n7T71nTH21 n7T 21 nl P n 7 This is also sometimes written as the falling factorial nk or n7 To count Tcombinations we can count Tpermu tations in a different way Suppose that we let Cn T be the number of ways to pick T unordered objects then we have Pn T Cn TTli Namely to have an ordering of T elements we rst pick the T elements and then we order them Rearranging we have Cm Pl 7 7 Tl 7 Tln7Tl T The term read n choose T is also known as a binomial coef cient This will be discussed in a future lecture Example How many ways can it rooks be placed on n X n chessboard so no two threaten each other How many ways can It rooks be placed on n X n chessboard if k S n Solution A rook can move along any row and col umn If there are n rooks and at most one rook can go in a column then there will be a single rook in each column We place rooks one column at a time In the rst column we have n choices in the second column we cannot put it in the same row as we used for the rst rook so there are n 7 1 choices for the third col umn we have n 7 2 choices and so on In total there are nn 71n 7 221 nl placements If we have It rooks then the approach is similar First we choose the columns that the rooks will go into This can be done in Cn 16 ways Once we have the columns we place rooks in one column at a time In particular the way that we can distribute the rooks in the k columns is nn71n7k71 Pnki Putting it together the number of ways to place the k rooks is Cn kPn k Problems of placing rooks on chessboards can lead to some interesting and highly nontrivial combina toricsl These types of problems can arise in algebraic combinatorics which unfortunately we will not have time to address this quarter Example Given eight points which line in the plane no three on a line how many lines do these points determine Solution To determine a line we need two points So this reduces to the number of ways to pick two of the eight patterns which can be done in ways Note that it is important that no three are on a line to guarantee that we do not overcountl Lecture 3 7 April 3 Example How many ways are there to choose k el ements from 121Hn so that no two are consecutive Solution If we did not have the restriction that el ements couldn7t be consecutive then we could do this in ways The problem is on how to guarantee that the elements are not consecutive Suppose that our elements we choose are a1lta2lta3ltltak where no two are consecutive Using the fact that no two are consecutive we have that a1lta271lta372ltltak7k71i These are k ditinct elements from n 7 k 7 1 121Hn 7 k 7 On the other hand given It distinct elements 121 lt 122 lt lt bk from n 7 k 7 1 we can nd It elements from for which no two are consecutive namely the elements b1ltb21ltb32ltltbkk71i So the number of ways there are to choose k elements from 121 1 i n so that no two are consecutive is the same as the number of ways there are to choose k elements from n 7 k 7 1 which is SI171 When using the multiplication principle it is impor tant to make sure that different sets of choices do not lead to the same outcome This can sometimes be subtle to detect so great care should be taken Example From among seven boys and four girls how many ways are there to choose a six member volleyball team with at least two girls Solution One seemingly natural approach is to rst pick two girls and then pick the remainder of the teami This way we guarantee that we meet the condition The number of ways to pick the two girls is 9 there are now nine people left and we have to choose 4 of then and this could be done in 3 ways for a grand total of Z 756 different possible teamsi But wait Suppose the girls are AB CD and the boys l234567 then we could have rst chosen AB and then C246 to form the team ABC246 but we could also have rst chosen BC and then A246 to form the team ABCV246 So different choices gave us the same teami We have committed the cardinal sin of overcountingi To correct this we have two options one is to gure out how much we have overcounted and then subtract off the overcounti The other is to go back and count in a different way one such different method is to split up the count into smaller cases where we won7t overcounti For example in this problem let us break it up by the number of girls on the teami If there are two girls we pick two girls and four boys to form the team which can be done in I if there are three girls we pick three girls and three boys to form the team which can be done in 3 if there are four girls we pick four girls and two boys to form the team which can be done in i ways so altogether there are 371 teams An arrangement of n distinct objects is nli But what happens if the objects are not distinct For example suppose we are looking at anagrams rearrangements of letters of a word For instance STEVE BUTLER can be arranged to RUE VEST BELT but it could also be arranged to gibberish VTSBEEERTLUW So the number of ways there are to rearrange the letters of a given word allowing for gibberish answers is found by counting the arrangements of objects with repeti tioni Example How many ways are there to rearrange the letters of the word BANANA Solution We present two methods The rst method is to group the letters together by type We have one B three As and two Nsi We now start with six empty slots which we will ll in with our letters in order First we put in the B there are six slots and we must choose one of them so this can be done in ways We now have ve slots left for us to choose for the position of the three As which can be done in waysi Finally we have two slots left for us to choose for the position of the two Ns which can be done in waysi Giving us a total of 6 5 2 lt1 lt3 lt2 7 60 rearrangementsi For our second method we rst make the letters dis tinct This is done by labeling so we have the letters B A1 A2 A3 N1 N2 These letters can be arranged in 6 ways and nally we remove the labalingi The prob lem is that we have now overcountedi For instance for the end result of ABANNA this would show up twelve ways as AlBAQNlNQAg AlBAgNlNQAQ AQBAlNlNQAg AQBAgNlNQAl AgBAlNlNQAQ AgBAQNlNQAl AlBAQNQNlAg AlBAgNQNlAQ AQBAlNQNlAg AQBAgNQNlAl AgBAlNQNlAQ AgBAQNQNlAl Namely we have 3 ways to label the As and 2 ways to label the Ns and ll ways to label the B This happens with each arrangement so in total we have 6V m 60 rearrangementsi These two approaches generalize The rst idea is to choose the slots for the rst type of objects then choose the slots for the second type of objects and so on The second idea is to label the elements and permute and then divide out by the overcountingi Given n1 objects of type 1 n2 objects of type 2 Hi nk objects of type k and n n1n2 nk then the number of ways to arrange these objects is n ninl ninlingininka n1 n2 nk nl lt n gt nllngl nkl n1n2uink The term m n M is also known as a multinomial coefficient we will discuss these more in a later lecturer Example How many ways are there to rearrange the letters of ROKOKO so there in no 000 Solution The number of ways to rearrange the letters of ROKOKO is the same as the number of ways to rearrange the letters of BANANA so there are 60 in a i But of course some of these have 000 but we can use one of the most useful techniques in counting Sometimes it is easier to count the complement S we now count the number of arrangements with 000771 This can be done by considering the arrange ments of the letters RKKOOOi This can be done in 4121 12 ways So the total number of rearrange ments without 000 is 60 7 12 48 A related problem is to distribute it identical objects among k different boxes or people or days or so on One way to do this is to use 7s stars to denote the identical objects and lay them down in a rowi We then draw in k 7 1 dividing lines bars which divides the n objects into k groups the rst group goes in the rst box the second group goes in the second box and so on For example suppose we are distributing n 20 pennies among k 6 children Then using bars and stars we represent giving four pennies to the rst child two to the second six to the third none to the fourth ve to the fth and three to the sixth by In this case we have a total of 25 bars and stars and once we know where the bars or stars go then we know where the stars or bars go So the number of ways to do the distribution is the number of ways to pick the bars or stars which is The number of ways to distribute it identical objects into k distinguished boxes is n k 7 1 7 n k 7 1 k 7 1 7 n Example How many ways are there to distribute twenty pennies among six children What if each child must get at least one penny Solution We already have answered the rst part this can be done in 53130 ways For the sec ond part we distribute pennies in two rounds 1n the rst round we give one penny to each child thus sat isfying the condition that each child gets a penny 1n the second round we distribute the remaining fourteen pennies among the six children arbitrarily which can be done in 159 11628 waysi Lecture 4 7 April 6 Example How many ways are there to order six 0s ve 1s and four 2s so that the rst 0 occurs before the rst 1 which in turn occurs before the rst 2 Solution We can build up the words one group of letters at a time To simplify the process we rst put down the 2s then the 1s and nally the Us First putting down the 2s we have 2222 Next we put down the 1s which can go before and after the 2s iiei U2U2U2U2U To satisfy the constraint we must have one of the 1s go into the rst slot and the remaining n 4 1s are distributed among the k 5 slots which can be done in 3 ways We now need to decide how to put in the 0s these again can go before and after the letters already placed iiei u1uuuuuuuuu To satisfy the constraint we must have one of the 0s go into the rst slot and the remaining n 5 0s are distributed among the k 10 slots which can be done in 194 waysi Combining this gives us 8 14 lt4 lt9 140140 ways Many problems into combinatorics relate to the problem of placing it balls into k binsi The number of ways to do this is dependent on our assumptions 0 Identical balls and distinct bins This is what was discussed in the previous lecture so it can be done in n k 7 1 k 7 1 ways 0 Distinct balls into distinct bins lmagine we place the balls one at a timer The rst ball can go into any of k bins the second ball can go into any of k bins i i i the nth ball can go into any of k binsi So by the multiplication rule the number of ways that this can be done is kkkkni n times 0 Distinct balls into distinct bins with number of balls in each bin speci ed T at is we want to place the balls so that n1 balls go into the rst bin n2 balls go into the second bin 1 i i nk balls go into the kth bin where n n1 nki This can be done by choosing n1 balls for the rst bin then choose ng of the remaining balls for the second bin ng of the now remaining balls for the third bin and so on The number of ways to do this is n n7n1 n7n17n277nk1 n1 n2 at 7 which from the last lecture is the same as nl nllngl nkl o Identical balls into identical bins This looks at how to break up the n balls into groups where or der is unimportant This leads to the eld of par titions an area of combinatorics with really beau tiful proofs and really hard problems7 we will be looking at these in a later lecture1 o Distinct balls into identical bins This looks at how to break up 7 7 1 1 1 7 n into small sub sets This can be counted using Bell numbers and Stirling numbers which we will look at brie y in a later lecture The number of ways of distributing n identical ob jects into k bins has another interpretations7 namely the number of nonnegative integer solutions to 11I2IknA To see this we count the balls7 let 11 be the number of balls in the ith bin7 then the sum of the 11 is the total number of balls which is n Conversely7 given a solution of 11 we can make a distribution into the bins by putting 11 balls into the ith bin for each i Example Count the number of integer solutions for each of the following 11zlzgzgz4 10 with 112 01 21zlzgzgz4 10 with 1121 31zlzgzg314 10 with 17 2 01 41 zlzgzgz4 10 with 1120 Solution We have the following 11 This is the straightforward case of n 10 and 4 variables so this can be done in 133 286 ways to 1 We satisfy the constraint 11 2 1 by rst distribut ing 1 to each 117 we now distribute the remaining n 6 among the k 4 variables so this can be done in 84 ways CA3 1 The dif cult part about this is the 14 term7 so we break into cases depending on the value of 141 1f 14 0 we distribute it 10 among k 3 which can be done in ways 1f 14 1 we distribute it 7 among k 3 which can be done in ways 1f 14 2 we distribute it 4 among k 3 which can be done in ways1 Finally7 if 14 3 we distribute it 1 among k 3 which can be done in ways1 So by the addition rule the total number of solutions is 122 T 1 120 Wm 41 We could break this up as we did the previous case and get the sum of several terms1 However we can avoid all of this by considering the auxiliary problem zlzgzgz4z510 withzi201 Here the 15 represents what we are short by in our sum to 101 In particular each solution to this problem is a solution to our original problem7 giving us 4 17 001 ways1 Example How many ways are there to rearrange the letters of the word MATHEMATICASTER so there are no consecutive vowels Solution We break this into three steps First the constraint gives us relationships between the conso nants and the vowels so we will see how many vowel consonant patterns there are There are six vowels and nine consonants1 If we put down the six vowels then we need to decide how to distribute the consonants among the vowels7 i1e17 uVuVuVuVuVuVu To satisfy our constraint we have to put ve of the con sonants in slots between the vowels7 we can distribute the remaining n 4 consonants among the k 7 slots which can be done in It ways1 Given the pattern we now arrange the vowels and consonants which can be done respectively in and ways 61 91 312111 312111111111 Combining everything we have 61 91 10 1 lt6 gt3931211139312111111111 381 024 000 ways The binomial theorem looks at expressions of the form I The term binomial refers to the two nomials7 or variables7 z and y1 For the rst few cases we have 1 y 1 I y1 z y 1y2 1221yy2 1 y3 ms 3z2y 3w y3 z y4 224 My My 4M y4 In general we have 1y 1yIyIy n terms The idea behind the term is that the way we mul tiply out I y is to choose one term from each of the n copies of I y to get zkyn k we have to choose the I value for exactly k of the n possible places which can be done in Because of its connection to the binomial theorem the terms are also known as binomial coe cientsi There is a more general version of the binomial at tributed to Isaac Newton First we de ne for any num ber r even imaginary and integer k 2 1 T 7rr71r7k71 k 7 kl Further we let 1 Then for lt 1 1 my 111 In the case that r is an integer then the term be comes 0 for k suf ciently large so this gives us back the form of the binomial theorem given above Lecture 5 7 April 8 As an application of the binomial theorem we have the following Lete2i718281828uiand0 lc n7 then k k E lt n lt E Q 70970 Proof For the rst inequality we have ltngt 3n71n72lnn7k71 k kk71k72 k7k71 2 m3 k 7 E k v where we used the fact that n 7 ak 7 a 2 nk for 0 S a S k 7 1 For the other inequality we rst note that from calculus we have that e 2 1 z for all I In particular for z 2 0 we have lt73 lt2gtza Now choose I kn and simplify to get the result 1 em gt 11 n l V Today we will look at using the binomial theorem and more generally at the binomial coef cients Our starting point will be looking at the coef cients in the binomial theorem7 iiei7 These can be arranged in a triangle known as Pascalls triangle as follows 15101051 1615201561 These numbers occur frequently in combinatorics so it is good to have the rst few rows memorized and know some of the basic properties of numbers in this trianglei We will now start to describe some of the various properties of the numbers in this trianglei One thing which is apparent is that the rows are symmetric In terms of the binomial coef cients this says the following n 7 n k 7 n 7 k Algebraic proof Using the de nition of from a previous lecture we have lt2 D Combinatorial proof By de nition is the number of ways to choose k elements from a set of n elements This is the same as deciding which n 7 k numbers will not be chosen which can be done in ways 1 We have now given two proofsi Certainly one proof is suf cient to show that it is true Nevertheless it is useful to have many different proofs of the same fact for instance there are hundreds of proofs for the Pythagorean Theorem and new ones are constantly be ing discvoered since they can give us different ideas of how to use these tools in other problems By com binatorial proof7 we mean a proof wherein we count some object in two different ways ie using the Rule of Counting in Two Ways from the rst lecturei Another pattern that seems to be happening is that the terms in the rows rst increase until the halfway point and then they decreasei This behavior is called unimodal and we have the following TL For n xed ltk gt is unimodali Proof To show this we have to show that it rst will increase and then decrease This can be done by looking at the ratio of consecutive terms In particular we have then 2 2 J1 then 2 S kill Substituting in the de nition for the binomial coeffi cient we have 2 21 11 g 1 Z n 7 k 1 11 k717ii7k1 k Solving we see that 2 1 when k S nl2i In particular we see that for the rst half of a row on Pascal7s triangle that the binomial coefficients will increase and for the second half of the row they will decrease Actually more can be said about the size of the bi nomial coefficients Namely it can be shown that they form the infamous bell shaped curvei One very important pattern is how the coefficients of one row relate to the coefficients of the previous rowi This gives us the most important identity for binomial coefficients n n 7 l n 7 l ltkgtltk71gtltkgt In other words this says to nd the term in Pas cal7s triangle you look at the two numbers above and add themi Using this one can quickly generate the rst few rows so instead of memorizing the rows you can also memorize the rst three or four and then memo rize how to ll in the rest This also can be used to give an inductive proof for the binomial theoremi Algebraic proof Plugging in the de nitions for bino mial coefficients we have lt1gtlt gt 7 n71 n71 n71 1 1 k71n7k71 lt igt n71 n k71n7k71 Win Combinatorial proof We have that is the number of ways to select k elements from 12i i i n i Using the addition rule this is the number of ways to select k elements from 1 2 i i i n with n being one of the chosen elements added to the number of ways to select k elements from 12i i i n with n not being one of the chosen elements In the rst case there are ways to choose the remaining k 7 1 elements other than n and in the second case there are ways to choose k elements other than n If we sum the values in the rst few rows of Pascal7s triangle we see that we get 124 816 32 64 This is a nice pattern and it holds in general ltgtltzgtltgtltgt7w Algebraic proof Putting z y 1 into the binomial theorem we have 2 1 1 1211617146 I D M k 0 Combinatorial proof In a previous lecture we saw that the number of subsets of 12Hin is 27h On the other hand the number of subsets with k elements is Combining these two ideas we have that the number of subsets is the number of subsets of size 0 added to the number of subsets of size 1 added to the number of subsets of size 2 i i i added to the number of subsets of size n We can also use the binomial theorem in more subtle ways Algebraic proof Thinking of the binomial theorem in terms of a function of I we nz 1 1 1 7 d n k n 7 n 71 n 7dzltZz ltkgtgt72kz k l 160 160 Substituting 1 l on the left and right sides gives us the result D Of course this also has a combinatorial interpreta tion Combinatorial proof Examining the term this counts the number of ways to pick a kelement subset and then pick one of these elements We can interpret this as the number of ways of forming a committee of size It with a chairperson ie first we pick the k people who will be on the committee and then we select one of the chosen people to be the chair So the left hand side which sums over all possible committee sizes counts all possible ways to form a committee with a chairpersoni We can also count this by first selecting the chairper son which can be done in n ways and then choosing the rest of the committee Since there are n71 people available to serve on the committee with the chair we can fill in the rest of the committee in 2 1 ways Counting committees arrangements gives some sim ple arguments to some binomial identitiesi As another example of this type of committee forming argument consider the following 160 k r 7 k r Combinatorial proof Let us count the number of ways to form a committee of size r from a group ofm women and n men If we ignore the gender balance since there are mn people then this can be done in waysl On the other hand the number of ways to form a committee with exactly k women is to first select the women in ways and then fill up the remaining seats with the men in waysl So is the number of ways to form our committee of total size r with exactly k womeni Since the possible values for k are 012 l l r the result now follows by the rule of addition There is also an algebraic proofi We do not give all the details but only provide a brief sketch The right hand side is the coefficient of IT in the expansion of 1zm the left hand side is the coefficient of IT in the expansion of l zml 1 Since 1zmn 1 zml I the coefficients must be equal giving the result As a special case of the previous result we have the following n 2 n 2 n 2 2n 0 lt1gt quot39ltngt 0 In other words if we add up the square of the num bers in a row of Pascalls triangle the result is another binomial coefficienti To see how this follows from what we just proved we note that using the symmetry of the binomial coefficients lt3gt2ltTgt2ltZgt2 7 2n 7 n The last step follows from noting that this is the pre vious result with m r no The following is a useful fact for rewriting product of binomial coefficients n k 7 n n 7 m k m 7 m k 7 m Algebraic proof Plugging in the definitions for the binomial coefficients we have 711 n 7 krlk 7 m Mani k mm m lt2 51gt D Combinatorial proof Examining the left hand side we first pick k out of n elements and then we pick m out of k elements We can interpret this as the number of sets A and B so that A Q B Q X with lAl m lBl k and le no That is given an n element set X we first pick B as a k element subset of X and then pick A as an m element subset of El We could also count this in a different way Namely we first pick the set A which can be done in ways and then pick B so that A Q B Q Xi To do the second step we need to fill out77 the set E by adding an additional k 7 m elements to the It already chosen for A since there are n7m elements not in A to choose from we can do this in waysl Lecture 1 7 March 30 We start our investigation into combinatorics by fo cusing on enumerative combinatoricsi This topic deals with the problem of answering how many77 We will start with a set S which is a collection of objects called elements and then we will determine the number of elements in our set denoted More information about the basics of set theory are found in the ap pendix of Applied Combinatoricsi We start with a few basic rules for counting Addition Rule 1f the set we are counting can be broken into disjoint pieces then the size of the set it the sum of the size of the pieces SUS Si Sj ifi9 j a SZSl i1 i1 Example A square with side length 4 is divided into 16 equal sqaures as shown below What is the total number of squares in the picture Solution We break the squares up according to size There are sixteen 1 X 1 squares nine 2 X w squares four 3 X 3 squares and one 4 X 4 square So by the addition rule there is a total of 16 9 4 1 30 squares Note here we must be careful about what is meant by disjoint Geometrically as squares the squares are not all disjoint one from another but we are not concerned with the geometry of the problem so when we talk about disjoint we mean not the same square So in our case when we broke up the squares into these sets by size theses sets are disjoint one from another Multiplication Rule Suppose we can describe the elements in our set us ing a procedure with m steps where at the ith step we have Ti choices available Where the number of choices is independent of our previous choices Then the size of the set is 7 17 2 quotrm It is important to realize that what we are counting using the multiplication rule is the number of choices that can be made In order to guarantee that we get the right count it is important that 1 every element in our set is realizable by at least one set of choices and 2 no two sets of choices gives us the same element An example of what can go wrong will be given in a later lecture Another important thing to note is that the number of choices is independent on the previous choices but not necessarily the choice that we have to make This is illustrated in the next example Example How many standard California license plates are possible A standard license plate has the form NLLLNNN where N is a number and L is a letter How many are possible if there is no repetition of numbers or letters Solution We can form the license plate one character at a time So we will use the multiplication rule where the decision at the ith stage is what character goes in the ith slot Since there are 10 possible numbers and 26 possible letters we have that the number of license plates is 10262626101010 175 760 000 When we add the restriction that that there is no rep etition of characters we again use the same principle as before Now the difference is that when we ll in the second number we only have nine options since we have already used one number when we ll in the third we only have eight options and when we ll in the fourth we only have seven Note that here we do not know which nine eight or seven choices are avail able because that depends on previous choices but the number of choices does not So the number when there is no repetition of numbers is 10262524987 78 624 000i Bijection Rule 1f the elements in S can be paired in a onetoone iiei bijective fashion then lSl We have already used the bijection rule when we did the multiplication rule since what we are doing is counting the number of choices which are paired onetoone with the elements One interesting thing is that it is possible to show that two sets have equal size by giving a bijection between the sets without ever knowing the size of the sets themselves Example How many subsets of 1 2 i i i n are there Solution We can pair a subset of with a binary word of length n a binary word is a word with the individual letters coming from 0 and 1 The way this is done is by taking a subset A and letting the ith letter of the binary word be 1 ifi is in A and 0 ifi is not in A For example for 1 2 3 we have 0 H 000 3 H 001 1lt gt100 139101 9010 239011 129110 1239111 Since there are 2 binary words it follows by the bi jection rule that the number of subsets is also 27 Rule of Counting in Two Ways If we count 5 in two different ways the results must be equali This is the basic idea behind many combinatorial proofs Namely we nd an appropriate set and count it in two different ways By then setting them equal we get some nontrivial relationshipsi Example Count the number of 957s in the diagram which has n rows and n 7 1 columns below we show the case n 4 in two different ways 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 Solution For our rst method we count along rowsi Each row has n 7 1 of the 957s and there are n rows so in total we have nn 7 1 total 957s For our second method we count using the diagonalsi In particular we have that there are n 123nn321ZZL i1 Equating these two ways of counting we have nn12i or i1 i1 Probability is counting Probability is a measurement of how likely an outcome is to occur If we are dealing with nitely many possible outcomes and each outcome is equally likely very common assumptionsl then the probability that a certain outcome occurs is the ratio of the outcomes with the desired result divided by the number of all possible outcomes Lecture 2 7 April 1 Example A domino is a tile of size 1 X 2 divided into two squaresi On each square are pips or dots7 the number of pips possible are0717 27 37 47 57 6 There are 28 possible domino pieces7 iiei7 7 7 7 7 i7 7 Two domino pieces t if we can arrange them so the two adjacent squares have the same number of pipsi So for example t do not t What 1s the probability that two dominos chosen at random will t Solution First let us count the total number of ways to pick two dominosi We can think of choos ing one domino and then a second one This can be done in 2827 756 ways But we have overcounted7 this is because the order that we pick domino pieces should not matter So for example right now we dis tinguish between the choice a and the 7 In essence we have counted ev ery pair twicei To correct for this we divide by 2 so that the number of ways to pick two domino pieces is 7562 378 Next let us count the number of pairs for which the dominos t We again think of picking a domino and then seeing how many domino pieces t with it There are two cases7 if we rst pick a domino of the form of which there are seven of this form then dom1nos which t with it are of the form y f 17 so there are six matchesi So in t 1 got 67 42 pairs In the second case we have a domino of the form where I y7 there are 21 such dominos and there are twelve dominos that can t with this type of domino7 namely7 for for 2 f y So in this case we got 2112 252 pa1rsi Combining we have 42 7 252 294 pairs that match7 but as before we have counted every pair twice and so there are 147 pairs of dominos that t Combining we have that the probability that two dominos chosen at random will t is 147378 7181 Given a set with n objects7 a permutation is an ordered arrangement of all n of the objects An 7 permutation is an ordered arrangement of 7 of the n objects An T combination is an unordered selection of 7 of the n objects We now count how many of each type of the fol lowing there are First off for a permutation by the multiplication rule we choose which object will be rst we have n choices7 then we choose which object will be second we now have n 7 1 choices7 and continue so on to the end So there are nn 71n 7 2 321 nl permutationsi The notation n17 read n factorial777 arises frequently in combinatorics and it is important to get a good handle on using it For example7 it is useful to be able to rewrite factorials7 iiei7 2n2l 2n22n12nli For convenience we will de ne 01 1 this helps to simplify a lot of notation Another useful fact for factorials is Stirling s approx imation which states that n n nlm 27rnlt7gt e This is useful when trying to get a handle on the size of an expression that involves factoriali For instance7 one object which has been extensively studied are the middle binomial coef cients see below which by Sterling7s approximation we have x47rn2n2n 1 7 2n 7 2n N n nlnl 27Tnnx27Tnn x7T7 L The method to count Tpermutations is the same as that of counting permutations We use the multipli cation principle but instead of going through it stages we stop at the Tth stage So we have that there are nltn71n72n7pi nn71n72n7T71nTH21 n7T 21 nl P n 7 This is also sometimes written as the falling factorial nk or n7 To count Tcombinations we can count Tpermu tations in a different way Suppose that we let Cn T be the number of ways to pick T unordered objects then we have Pn T Cn TTli Namely to have an ordering of T elements we rst pick the T elements and then we order them Rearranging we have Cm Pl 7 7 Tl 7 Tln7Tl T The term read n choose T is also known as a binomial coef cient This will be discussed in a future lecture Example How many ways can it rooks be placed on n X n chessboard so no two threaten each other How many ways can It rooks be placed on n X n chessboard if k S n Solution A rook can move along any row and col umn If there are n rooks and at most one rook can go in a column then there will be a single rook in each column We place rooks one column at a time In the rst column we have n choices in the second column we cannot put it in the same row as we used for the rst rook so there are n 7 1 choices for the third col umn we have n 7 2 choices and so on In total there are nn 71n 7 221 nl placements If we have It rooks then the approach is similar First we choose the columns that the rooks will go into This can be done in Cn 16 ways Once we have the columns we place rooks in one column at a time In particular the way that we can distribute the rooks in the k columns is nn71n7k71 Pnki Putting it together the number of ways to place the k rooks is Cn kPn k Problems of placing rooks on chessboards can lead to some interesting and highly nontrivial combina toricsl These types of problems can arise in algebraic combinatorics which unfortunately we will not have time to address this quarter Example Given eight points which line in the plane no three on a line how many lines do these points determine Solution To determine a line we need two points So this reduces to the number of ways to pick two of the eight patterns which can be done in ways Note that it is important that no three are on a line to guarantee that we do not overcountl Lecture 3 7 April 3 Example How many ways are there to choose k el ements from 121Hn so that no two are consecutive Solution If we did not have the restriction that el ements couldn7t be consecutive then we could do this in ways The problem is on how to guarantee that the elements are not consecutive Suppose that our elements we choose are a1lta2lta3ltltak where no two are consecutive Using the fact that no two are consecutive we have that a1lta271lta372ltltak7k71i These are k ditinct elements from n 7 k 7 1 121Hn 7 k 7 On the other hand given It distinct elements 121 lt 122 lt lt bk from n 7 k 7 1 we can nd It elements from for which no two are consecutive namely the elements b1ltb21ltb32ltltbkk71i So the number of ways there are to choose k elements from 121 1 i n so that no two are consecutive is the same as the number of ways there are to choose k elements from n 7 k 7 1 which is SI171 When using the multiplication principle it is impor tant to make sure that different sets of choices do not lead to the same outcome This can sometimes be subtle to detect so great care should be taken Example From among seven boys and four girls how many ways are there to choose a six member volleyball team with at least two girls Solution One seemingly natural approach is to rst pick two girls and then pick the remainder of the teami This way we guarantee that we meet the condition The number of ways to pick the two girls is 9 there are now nine people left and we have to choose 4 of then and this could be done in 3 ways for a grand total of Z 756 different possible teamsi But wait Suppose the girls are AB CD and the boys l234567 then we could have rst chosen AB and then C246 to form the team ABC246 but we could also have rst chosen BC and then A246 to form the team ABCV246 So different choices gave us the same teami We have committed the cardinal sin of overcountingi To correct this we have two options one is to gure out how much we have overcounted and then subtract off the overcounti The other is to go back and count in a different way one such different method is to split up the count into smaller cases where we won7t overcounti For example in this problem let us break it up by the number of girls on the teami If there are two girls we pick two girls and four boys to form the team which can be done in I if there are three girls we pick three girls and three boys to form the team which can be done in 3 if there are four girls we pick four girls and two boys to form the team which can be done in i ways so altogether there are 371 teams An arrangement of n distinct objects is nli But what happens if the objects are not distinct For example suppose we are looking at anagrams rearrangements of letters of a word For instance STEVE BUTLER can be arranged to RUE VEST BELT but it could also be arranged to gibberish VTSBEEERTLUW So the number of ways there are to rearrange the letters of a given word allowing for gibberish answers is found by counting the arrangements of objects with repeti tioni Example How many ways are there to rearrange the letters of the word BANANA Solution We present two methods The rst method is to group the letters together by type We have one B three As and two Nsi We now start with six empty slots which we will ll in with our letters in order First we put in the B there are six slots and we must choose one of them so this can be done in ways We now have ve slots left for us to choose for the position of the three As which can be done in waysi Finally we have two slots left for us to choose for the position of the two Ns which can be done in waysi Giving us a total of 6 5 2 lt1 lt3 lt2 7 60 rearrangementsi For our second method we rst make the letters dis tinct This is done by labeling so we have the letters B A1 A2 A3 N1 N2 These letters can be arranged in 6 ways and nally we remove the labalingi The prob lem is that we have now overcountedi For instance for the end result of ABANNA this would show up twelve ways as AlBAQNlNQAg AlBAgNlNQAQ AQBAlNlNQAg AQBAgNlNQAl AgBAlNlNQAQ AgBAQNlNQAl AlBAQNQNlAg AlBAgNQNlAQ AQBAlNQNlAg AQBAgNQNlAl AgBAlNQNlAQ AgBAQNQNlAl Namely we have 3 ways to label the As and 2 ways to label the Ns and ll ways to label the B This happens with each arrangement so in total we have 6V m 60 rearrangementsi These two approaches generalize The rst idea is to choose the slots for the rst type of objects then choose the slots for the second type of objects and so on The second idea is to label the elements and permute and then divide out by the overcountingi Given n1 objects of type 1 n2 objects of type 2 Hi nk objects of type k and n n1n2 nk then the number of ways to arrange these objects is n ninl ninlingininka n1 n2 nk nl lt n gt nllngl nkl n1n2uink The term m n M is also known as a multinomial coefficient we will discuss these more in a later lecturer Example How many ways are there to rearrange the letters of ROKOKO so there in no 000 Solution The number of ways to rearrange the letters of ROKOKO is the same as the number of ways to rearrange the letters of BANANA so there are 60 in a i But of course some of these have 000 but we can use one of the most useful techniques in counting Sometimes it is easier to count the complement S we now count the number of arrangements with 000771 This can be done by considering the arrange ments of the letters RKKOOOi This can be done in 4121 12 ways So the total number of rearrange ments without 000 is 60 7 12 48 A related problem is to distribute it identical objects among k different boxes or people or days or so on One way to do this is to use 7s stars to denote the identical objects and lay them down in a rowi We then draw in k 7 1 dividing lines bars which divides the n objects into k groups the rst group goes in the rst box the second group goes in the second box and so on For example suppose we are distributing n 20 pennies among k 6 children Then using bars and stars we represent giving four pennies to the rst child two to the second six to the third none to the fourth ve to the fth and three to the sixth by In this case we have a total of 25 bars and stars and once we know where the bars or stars go then we know where the stars or bars go So the number of ways to do the distribution is the number of ways to pick the bars or stars which is The number of ways to distribute it identical objects into k distinguished boxes is n k 7 1 7 n k 7 1 k 7 1 7 n Example How many ways are there to distribute twenty pennies among six children What if each child must get at least one penny Solution We already have answered the rst part this can be done in 53130 ways For the sec ond part we distribute pennies in two rounds 1n the rst round we give one penny to each child thus sat isfying the condition that each child gets a penny 1n the second round we distribute the remaining fourteen pennies among the six children arbitrarily which can be done in 159 11628 waysi Lecture 4 7 April 6 Example How many ways are there to order six 0s ve 1s and four 2s so that the rst 0 occurs before the rst 1 which in turn occurs before the rst 2 Solution We can build up the words one group of letters at a time To simplify the process we rst put down the 2s then the 1s and nally the Us First putting down the 2s we have 2222 Next we put down the 1s which can go before and after the 2s iiei U2U2U2U2U To satisfy the constraint we must have one of the 1s go into the rst slot and the remaining n 4 1s are distributed among the k 5 slots which can be done in 3 ways We now need to decide how to put in the 0s these again can go before and after the letters already placed iiei u1uuuuuuuuu To satisfy the constraint we must have one of the 0s go into the rst slot and the remaining n 5 0s are distributed among the k 10 slots which can be done in 194 waysi Combining this gives us 8 14 lt4 lt9 140140 ways Many problems into combinatorics relate to the problem of placing it balls into k binsi The number of ways to do this is dependent on our assumptions 0 Identical balls and distinct bins This is what was discussed in the previous lecture so it can be done in n k 7 1 k 7 1 ways 0 Distinct balls into distinct bins lmagine we place the balls one at a timer The rst ball can go into any of k bins the second ball can go into any of k bins i i i the nth ball can go into any of k binsi So by the multiplication rule the number of ways that this can be done is kkkkni n times 0 Distinct balls into distinct bins with number of balls in each bin speci ed T at is we want to place the balls so that n1 balls go into the rst bin n2 balls go into the second bin 1 i i nk balls go into the kth bin where n n1 nki This can be done by choosing n1 balls for the rst bin then choose ng of the remaining balls for the second bin ng of the now remaining balls for the third bin and so on The number of ways to do this is n n7n1 n7n17n277nk1 n1 n2 at 7 which from the last lecture is the same as nl nllngl nkl o Identical balls into identical bins This looks at how to break up the n balls into groups where or der is unimportant This leads to the eld of par titions an area of combinatorics with really beau tiful proofs and really hard problems7 we will be looking at these in a later lecture1 o Distinct balls into identical bins This looks at how to break up 7 7 1 1 1 7 n into small sub sets This can be counted using Bell numbers and Stirling numbers which we will look at brie y in a later lecture The number of ways of distributing n identical ob jects into k bins has another interpretations7 namely the number of nonnegative integer solutions to 11I2IknA To see this we count the balls7 let 11 be the number of balls in the ith bin7 then the sum of the 11 is the total number of balls which is n Conversely7 given a solution of 11 we can make a distribution into the bins by putting 11 balls into the ith bin for each i Example Count the number of integer solutions for each of the following 11zlzgzgz4 10 with 112 01 21zlzgzgz4 10 with 1121 31zlzgzg314 10 with 17 2 01 41 zlzgzgz4 10 with 1120 Solution We have the following 11 This is the straightforward case of n 10 and 4 variables so this can be done in 133 286 ways to 1 We satisfy the constraint 11 2 1 by rst distribut ing 1 to each 117 we now distribute the remaining n 6 among the k 4 variables so this can be done in 84 ways CA3 1 The dif cult part about this is the 14 term7 so we break into cases depending on the value of 141 1f 14 0 we distribute it 10 among k 3 which can be done in ways 1f 14 1 we distribute it 7 among k 3 which can be done in ways 1f 14 2 we distribute it 4 among k 3 which can be done in ways1 Finally7 if 14 3 we distribute it 1 among k 3 which can be done in ways1 So by the addition rule the total number of solutions is 122 T 1 120 Wm 41 We could break this up as we did the previous case and get the sum of several terms1 However we can avoid all of this by considering the auxiliary problem zlzgzgz4z510 withzi201 Here the 15 represents what we are short by in our sum to 101 In particular each solution to this problem is a solution to our original problem7 giving us 4 17 001 ways1 Example How many ways are there to rearrange the letters of the word MATHEMATICASTER so there are no consecutive vowels Solution We break this into three steps First the constraint gives us relationships between the conso nants and the vowels so we will see how many vowel consonant patterns there are There are six vowels and nine consonants1 If we put down the six vowels then we need to decide how to distribute the consonants among the vowels7 i1e17 uVuVuVuVuVuVu To satisfy our constraint we have to put ve of the con sonants in slots between the vowels7 we can distribute the remaining n 4 consonants among the k 7 slots which can be done in It ways1 Given the pattern we now arrange the vowels and consonants which can be done respectively in and ways 61 91 312111 312111111111 Combining everything we have 61 91 10 1 lt6 gt3931211139312111111111 381 024 000 ways The binomial theorem looks at expressions of the form I The term binomial refers to the two nomials7 or variables7 z and y1 For the rst few cases we have 1 y 1 I y1 z y 1y2 1221yy2 1 y3 ms 3z2y 3w y3 z y4 224 My My 4M y4 In general we have 1y 1yIyIy n terms The idea behind the term is that the way we mul tiply out I y is to choose one term from each of the n copies of I y to get zkyn k we have to choose the I value for exactly k of the n possible places which can be done in Because of its connection to the binomial theorem the terms are also known as binomial coe cientsi There is a more general version of the binomial at tributed to Isaac Newton First we de ne for any num ber r even imaginary and integer k 2 1 T 7rr71r7k71 k 7 kl Further we let 1 Then for lt 1 1 my 111 In the case that r is an integer then the term be comes 0 for k suf ciently large so this gives us back the form of the binomial theorem given above Lecture 5 7 April 8 As an application of the binomial theorem we have the following Lete2i718281828uiand0 lc n7 then k k E lt n lt E Q 70970 Proof For the rst inequality we have ltngt 3n71n72lnn7k71 k kk71k72 k7k71 2 m3 k 7 E k v where we used the fact that n 7 ak 7 a 2 nk for 0 S a S k 7 1 For the other inequality we rst note that from calculus we have that e 2 1 z for all I In particular for z 2 0 we have lt73 lt2gtza Now choose I kn and simplify to get the result 1 em gt 11 n l V Today we will look at using the binomial theorem and more generally at the binomial coef cients Our starting point will be looking at the coef cients in the binomial theorem7 iiei7 These can be arranged in a triangle known as Pascalls triangle as follows 15101051 1615201561 These numbers occur frequently in combinatorics so it is good to have the rst few rows memorized and know some of the basic properties of numbers in this trianglei We will now start to describe some of the various properties of the numbers in this trianglei One thing which is apparent is that the rows are symmetric In terms of the binomial coef cients this says the following n 7 n k 7 n 7 k Algebraic proof Using the de nition of from a previous lecture we have lt2 D Combinatorial proof By de nition is the number of ways to choose k elements from a set of n elements This is the same as deciding which n 7 k numbers will not be chosen which can be done in ways 1 We have now given two proofsi Certainly one proof is suf cient to show that it is true Nevertheless it is useful to have many different proofs of the same fact for instance there are hundreds of proofs for the Pythagorean Theorem and new ones are constantly be ing discvoered since they can give us different ideas of how to use these tools in other problems By com binatorial proof7 we mean a proof wherein we count some object in two different ways ie using the Rule of Counting in Two Ways from the rst lecturei Another pattern that seems to be happening is that the terms in the rows rst increase until the halfway point and then they decreasei This behavior is called unimodal and we have the following TL For n xed ltk gt is unimodali Proof To show this we have to show that it rst will increase and then decrease This can be done by looking at the ratio of consecutive terms In particular we have then 2 2 J1 then 2 S kill Substituting in the de nition for the binomial coeffi cient we have 2 21 11 g 1 Z n 7 k 1 11 k717ii7k1 k Solving we see that 2 1 when k S nl2i In particular we see that for the rst half of a row on Pascal7s triangle that the binomial coefficients will increase and for the second half of the row they will decrease Actually more can be said about the size of the bi nomial coefficients Namely it can be shown that they form the infamous bell shaped curvei One very important pattern is how the coefficients of one row relate to the coefficients of the previous rowi This gives us the most important identity for binomial coefficients n n 7 l n 7 l ltkgtltk71gtltkgt In other words this says to nd the term in Pas cal7s triangle you look at the two numbers above and add themi Using this one can quickly generate the rst few rows so instead of memorizing the rows you can also memorize the rst three or four and then memo rize how to ll in the rest This also can be used to give an inductive proof for the binomial theoremi Algebraic proof Plugging in the de nitions for bino mial coefficients we have lt1gtlt gt 7 n71 n71 n71 1 1 k71n7k71 lt igt n71 n k71n7k71 Win Combinatorial proof We have that is the number of ways to select k elements from 12i i i n i Using the addition rule this is the number of ways to select k elements from 1 2 i i i n with n being one of the chosen elements added to the number of ways to select k elements from 12i i i n with n not being one of the chosen elements In the rst case there are ways to choose the remaining k 7 1 elements other than n and in the second case there are ways to choose k elements other than n If we sum the values in the rst few rows of Pascal7s triangle we see that we get 124 816 32 64 This is a nice pattern and it holds in general ltgtltzgtltgtltgt7w Algebraic proof Putting z y 1 into the binomial theorem we have 2 1 1 1211617146 I D M k 0 Combinatorial proof In a previous lecture we saw that the number of subsets of 12Hin is 27h On the other hand the number of subsets with k elements is Combining these two ideas we have that the number of subsets is the number of subsets of size 0 added to the number of subsets of size 1 added to the number of subsets of size 2 i i i added to the number of subsets of size n We can also use the binomial theorem in more subtle ways Algebraic proof Thinking of the binomial theorem in terms of a function of I we nz 1 1 1 7 d n k n 7 n 71 n 7dzltZz ltkgtgt72kz k l 160 160 Substituting 1 l on the left and right sides gives us the result D Of course this also has a combinatorial interpreta tion Combinatorial proof Examining the term this counts the number of ways to pick a kelement subset and then pick one of these elements We can interpret this as the number of ways of forming a committee of size It with a chairperson ie first we pick the k people who will be on the committee and then we select one of the chosen people to be the chair So the left hand side which sums over all possible committee sizes counts all possible ways to form a committee with a chairpersoni We can also count this by first selecting the chairper son which can be done in n ways and then choosing the rest of the committee Since there are n71 people available to serve on the committee with the chair we can fill in the rest of the committee in 2 1 ways Counting committees arrangements gives some sim ple arguments to some binomial identitiesi As another example of this type of committee forming argument consider the following 160 k r 7 k r Combinatorial proof Let us count the number of ways to form a committee of size r from a group ofm women and n men If we ignore the gender balance since there are mn people then this can be done in waysl On the other hand the number of ways to form a committee with exactly k women is to first select the women in ways and then fill up the remaining seats with the men in waysl So is the number of ways to form our committee of total size r with exactly k womeni Since the possible values for k are 012 l l r the result now follows by the rule of addition There is also an algebraic proofi We do not give all the details but only provide a brief sketch The right hand side is the coefficient of IT in the expansion of 1zm the left hand side is the coefficient of IT in the expansion of l zml 1 Since 1zmn 1 zml I the coefficients must be equal giving the result As a special case of the previous result we have the following n 2 n 2 n 2 2n 0 lt1gt quot39ltngt 0 In other words if we add up the square of the num bers in a row of Pascalls triangle the result is another binomial coefficienti To see how this follows from what we just proved we note that using the symmetry of the binomial coefficients lt3gt2ltTgt2ltZgt2 7 2n 7 n The last step follows from noting that this is the pre vious result with m r no The following is a useful fact for rewriting product of binomial coefficients n k 7 n n 7 m k m 7 m k 7 m Algebraic proof Plugging in the definitions for the binomial coefficients we have 711 n 7 krlk 7 m Mani k mm m lt2 51gt D Combinatorial proof Examining the left hand side we first pick k out of n elements and then we pick m out of k elements We can interpret this as the number of sets A and B so that A Q B Q X with lAl m lBl k and le no That is given an n element set X we first pick B as a k element subset of X and then pick A as an m element subset of El We could also count this in a different way Namely we first pick the set A which can be done in ways and then pick B so that A Q B Q Xi To do the second step we need to fill out77 the set E by adding an additional k 7 m elements to the It already chosen for A since there are n7m elements not in A to choose from we can do this in waysl We have already seen how to use committees to give identities about binomial coef cients Another useful object is studying walks on a square lattice Example On the square lattice shown below how many different walks are there from 00 to 74 which consists of steps to the right by one unit or up one unit 4 0 Solution Looking at the walks we see that we will need to take 7 steps to the right and 4 steps up for a total of 11 steps Moreover every walk from 00 to 74 can be encoded as a series of right steps R and up steps For instance the path RRRUURRURRU corresponds to the following path 4 0 So the number of walks is the same as the number of ways to arrange seven Rs and four Us which is 141 171 330 ie choose when we take an up step or choose when we take a right stepi Example On the square lattice shown below how many different walks are there from 00 to 74 which consists of steps to the right by one unit or up one unit 77 4 00 l Solution This problem is nearly the exact same as the problem before except now we have to forbid some walksi In particular we have to throw out all walks that pass through the point 4 2 So let us count how many walks there are that pass through 42i Such a walk can be broken into two parts namely a walk from 0 0 to 4 2 of which there are such walks and a walk from 4 2 to 7 4 of which there are such walksi Since we can combine these two halves of the walk arbitrarily then by the Rule of Multipli cation the number of walks that pass through 42 is 150 Therefore the number of walks not passing through is 330 7 150 180i Lecture 6 7 April 10 As another application of the binomial theorem we have the following For n 2 1 n gel 0 In other words starting with the second row and going down if we sum along the rows alternating sign as we go the result is 0 Given the symmetry it trivially holds when k is odd it is not trivial to show that it holds when k is even Algebraic proof In the binomial theorem set I 71 and y l to get 0 711 khklnikG 21k D Combinatorial proof First note that this is equivalent to showing the following lt3gtlt3gtltzgtlt gtltzgtlt2gt The left hand side counts the number of subsets of 12Hin with an even number of elements while the right hand side counts the number of subsets with an odd number of elements To show that we have an equal number of these two types we will use an involution argument An involution on a set X is a mapping 45 z X A X so that 1 Given an involution 45 the elements then naturally split into xed points elements with z or pairs two elements I f y where y and My as In our case our involution will act on 2M the set of all subsets of 1 2 i i i and is de ned for a subset A as follows Al iflis in A MA AU1 1fl 1s not 1n Al In other words we take a set and if 1 is in it we re move it and if 1 is not in it we add it We now make some observations First for any subset A we have A so that it is an involutioni Further there are no xed points since 1 must either be in or not in a set So we can now break the collection of subsets into pairs A Finally by the involution A and 45A will differ by exactly one element so one of them is even and one of them is odd So we now have a way to pair every subset with an even number of elements with a subset with an odd number of elements So the number of such subsets must be equa i We now give two identities which are useful for sim plifying sums of binomial coef cientsi ltzgtltnrgtltnrgtlt 1gt7 ltgtltk1gtltgtlt1gt1 To prove the rst one we will count the number of walks from 07 0 to n17 16 using right steps and up steps in two ways Lm 0 We must make n 1 steps to the right and k steps up So the number of ways to walk from one corner to the other is the number of ways to choose when to make the up steps which is n k 1 lt k 1 We can also count the number of walks by grouping them according to which line segment is used in the last step to the right in the picture above this cor responds to grouping according to the line segment which intersects the dotted line These line segments go from to n 17i where i 0111161 Once we have crossed the line segment there is only one way to nish the walk to the corner straight up the side On the other hand the number of ways to get to n7 is So by the rule of addition we have that the total number of walks is n 0 n 1 n 2 n k ltogtlt1gtlt2gtmltkl Combining these two different ways to count the paths gives the identity A proof of the other result can be done similarly us ing the following picture we leave it to the interested reader to ll in the details 7hkD These identities can also be proved by using i For example7 we have the following ltZgtltkZ1gt ltZgtlt 21gtltZigt lt2gtltnsgtltk1gtlt1gt lt2gtltngtltkgtltgt When 1 was taught these identities they were called the hockey stick77 identitiesi This name comes from the pattern that they form in Pascalls trianglei For instance we have that shown below in blue is the shown below in red The other identity corresponds to looking at the mirror image of Pascalls trianglei We now give an application of the hockey stick iden tity if nn162n1 390 1n the rst lecture we saw how to add up the sum ofi by counting dots in two different ways Here we want to sum up i2 the problem is that we don7t have an easy method to do that We do have an easy method to add up the binomial coef cients7 so if we can rewrite i2 in terms of binomial coef cients then we can easily answer this question So consider the following The ability to rewrite i2 as a combination of binomial coef cients can also be used for any other polynomial expression of if The trick is to nd the coef cients involved For the case of polynomials of the form if we have that the coef cient of is kl i where are the Stirling numbers of the second kind which we will discuss in a later lecturer Now using this new way to write i2 we have HMS o N m H Ems o A O O N V Jr A H N V V n 1nn 71 n1n 2fT mnqwg n 1n2n 1 6 i The only dif cult step now is going from the second to the third line which is done using the hockey stick identityi There is a more general form of the binomial the orem known as the multinomial theorem multino mial77 referring to many variables as compared to bi nomial77 which refers to two It states 1112quot391kn n n1 m M E n n ngt1112quot391k7 n1n2 quotkquot 1 27 k quot120 n220 quotk20 where n 7 nl n1n2uink nllnglnnkl is the multinomial coef cient we have seen in previous lectures Returning to the binomial theorem we have that Wltzgtltalgtzltzgtw In particular for it xed all of the binomial coef cients are stored as coef cients inside of the function fz 11 In general given any sequence of num bers a0a1a2iu possibly in nitely many we can store these as coef cients of a function which we call the generating function as follows 91a0alzagz2i There are different ways that we can store the se quence as coef cients leading to different classes of generating functions This method is what is known as an ordinary generating function in a later lecture we will see what are known as exponential generating functionsi Generally speaking we will treat the function as a formal series ie as an algebraic rather than ana lytic structure This makes it convenient to work with when we do not need to worry about convergencei Nevertheless we will make extensive use of analytic techniques when we do that is when we will start to worry about convergence Let us now consider the problem of nding the gen erating function for the sequence an where k is fixed In other words we want to nd a function so that its series expansion note that there are in nitely many an in this case is 99 Zn y We can do this by actually investigating a much more general functioni Namely we will use a generating function with two variables I and y and is de ned as follows it h17yi 1m Using the binomial theorem we have MW wax gynmw gnaw n 1 7 1 17y1z 17yizy Note that this function stores the entire Pascalls tri angle inside of it In the above derivation we used the following im portant identity 00 1222sz i Analytically this is true for lt 1 formally this is always true Now to nd our desired gy we are looking for the coef cient of zki So we now rewrite hz y as a power series in z and get 1 7 m 7 7 iltlt1eyigtklgtzi k0 hwy H Finally reading off the coef cient for xk in hx y gives us our desired function name y k 99 Zn Lecture 7 7 April 13 Today we look at one motivation for studying gen erating functions namely a connection between poly nomials and distribution problems Let us start with a simple example Example Give an interpretation for the coef cient of x11 for the polynomi gx 1 x2 x3 x5 Solution First note that we can write gx as 1x2x3x51x2x3x51x2x3x5 and that a typical term which we will get when we expand has the form xnlxmx g where the term x 1 comes from picking a term from the rst polynomial so n1 6 0 2 35 the term x 2 comes from pick ing a term from the second polynomial so it E 0235 and the term x 3 comes from picking a term from the third polynomial so n3 6 0 2 35i Since we are interested in the coef cient of x11 then we need n1 n2 n3 11 So this can be rephrased as a balls and bins problem where we are trying to distribute 11 balls among three bins where in each bin we can have either 0 2 3 or 5 balls Example Give an interpretation for the coef cient of xT for the function gx lxx2lxx2 xx3x5 Solution By the same reasoning as we have before a typical term in the expansion looks like xnimng with n1 being 0 1 or 2 n2 2 0 and n3 2 0 and even So this can be rephrased as a balls and bins problem where we are trying to distribute 7 balls among three bins where in the rst bin we put 0 1 or 2 balls in the second bin we put any number of balls we want in the third bin we put in an odd number of balls In general given a polynomial 91 91Iy21 9161 with each gi a sum of some power of xs iiei 2x44 I Then the coef cient of xT in gx is the number of ways to place 7 balls into k bins so that in the ith bin the number of balls is g for some i The idea is that the term tells you the restrictions about the kind of balls that can be placed into that bini It is important that the coef cients of the are all 17s We can also start with a balls and bins problem and translate it into nding the coef cient of some appropriate polynomial Example Translate the following problem into nding a coef cient of some function How many ways are there to put 12 balls into four bins so that the rst two bins have between 2 and 5 balls the third bin has at least 3 balls and the last bin has an odd number of balls77 Solution Since there will be 12 balls we will be look ing for the coef cient of x12i Now let us translate the condition on each bin For the rst two bins there are between 2 and 5 balls so 91W Q2I I2 ISI4I5 remember the powers list the number of balls that can be put in the bin For the third bin we have to have at least 3 balls so ggxx3x4i We could also use the function g z zgz4zl27 the difference being that we stop and have a poly nomial instead of an in nite series The reason we can do this is that we are only interested in the co ef cient of x12 anything which will not contribute to that coef cient can be dropped without changing the answer However by keeping the series we can use the same function to answer the question for any arbitrary number of balls and so the rst option is more general Finally for the last bin we have 941z1315m Putting it altogether we are trying to nd the coef cient of x12 for the function x2x3x4x52x3x4xx3x5i Of course translating one problem to another is only good if we have a technique to solve the second prob lemi So our next natural step is to nd ways to deter mine the coef cient of functions of this type To help us do this we will make use of the following identitiesi 1z k0 a znw gltiwkltzgtzmk 17 m1 1x 1zz2mzm 1 1 2 17 lzz forlzlltl 1 nilk k aizw E3lt k gtI kgo The rst two are simple applications of the binomial theorem1 The third is easily veri able by multiplying both sides by l 7 z and simplifying The fourth one is a well known sum and can be considered the limiting case of the third one Note that as a function of 1 ie analytically this makes sense only when lt 11 Formally there is no restriction on I this is because formally 1k is acting as a placeholder1 To see why the last one holds we note that this is 1 1 1 1 W m ntimes 1z121zz2 n times Translating this into a balls and bins problem the co ef cient of Elk would correspond to the number of so lutions of 1 2 nk where each ei 2 01 We have already solved this prob lem using bars and stars namely this can be done in firk ways giving us the desired result We will need one more tool and that is a way to multiply functions We have the following which is a simple exercise in expanding and grouping coef cients1 Given fr aoa11a212w 91 b0blzbgz21 Then 9091 a0170 0171 a1b01 aobk albkil akb01k 1 The key is that the coef cient of 1k is found by combining elements aizi bkizk 1 for i 0111 k1 We now show how to use these various rules to solve a combinatorial problem1 Example How many ways are there to put 25 balls into 7 boxes so that each box has between 2 and 6 balls Solution First we translate this into a polynomial problem1 We are looking for 25 balls so we will be looking for a coef cient of 1251 The constraint on each box is the same namely the between 2 and 6 balls so that the function we will be considering is 91 I2 13 I4 I5 157 1141 z 12 13 I471 Here we pulled out an 12 out of the inside which then becomes 114 in front Now since we are looking for the coef cient of I25 and we have a factor of 114 in front our problem is equivalent to nding the coef cient of 1 in gz 1 1 12 13 I471 Combinatorially this is also what we would do Namely distribute two balls into each bin fourteen balls in total and then decide how to deal with the remaining 111 Using our identities we have gz 11 12 13 I47 1715 7 1 1 5 77 lem I airy 7 7 7 5 7 10 6k k 0191 lt2gtI Z k I kgo Finally we use the rule for multiplying functions to gether to nd the coef cient of 1111 In particular note that in the rst part of the product only three terms can be used as all the rest will not contribute to the 11 coef cient of z 1 So multiplying we have that the coef cient to In is 7 611 7 66 7 61 ltogtltugt lt1gtlt6gtlt2gtlt1gt67055 This can also be done combinatorially1 The rst term counts the numbers without restriction The second term then takes off the exceptional cases but it takes off too much and so the third term is there to add it back in Lecture 8 7 April 15 We can use the rule for multiplying functions to gether to prove various results For instance let M lt1zgtm andgltzgt lt1zgtmhen fltzgtgltzgt l zm i We now compute the coef cient of IT of in two different ways to get iW Hm 160 k 7 7 k 7 The left hand side follows by using the rule of multi plying and 91 while the right hand side is the binomial theorem for We turn to a problem of nding a generating func tion Example Show that the generating function for the number of integer solutions to 1 2 3 4n with0 61 62 63 64is 1 f lt17zgtlt1ez2gtlt1ez3gtlt17w Solution First note that we can rewrite the function as lz12zglz2z415 gtlt11315zglz418112i Note that translating this back into a balls and bins problem this says that we have four binsi In the rst bin we have any number of balls in the second bin we have a multiple of two number of balls in the third bin we have a multiple of three number of balls and in the fourth bin we have a multiple of four number of balls In other words the generating function counts the number of solutions to f12f23f34f4n with f1 f2 f3 f4 2 0 We now need to show that these two problems have the same number of solutions To do this let us start with a solution of 61626364 n and pictorially represent our solution by putting four row of s with 64 stars in the rst row 63 stars in the second row 62 stars in the third row and 61 stars in the fourth rowi Finally let f4 be the number of columns with four s f3 the number of columns with three s f2 the number of columns with two s and f1 the number of columns with one 9a This gives a solution to f1 2f2 3f3 4f4 n This gives a onetoone correspondence between solutions to the two different problems so they have an equal number of solutions giving the result As an example of the last step suppose we start with 359ll 28 Then pictorially this corresponds to the following picture we have marked the number of s in each rowcolumn ll 9 5 3 44433222211 So translating this gives us the solution 2 24 32 43 28 to the second problemi This problem says that the number of ways to break 71 into a sum of at most four parts is the same as the number of ways to break 71 into a sum of parts where each part has size at most fouri We will generalize this idea in the next lecturer For now we start by looking at partitions A partition of a number n is a way to break 71 up as a sum of smaller pieces For instance llllll2l3224 are the ways to break four into pieces We do not care about the order of the pieces so that l l 2 and l 2 l and 2 l l are considered the same partitioni This corresponds to the number of ways to distribute identical balls among identical bins for now we will suppose that we have an unlimited number of bins so that we can have any number of parts in the partition Let pn denote the number of partitions of n n partitions ofn pn 0 0 l l l l 2 11 2 2 3 111 12 3 3 4 1111 112 13 5 22 4 5 lllll lll2 7 11312214 23 5 6 llllll ll llll2 lll3 1122114123 15 222 24 33 6 The function pn has been well studied but is highly nontriviali One of the greatest mathematical geniuses of the twentieth century was the Indian math ematician Srinivasa Ramanujani Originally a clerk in India he was able through personal study discover dozens of previously unknown relationships about par titionsi He sent these along with other discoveries to mathematicians in England and one of them Gr Hi Hardy was able to recognize the writings as some thing new and exciting which caused him to bring Ra manujan to England which resulted in one of the great mathematical collaborations of the twentieth century Examples of facts that Ramanujan discovered include that p5n 4 is divisible by 5 p7n 5 is divisible by 7 and p11n 6 is divisible by 11 One natural question is to whether the exact value of pn is known There is a nice formula for pn name y 0quot sinh I 1 2714 pm Wi gmnwl kfvi T14 Wm where Ak is a speci c sum of 24kth roots of unity Proving this is beyond the scope of our class We now turn to the much easier problem of nding the generating function for pn that is we want to nd 2 n20 The rst thing is to observe that a partition of size n corresponds to a solution of 12523 3quot39k k 39 717 where each ei represents the number of parts of size if Notice in particular the the contribution of ek will be a multiple of kl So turning this back into balls and bins we have n balls and in nitely many binsi So the number of solutions using what we did last time is Zpnzn 1zz2zg y gtlt 112z415 gtlt 11315I9 ET I TRTI gtlt gtlt 1zk12kzgkX i ek term Since 41 172167 we can rewrite the generating function as 12k22k23km 1 1 1 1 n 7 7777 gmn 7 17117121713 171k 1 Hm kZI We can do variations on this For instance we can look at partitions of n where no part is repeated In other words we want to restrict our partitions so that ek 0 or 1 for each kl If we denote these partitions by pd then 2mm lt1zgtlt1z2gtlt1zkgt n20 Hawk k21 Similarly we can count partitions with each part oddi In other words we want to restrict out parti tions so that 62k 0 for each kl If we denote these partitions by p0n then it is easy to modify our con struction for pn to get 1 Emm H1 12171 n20 kZI We can combine these two generating functions to derive a remarkable resulti For n 2 1 we have pdn p0ni Remarkably we do not know in general what pd or p0n is nevertheless we do know that they are equal As an example of this we have that 1006 4 because of the partitions 11111L 111a 13 33 while pa 6 4 because of the partitions 12a 1 21 6 1t suf ces for us to show that the two generating functions are identical 1f the functions are the same then the coef cients must be the same giving us the desired result So we have that Zpdnzn H1 116 n20 kgi 2k 171k kgi 1712171417151718 171171217131713 1 1 1 1izl1izgl1iz5ln 1 H 1 12171 Emm n k21 n20 We can also give a bijective proofi To do this we need to give a way to take a partition with odd parts and produce a unique partition with distinct parts and vice versa This can be done by repeatedly apply ing the following rule until it cannot be done anymore 0 With the current partition if any two parts are equal combine them into a single part For example for the partition 111111 A 21111 a 2 2 1 1 a 4 1 1 A 4 Jr 2 This rule takes a partition with odd parts and produces a partition with distinct parts To go in the opposite direction this cane be done by applying the following rule until it cannot be done anymore 0 With the current partition if any part is even then split it into two equal parts For example for the partition 346 A 2236 a 11236 a 111136 a 1111333 These two rules give a bijective relationship between partitions with an odd number of parts and partitions with distinct parts Lecture 9 7 April 17 We can visually represent a partition as a series of rows of dots much like we did in the example in the previous lecturei This representation is known as a FerreT s diagrami The number of dots in each row is the size of the part and we arrange the rows in weakly decreasing order The partition 4 3 11 would be represented by the following diagrami We can use Ferrer s diagrams to gain insight into properties of partitions For instance one simple op eration that we can do is to take the transpose or the conjugate of the partition This is done by ip ping77 across the line in the picture below so that the columns become rows and rows become columnsi o o o l o a o oh o ob o a o o I Since we do not change the number of dots by taking the transpose this takes a partition and makes a new partition So in this case we get the new partition 4 2 2 1 Note that if we take the transpose of the transpose that we get back the original diagrami There are some partitions such that the transpose ofthe partition gives back the partition such partitions are called self con jugatei For instance there are two self conjugate par titions for n 8 namely 4211 and 332i A famous result says that the number of self conjugate partitions is equal to the number of partitions with distinct odd partsi So for example for n 8 there are two partitions with distinct odd parts namely 7 1 and 5 3 One proof of this relationship is based on using Ferrer s diagrams We will not ll in all of the details here but give the following hint for n 8 o o o o I o I o o c r r Also note that when we take the transposition that the number of rows becomes the size of the largest part in the transposition while the size of the largest part becomes the number of rows So mapping a partition to its transpose establishes the following facti There is a onetoone correspondence between the number of partitions of n into exactly m parts and the number of partitions of n into parts of size at most m with at least one part of size ml It is easy to count partitions with parts of size at most m with at least one part of size ml In particular if we let denote the number of partitions of n into exactly m parts then we have using the techniques from the last lecture 7L1 m I39m 7 7 2 I I 7 m 20 lt1 zgtlt1 z lt1 z gt Another object associated with a Ferrer s diagram is the Durfee square which is the largest square of dots that is in the upper left corner of the Ferrer s diagrami For example for the partition 6 6 4 3 2 11 we have a 3X3 Durfee square as shown in the following picture It should be noted that every partition can be de composed into three parts Namely a Durfee square and then two partitions one on the right of the Durfee square and one below the Durfee square as illustrated belowi i gtlt i partition with square at most 139 parts quotEa 30 ES 04 7 56 um g 156 Q If we group partitions according to the size of the largest Durfee square and then use generating func tions for partitions with at most 239 parts and partitions with parts at most 239 which by transposition are the same generating function we get the following iden tity n n n 7 n2 1 1 2W 7 Z is H H n20 n20 squarek1 k1 left bottom partition pamuon Z 7 7 2 722 7712 n201z1 z 1 I There are a lot more fascinating and interesting things that we can talk about in regards to partitionsi We nish our discussion with the following H1izi172722252772127215ltH n21 Z 1izs jgt2 fooltjltoo This is very similar to what we encountered in the previous lecture namely H1 We saw that this last expression was used to count the number of par titions with distinct parts In the current expression something similar is going on the difference is that previously every partition of n with distinct parts con tributed 1 to the coefficient of I now the contribu tion of a partition of n with distinct parts depends on whether the number of parts is even or odd Namely if the number of parts is even then the contribution is 1 and if the number of parts is odd the contribution is 71 In particular it is not hard to see that H 1 Ii 2 EM 001 n21 n20 where is the number of partitions of n into an even number of distinct parts and 0n is the num ber of partitions of n into an odd number of distinct parts So to determine the product we need to deter mine 7 0n we will see that this value is 71 or 1 To do this we give a bijection between the num ber of partitions of n into an even number of distinct parts and the number of partitions of n into an odd number of distinct parts This is done by taking the Ferrer s diagram of a partition into distinct parts and comparing the size of the smallest part call it 4 and the size of the largest 45 run in the upper left corner call it T 1f 4 gt T then take the points from the 45 run and make it into a new part 1f 4 2 T then take the smallest part and put it in at the end as the 45 runi An example of what this is doing is shown belowi 1n the partition on the left we take the smallest part and put it at the end of the rst few rows while in the partition on the right we take the small 45 run at the end of the rst few rows and turn it into the smallest part 000 000000 a oooooooy 000 000000 on m E In particular this gives an involution between par titions of n into an odd number of distinct parts and partitions of n into an even number of distinct parts All that remains is to nd the xed points of the in volution namely those partitions into distinct parts where this operation failsi It is not too hard to see that the only way that this can fail is if we have one of the two following types of partitions 1n the one on the left we have 4 T but we cannot move 4 down to the 45 line because of the overlap 1n the one on the right we have 4 lt T but if we take the points on the 45 line it will create a partition which does not have distinct parts Counting these exceptional cases are partitions of size 3139 i j 2 1 Putting all of this together along with a little bit of playing with terms explains the form of the product This is known as Eulerls pentagonal theorem be cause the numbers that come up in the powers with nonzero coefficients are pentagonal numbers which can be formed by stacking a square on top of a tri angle 1 The pentagonal theorem has a nice application which is useful for quickly generating the number of partitions of n We have 1001 10011pn2Pn5710n7 where the terms on the right hand side are those from the pentagonal theoremi This follows by noting that 1 g xmo ltpnzngtlt Z 1jz312jgt2gt fooltjltoltgt Now using the rule for multiplying functions together and comparing coef cients on the left and right hand sides we see that for n 2 1 that 0 100170ni1Pn2pn5pni7 7 rearranging now gives the desired result We now return to generating functions The type of generating functions that we have encountered are what are called ordinary generating functions which are useful in problems involving combinations But there is another class of generating functions known as exponential generating functions which are useful in problems involving arrangements T eof eneratin yp g g form used to count nctlon ordinary E anxn combinations n20 In exponential E anj arrangements no n20 The term exponential comes from the fact that if a1 a2 1 then the resulting function 1s In 24761 n21 no A typical problem involving combinations looks at counting the number of nonnegative solutions to an equation of the form n1n2quot39nkn where we have restrictions on the nil In particular for each solution that we nd we add 1 to the count for the number of combinations For arrangements we start with the same basic problem namely we must rst choose what to arrange so we have to have a non negative solution to an equation similar to the form n1n2quot39nkn where again we have restriction on the nil But now after we have chosen our terms we still need to arrange or order themi From a previous lecture if we have n1 objects of type 1 n2 objects of type 2 and so on then the number of ways to arrange them is nl nllngl nkl7 0 now for each solution to n1 n2 nk n this is what will be contributed to the count for the number of arrangements The exponential function is perfectly set up to count the number of exponential functions To see this consider lt2ltggtltg gt where S is the possible values for nil Then a typical product will be of the form x 1 x 2 x n11 7121 nkl if n1n2 nk n then the contribution to xnnl 1s nl x 711an1 vigil the number of arrangements just like we wanted Let us look at two related problems to compare the differences of the two types of generating functions Example Find a generating function which counts the number of ways to pick n digits from 0s 1s and 2s so that there is at least one 0 chosen and an odd number of 1s Solution Using techniques from previous lectures we have that the ordinary generating function is xx2x3 xx3x5 1xx2 x x 1 x2 17x17x217x 17x31x Example Find a generating function which counts the number of ternary sequences sequences formed using the digits 0 1 and 2 of length n with at least one 0 and an odd number of 1s Solution This problem is related to the previous except that after we pick out which digits we will be using we still need to arrange the digits So we will use an exponential generating function to count thesei In our case we have 12 IS IS 15 12 z z 1z x7 7x exi17e 26 exe37e27e71i Note that the approach is nearly identical for both problems the only difference in the initial setup for the generating functions is the introduction of the fac torial terms So the same techniques and skills that we learned in setting up problems before still holds The only real trick is to decide when to use an expo nential generating function and when not to use it In the end it boils down for now to whether or not we need to account for ordering in what we choose If we don7t then go with an ordinary generating function if we do go with an exponential generating function Lecture 10 7 April 20 In the last lecture we saw how to set up an expo nential generating function to solve an arrangement problemi As with ordinary generating functions if we want to use exponential generating functions we need to be able to nd coefficients of the functions that we set up To do this we list some identitiesi 7 i 16016 ip 160 kl e e x2 x4 x6 T 71 IHJWH ex7e x3 x5 x7 T I E 39 k 2 3 n71 kzni i i n7 Example Find the number of ternary sequences se quences formed using the digits 0 1 and 2 of length n with at least one 0 and an odd number of 1s Solution From last time we know that the exponen tial generating function gx which counts the number of ternary sequences is 1 gltzgt E7207671 1 x x x lt23ng722ng7zg71gt n20 n20 n20 1 n 273ni2 71ii 2 nl ngt1 So reading off the coefficient of xnnl we have that the number of such solutions is 3 7 2 7 12 for n 2 1 and 0 for n 0 Example Find the exponential generating function where the nth coefficient counts the number of n letter words which can be formed using letters from the word BOOKKEEPER K Solution We will use an exponential generating func tion since we are interested in counting the number of words and the arrangement of letters in words gives different words Since order is important we will go with an exponential generating function We group by letters There are 3 Es 2 Ks and Os and 1 B P and R So putting this together the desired exponential gen erating function is x2 x3 x22 3 fltzgt 7 1I l11 l 11 x2 x3 x4 x5 1 6x 33 1665 7581 31005 16 I7 18 11130a 34020W 84000g I9 110 151200a 151200 i The last step is done by multiplying the polynomial out letting the computer do all of the heavy lifting So we can read off the coefficients and see for example that there are 34020 words of length 7 that can be formed using the letters from BOOKKEEPERi Example How many ways are there to place it dis tinct people into three different rooms with at least one person in each room Solution This does not look like an arrangement problem so we might not automatically think of using exponential generating functions However we preVi ously saw that the number of ways of arranging n1 objects of type 1 n2 objects of type 2 Hi and nk objects of type It is the same as the number of ways to distribute n distinct objects into k bins so that bin 1 gets n1 objects bin 2 gets n2 objects 1 i i and bin It gets nk objectsi So this problem is perfect for exponential generating functions In particular since there are three room we can set this up as n1 n2 n3 n where ni are the number people in room ii Since each room must have at least one person we have that ni 2 1 So the exponential generating function is 2 3 4 Mr z773 grills e3173e23e71 x x x n n 3 H P ZZ HHEH n20 n20 n20 Z 3 7 32 3pm n21 Reading off the coefficients we see that the answer to our question with it people is 3 7 22 3 In a later lecture we will see an alternative way to derive this expression using the principle of inclusionexclusion Lecture 11 7 April 24 1t frequently happens that we want to prove a state ment is true for n 12r r n For instance on the first day we saw that 1 12 forn21r We gave a proof for this using a method of counting a set of dots in two different ways However we could prove it in another way First let us prove it for n 11 Since 1 1112 the case n 1 is true Now let us assume that the statement is true for it ie we can assume it is true 1 2 n nn12 and consider the case n 11 We have n n 1 12nn1 n1 v oasoforn7n1ltg1gt 7W1 This shows that the case n 1 is also true Be tween these two statements this shows it is true for n 1 2 311 lrer we have shown it is true for n 1 then by the second part since it is true for n 1 it is true for n 2 then again by the second part since it is true for n 2 it is true for n 3 This is an example of mathematical induction which is a useful method of proving statements for n 12r H though we don7t have to start at 1 we can start at any value In general we need to prove two parts 11 The statement holds in the first case 21 Assuming the statement holds for the cases k S n show that the statement also hold for n 11 This is what is known as strong induction Usually it will suffice for us to only assume the previous case ie assume the case k n is true and then show n1 also holds which is known as weak induction The idea behind proof by induction is analogous to the idea of climbing a ladder We first need to get on the ladder prove the first case and then we need to be able to move from one rung of the ladder to the next show that if one case is true then the next case is true It is important that you remember to prove the first case The most important thing about an induction proof is to see how to relate the previous cases to the cur rent caser Often once that is understood the rest of the proof is very straightforward Example Prove for n 2 1 712 22 7 32 71 n2 7 71 wr Solution We first prove the case n 11 Since 1 1 1 712 111I the first case holdsr Now we assume the case corre sponding to n is true and now we want to prove the case corresponding to n1 is true That is we assume 1 712 22 7 32 71 n2 7 71 r and we want to show 712 7 22 7 32 7 I I I 7 70an 7 71n1n12 1n 2 71 n1n I ltgt 7777 So let us begin we have 712 22 7 32 I I I7I7 71nn271n1n12 x Case corresponding to n ew awww 71 1n 1 lt 7 g n 1 n 1ltn1n2 71 2 r Example Prove for n 2 1 n 1 1 4mm 3 f 1 B 23 Solution We first prove the case n 11 Since 1 7 1 7 1 E 7 2 7 m the first case holdsr Now we assume the case corre sponding to n is true and now we want to prove the case corresponding to n1 is true That is we assume 1 1 1 7 n lllmi and we want to show 1 1 1 1 7 n1 39 nn1MnM2 717 So let us begin we have 1 1 1 1 m nn1 n1n2 case corresponding to n n 1 7 nn 2 1 71 1n2 M 1n2 12 n 1 n1n2 W We now turn to recurrence relations A recurrence relation sometimes also referred to as a recursion rela tion is a sequence of numbers where an sometimes written an the nth number can be expressed using previous ak for k lt n Examples of recurrence rela tions include the following 0 an 3an1 2an2 7 an73i This is an example of a constant coef cient homogeneous linear re currencei We will examine these in more detail in a later lecturer 0 an 2an1 n21 This is an example of a non homogeneous recursioni We will also examine these in some special cases in a later lecturer o an1 aoana1an1 anaoi This is related to the idea of convolution in analysis It shows up frequently in combinatorial problems in particu lar the Catalan numbers can be found using this method amk an1 161 an71ki This is an example of a multivariable recurrencei That is we have that the number that we are interested in nding has two parameters instead of one We have seen this particular recurrence before namely n n 7 1 n 7 1 kHHH k 1 We are often interested in solving a recurrence which is to nd an expression for an that is independent of the previous aki In other words we want to nd some function so that an In order for us to do this we need one more thing that is initial conditions These initial conditions are used to prime the pump77 and get the recursion startedi Example The Tower of Hanoi77 puzzle relates to a problem of moving a stack of n differently sized discs on one pole to another pole see the following picture There are two rules 1 only one disc at a time can be moved 2 at no time can a larger disc be placed over a smaller disci Find a recursion for Tn the minimal number of moves needed to move n discs Solution Experimenting we note that T1 1 ie move the disc and we are done T2 3 ie move the small disc to the center pole move the large disc to the end pole and then move the small disc back We can keep this going but now let us step back As we are moving discs we must at some point move the bottom disc from the left pole to the right polei We can use this to break the operation of moving all the discs into several steps as outlined belowi L11 ll 11771 moves ll 1 move 1 ll 11771 moves So combining we have Tn Tn71 1 Tn71 2Tn71 1 We have now found a recursion for Tni Using this along with the rst two cases we did by hand we have the following values for Tni n11 2 3 4 5 6 7 8 9 10 Tnl13 715 3163127 255 5111023 Staring at the Tn they look a little familiari In particu lar they are very close to the numbers 2 4 816 32 i H which are the powers of 2 So we can guess that T n 7 1 n This right now is a guess To show that the guess is correct we need to do the following two things 0 Show that the initial conditions are satis ed 0 Show that the recurrence relationships is satis ed If this reminds you of induction you are right Show ing the initial conditions is satis ed establishes the base case and showing that the recurrence relationship is satis ed shows that if it is true to a certain case then the next case is also true So we now check Our initial condition is that T1 1 and since 21 71 1 our initial condition is satis ed Now we check that Tn 2 7 1 satis es the recurrence Tn 2Tn1 11 We have 2Tn11 22 1711 2ni21 27171 Tn showing that the recurrence relationship is satis ed This establishes that Tn 2 7 1 This is good news since legend has it that there is a group of monks work ing on a copy of the Tower of Hanoi puzzle with 64 golden discs when they are the done the world will end We now know that it will take them 2544 18446744073709551615 Inoveg so the world is in no danger of ending soonl A very famous recursion is the one related to Fi bonacci numbersi This recursion traces back to a prob lem about rabbit population in Lille Abaci one of the rst mathematical textbooks about arithmetic writ ten in 1202 by Leonardo de Pisa also known as Fi bonacci1 The numbers are de ned by F0 0 F1 1 and Fn2 Fn1 Fn ie to nd the next num ber add the two most recent numbers The rst few Fibonacci numbers are listed belowi Note the book de nes the Fibonacci numbers by letting F0 F1 1 this is the same set of numbers but the index is shifted by 1 the de nition we have given here is the more commonly accepted versioni n10 P 0 78910 13213455 We will study these numbers in some detail and nd some simple expressions for calculating the nth Fi bonacci number in later lectures The Fibonacci num bers are one of the most studied numbers in mathe matics they even have their own journal dedicated to studying them This is in part because they arise in many different interpretations Example Count the number of binary sequences with no consecutive Osi Solution Let an be the number of binary sequences of length n with no consecutive Osi Calculating the rst few cases we see the following n admissible 1011 1101 1110 1111 The sequence an looks like Fibonacci numbers in particular it looks like an Fn11 But we still have to prove that Let us turn to nding a recursion for the an1 We can group the sequences without consecutive 0s of length n into two groups The rst group will be those that have a 1 at the end and the second group will have a 0 at the end In the rst group the rst n 7 1 terms is any sequence of length n 7 1 without consecutive Us In the second group if the last term is 0 then we must have that the second to last term be 1 so the rst n 7 2 terms is any sequence of length n 7 2 without consecutive Us In particular we have the following two groups 1 and 10 v length n 7 1 length n 7 2 an71 such M72 such So by the rule of addition it follows that an an 71 an 7 2 This is the same recurrence as the Fibonacci num bers so we have that the number of such sequences are counted by the Fibonacci numbersl Example A composition is an ordered partition so for example the compositions of 4 are 111L11z12h21h2z133L4 Count the number of compositions of n with all parts oddi Solution Let bn be the number of compositions of n with all parts oddi Calculating the rst few cases we see the following n admissible 13L31L5 Again the sequence looks like Fibonacci numbers and in particular it looks like bn n1 Again we still have to prove it After all it is possible that something looks true for the rst few billion cases but eventually is false We can group compositions according to the size of the last part There are two cases if n is odd the last part can be any of n n7 2 n7 411111 On the other hand if n is odd the last part can be any of n7 1 n73 11 1 11 In particular it is not dif cult to see b 7 1bn71bn73 ifnodd mi bn71bn73 ifneveni The bn71 term is when the last part is 1 the bn73 is when the last part is 3 and so on The 1 term for the case n odd corresponds to the composition This doesn7t look like the recurrence for the Fi bonacci numbers at alll But perhaps we can massage this recurrence and get the Fibonacci recurrence to pop out In particular we note that for the case it odd we bn1bn71bn73bn75 bn711bn73bn75 T bn71bn72i For the case it even we have bn bn71bn73bn75 bn71 bn73bn75 bn72 bn 71 bn7 2 In particular we see that bn bn 7 1 bn 7 2 so the sequence bn does satisfy the same recurrence property as the Fibonacci numbers and so we have that the bn are the Fibonacci numbersi Lecture 12 7 April 27 Example Find the number of compositions of n with no part equal to 1 Solution Let dn denote the number of such com positions for n Then for the rst few cases we have n admissible Looking at the numbers 011 2 3 5 these look famil iar they look like Fibonacci numbersi Again Havenlt we seen them enough No you can never see enough Fibonacci numbers So now let us turn to making a recursion for We can group compositions of it according to the size of the last part Namely the size of the last part can be 2 3i i i n72 n we cannot have the last part be size 1 since we are not allowed parts of 1 for the same reason we cannot have a part of size n71 since the other part would be 1 If the last part is k then we have that the rest of the composition would be some composition of n 7 k with no part of size 1 In particular it follows that dndn72dn73dn74d21 dn71 in particular if we group all but the rst term what we have is dn 7 1 an dn dn 7 2 dn 71 The same recursion for the Fibonacci numbersi Since we start with Fibonacci numbers and the same recur rence is satis ed it follows that dn Fn71 ie the number of such compositions is counted by the Fibonacci numbers with the index shifted by 1 We now want to look at some important numbers that arise in combinatoricsi We look at them now since they can be described using multivariable recurrencesi The Stirling numbers of the second kind denoted 2 counts the number of ways to partition the set 2Hin into k disjoint nonempty subsets ie each element is in one and only one subseti For ex ample we have the following n k possible partitions Z n4 l 2 3 4 1 22 123u4 124u3 7 134U2 1U234 12U34 13U24 14 U 23 1U2U34 1U273U4 6 1u24u3 12U3U4 13 u 2 u4 14 U 2 U 3 1U2U3u4 1 The rst few values of are shown in the follow ing ta ei gm 2 2 z 2 2 n 1 n 1 1 n3 1 3 1 n4 1 7 6 1 n 1 15 25 10 1 n 1 31 90 65 15 1 Looking at this table we see a few patterns pop out 0 71L 1 This is obVious since the only way to break a set into one subset is to take the whole set 0 1i Th1s 1s also obV1ous s1nce the only way it to break a set with n elements into n subsets is to have each element of the set in a subset by itself 7 n71 o 2 2 7 1 To see th1s note that 1f we break our set into two sets then it has the form of A U A ie A and its complement We may as sume that 1 is in A1 or each remaining element it is either in A or not the only condition is that they cannot all be in A else A 0 so there are 2 1 7 1 ways to ll in the remainder of 1 n n 1 Z 1 This can be seen by noting that there is one subset with two elements with two elements and the remaining subsets are singletons iiei subsets of size one So the number of such partitions is the same as the number of ways to pick the elements in the subset with two elements which can be done in waysi On a side note the row sums of this table are 12151552 11 these are also important numbers known as the Bell numbers We now turn to the recursion for the Stirling num bers of the second kind n n 7 1 k n 7 1 kHthl 4 Note that this is similar to the recursion for bino mial coef cients The only difference being the addi tional factor of In To verify the recurrence we break the partitions of 12111n into two groups In the rst group are partitions with the set and in the second group are partitions without the set 1n the rst group we have n in a set by itself and we need to partition the remaining n7 1 elements into k 7 1 sets which can be done in ways In the second group we rst form It sets using the rst n 7 1 elements which can be done in ways we now need to add n into one of the sets since there are n sets and we can put them into any one of them the number in this group is kn11 The Stirling numbers of the second kind arise in many applications even more than the Stirling num bers of the rst kind As an example consider the following Example Show that the number of ways to place n7 k nonattacking rooks below the diagonal of an n X n is n k 1 Solution Since we know that counts the num ber of partitions of 1 21 11 n one method is to give a onetoone correspondence between the rook place ments and the set partitionsi We will describe the positions of the chessboard as coordinates ij with i ltj1 So suppose that 12111n41u42uu4k is a partitioning and suppose that Ai a1a2111ami with al lt a lt lt ammi Then place rooks at the coordinates ahag a2 a3 1 1 1 muggt71 ami1 For each set we will place 71 rooks so altogether we will p ace k 7 1 n7 k rooksi i1 Further note that by this convention at most one rook will go in each row and in each column so that the rooks are nonattacking Conversely given a non attacking rook placement we can reconstruct the par titioni Namely if there is a rook at position p 4 then put p and 4 into the same subset of the partition It is easy to see that each placement of rooks corresponds to a partition and each partition corresponds to a place ment of rooks giving us the desired correspondencei The best way to see this is to work through a few examples We will illustrate one here and encourage the reader to make up their own So suppose that our partition is 1 3 5 u 2 u 4 7 s u 69 Then the corresponding rook placement is shown be lowi We also have Stirling numbers of the rst kind de noted These count the number of permutations in the symmetric group Sn that have It cyclesi Equiv alently this is the number of ways to sit n people at k circular tables so that no table is empty If we let abc denote a table with persons a b and c seated in clockwise order note that abc boa cab but abc acb then we have the following n k possible seatings 1 1234 1243 1324 6 1342 1423 1432 7 1234 1243 2134 11 2043 3024 3042 4023 4032 1234 1324 1423 2 lt1gtlt2gtlt34gt lt1gtlt3gtlt24gt lt1gtlt4gtlt23gt 6 i4 lt12gtlt3gtlt4gt lt13gtlt2gtlt4gt lt14gtlt2gtlt3gt 7 lt1gtlt2gtlt3gtlt4gt 1 The rst few values of are shown in the following m m 2 m m m n1 1 n2 1 1 n3 2 3 1 n4 6 11 6 1 n5 24 50 35 10 1 n6 120 274 225 85 15 1 Looking at this table we again see a few patterns pop out n o 1 n 7 1li This is obvious since everyone is sitting at one table Fix the rst person then there are n 7 1 possible people to seat in the next seat n 7 2 in the following seat and so on n o J 1 This is obvious since the only way that n this can happen is if everyone is at a private tablei n n o 1 As before one table will have a n 7 pair of people sitting and the rest will have one person eachi We only need to pick the two people who will be sitting at the table together which can be done in waysi Looking at the the row sums of this table we have 12624 120 720 which are the factorial num bers This is easy to see once we note that there is a onetoone correspondence between permutations and these seatingsi Essentially the idea here is that we are re ning our count by grouping permutations according to the number of cycles We now turn to the recursion for the Stirling num bers of the rst kind n n 7 1 n 7 1 l M lml n 1gtl k l l Again we note the similarity to the recursion for the binomial coef cients as well as the Stirling numbers of the second kind Of course a small change can lead to very different behavior To verify the recurrence we break the seating ar rangements into two groups In the rst group we consider the case where n sits at a table by themselves and in the second group n sits at a table with other people In the rst group since n is at a table by them selves this leaves n 7 1 people to ll in the other k 7 1 tables which can be done in ways In the second group rst we seat everyone besides n at k tables this can be done in ways now we let n sit down since n can sit to the left of any person there are n 71 places that they could sit and so the total number of arrangements in this group is n 7 1 Lecture 13 7 April 29 Previously we saw that if we can guess the solution to a recurrence problem then we can prove that it is correct by verifying the guess satis es the initial con ditions and satis es the recurrence relationi But this assumes we can guess the solution which is not easy For instance what is a way to express the Fibonacci numbers without using the recursion de nition We now turn to systematically nding solutions to some recurrences In this lecture we limit ourselves to solving homo geneous constant coe cient linear recursions of order kl This is a mouthful of adjectives with this many as sumptions we should be able to solve these recurrencesl Recursions of this type have the following form an Clan71 52an72 51604717167 where the 5152 1 r 1516 are constants hence the term constant coef cient That we only look back in the previous k terms to determine the next term explains the order k that we are using linear combinations of the previous k terms explains the linear h Finally homogeneous77 tells us that there is nothing else be sides the linear combination of the previous k terms an example of something which is not homogeneous would be an Clan71 52an72 Ckan7k fn7 where is some nonzero function depending on n Our method and even the language that we use in solving these linear recurrences is similar to the ap proach in solving differential equations So for example when we had a homogeneous constant coef cient linear differential equation of order k we would try to nd solutions of the form y e and determine which val ues of r are possible Are approach will be the same we will try to nd solutions of the form an r and determine which values of r are possible Putting this into the equation we get r clrni1 Cgrni2 ckrn ki Dividing both sides of this equation by the smallest power of r in this case rn k this becomes rk on cw Ck or rk 7 clrlk 1 7 Cgrk 2 7 7 ck 0 Because the c s are constants this last expression does not depend on n but is a kth degree polynomiali So we can nd the roots of this polynomial at least in theoryl and the roots are the possible values of 7 1 So suppose that we have the roots 7 17 2 1 1 1 Tk for now we will assume that they are all distinct We now have k different solutions and so we can combine them together in a linear combination hence the important reason that we assumed linear1 So that some solutions are of the form an D1T Dy Der where D1D211 1Dk are constants Now let us back to the original problemi Equation tells us that we look at the previous k terms to determine the next termi So in order for the recursion to get started we need to have at least k initial terms the initial condi tions In other words we have k degrees of freedom and conveniently enough we have k constants avail able So using the k initial conditions we can solve for the k constants D1 D2111 Dki In fact every solution to this type of recurrence must be of this type We still need to determine what to do when there are repeated roots we will address this in the next lecturei Example Solve the recurrence relationship a0 4 a1 11 an an 2on71 San2 or n 2 1 Solution First we translate the recurrence relation ship into a polynomial in 7 1 Since it is a second order recurrence this will become a quadratic namely 7 2 2T3 or 07 2727 73 7 737 11 So that the roots are 7 7131 So that the general solutions are an C71 D3 The initial conditions translate into 4 a0 C D 11 a1 7C3D1 Adding these together we have 15 4D or D 154 substituting this into the rst equation we have C 4 7 154 141 So our solution to the recurrence is 1 15 n 7 71 n 73711 a 4 l 4 Example Recall that the Fibonacci numbers are de ned by F0 0 F1 1 and Fn2 Fn1 Fn for n 2 01 Find an expression for the nth Fibonacci num beri Solution First we translate the recurrence relation ship into a polynoial in 7 1 This is again a second order recurrence so it becomes a quadratic namely 7 27 1 or 7 277 7101 Since it is not obvious how to factor we plug this into the quadratic formula TiumB T So the general solution to this recursion is n n 11 We now plug the initial conditions to solve for C and D1 We have 0F0 CD E E 2 2 The rst equation show that C 7D putting this into the second equation we can now solve for C and D namely C 15 and D 7151 Substituting these in we have 1lt1 3gt 1143 7 2 3 2 CD 07D 07D This seems very unusual the Fibonacci numbers are whole numbers and so don7t have any 5 terms in them but the above expression is rife with themi So we should check our solution One way is to plug it into the recurrence and verify that this works but that can take some time A quick way to check is to plug in the next term and verify that we get the correct answer For example by the recursion we have that F2 1 but plugging n 2 in the above expression we have 1 1 J3 2 1 1 7 3 2 A 2 gt A 2 gt 1235 172 5 4J3 1 NE 4J3 4J3 Notice the 5 terms all cancel out so that we are left with whole numbers The number that shows up in 1g2 is called the golden ratio denoted by This number is one of the most celebrated constants in mathematics and dates back to the ancient Greeks who believed that the best looking rectangle would be one that is similar to a 1 X 45 rectanglei The idea being that in such a rectangle if we cut off a 1 X 1 square the leftover piece is similar to what we started with However experimental studies indicate that when asked to choose from a large group of rectangles that people tend not to go with the ones proportional to 1 X So perhaps the Greeks were wrong about that Finally let us make one more observation about the Fibonacci numbers e ave 1 x3 2 1 7 x3 2 1 618033988 i H 70618033988 H In particular since l1 7 lt 1 when we take high powers of this term we have that this becomes very small From this we have that the second term in the above expression for Fn is smaller than 12 for all values of n 2 0 and so 1 1 5 Fn nearest integer to 7 i 1 V3 2 So that the rate of growth of the Fibonacci numbers is 1 Example Solve the recurrence 9 29771 7 297 with the initial conditions go 1 and 91 1 Solution We again translate this into a polynomial in Ti This becomes the quadratic T22T72 or T272T20i Putting this into the quadratic formula we nd that the roots are 2 i 4 7 8 7 1 i ii 2 Now we have complex rootsl So we might pause and think how do we change our approach The answer is not at all the exact same techniques work whether the roots are real or complex So now the general solution is 9 C1z D172 i Putting in the initial conditions this translates into 1 go CDi 491 C1iD17i CDiC7D 1z CiDi This gives C D 1 and C 7 D 732quot Adding together and dividing by 2 we have C 1 7 3i2 while taking the difference and dividing by 2 we have D 1 3i2i So our solution is 9n lt13igt1in 13170 It should be noted that C and D are complex conju gates This must happen in order to have the expres sion for 9 to be real values which must be true by the recurrence Lecture 14 7 May 1 As mentioned in the last lecture solving recurrences is very similar to solving differential equations Many of the same techniques that worked for differential equations will work for recurrences As an example when solving the differential equation y 7 2y y 0 we would turn this into a polynomial 7 2 7T1 0 and get the roots 7 1 1 we would then translate this into the general solution y Ce Dre the extra factor of 1 comes from the fact that we have a double root ie we could not use Ce De C De C e as this does not have enough freedom for giving general solutions to the differential equation For recurrences we will have essentially the same thing occuri Suppose that we are working with the recurrence an 51047171 52047172 51604717167 then for nding the general solution we would look at the roots of Tk 7 clrkil 7 Cgrk 2 7 7 ck 0 Suppose that p is a root of multiplicity Z then the general solution has the form an Dl n DWI7n DSnQPn 39 39 39 Dalia7n where the corresponds to the contribution of any other roots Notice that we have multiplicity Z and that we have Z constants just the right amount this should always happen Example Let a0 11 a1 6 and an 4an174an2 for b 2 2i Solve the recurrence for uni Solution We rst translate the recurrence into the polynomial 7 2 7 47 4 0 which has a double root of 2 So the general solution will be of the form an C2 Dn2ni To solve for C and D we use our initial conditions We have a0 C 11 and a1 2C 2D 6 from which we can deduce that D 78 So the solution is an 112 7 8n2ni Example Solve the recurrence bn 312n 71 7 312n 7 2 bn 7 3 with initial conditions b02 121 7 1 and b23i Solution We rst translate the recurrence into the polynomial 0r373T23T71T713 which has a triple root of 1 So the general solution will be of the form bn C1 Dn1n En21n C Dn Ean To solve for the constants we use our initial conditions ave 2 a0 C 71 a1 CDE 3 a2 C2D4El From the rst equation we have C 2 Putting this in we have D E 73 and 2D 4E 1 Solving these we get D 7132 and E 72 So our solution is bn277n nl 13 7 2 2 We can occasionally take a recurrence problem which is not a constant coef cient homogeneous lin ear recurrence of order k and rewrite it so that it is of the form thus allowing us to use the techniques that we have discussed so far to solve Example Let do 1 and ndn 3dn71l Solve for dnl Solution This does not have constant coef cients so our current techniques do not work One method to solve this is to start listing the rst few terms and look for a pattern in this case it is not hard to nd the pattern lnstead let us do something that at rst blush seems to make things worse let us take the recurrence and multiply both sides by n 7 1 giving n 71lndn nldn 3n 71ldn1l Now let us make a quick substitution namely let us set on nldnl Then the above recurrence becomes an Scn1 which has the solution on nldn E3 which shows that the general solution is an ES Lnll Our initial condition then shows that 1 do E so that our desired solution is an 3nnll The trick in the last example was to nd a way to substitute to rewrite the recurrence as one that we have already done This allowed us to take a re currence which did not have constant coef cients and treat it like one that did This same technique can also take some recurrences which are not linear and reduce it to ones which are linear Example Find the solution to the recurrence with a01a22and an 2 an1 an72an1 7 an72 for n 2 2 Solution We start by rewriting this recurrence note that for the term inside the square root it is of the form a b a 7 b which we can replace by a2 7 b2 doing this and squaring both sides we have 2 7 2 2 an 7 4an71 7 4an72l There is an obvious substitution to make namely 12 a3 which relates this problem to the recurrence bn 4117171 4117727 with initial conditions 120 a3 1 and b1 a 4 As we saw in a previous example this has the general solution 12 C2 Dn2nl It is easy to see that the initial conditions translate into C 1 and D 1 So we have a3 12 2 712 n12 1 Taking square roots and seeing that we want to go with the 77 square root to match our initial condi tions we have an n12nl Example Solve for 9 where 91 1 92 2 and 974 W forn22l 9n Example This is highly nonlinear The problem is that we have division and then we also have things be ing raised to powersl We would like to translate this into something similar to what we have already done Thinking back over our repertoire we recall that loga rithms turn division into subtraction and also allow us to bring powers down So let us take the logarithm of both sides We could use any base that we want but let us go with log2 log base 2 Then we have 3 10g2 an 2 logg gn71 7 1 logg 97172 If we let hn log2 9 then our problem translates into 3 hn 2hn71 1hn72 with initial conditions he log2 go 0 and hl log291 1 our choice of base 2 was made precisely so that these initial conditions would be clean To solve this recurrence we rst translate this into the polynomia 0T22T T77Tquot so that our roots are 7 1132 So the general solution for hn is 1 2 3 n hn C 7 D 7 i lt2 2 Our initial conditions give us 0 C D and 1 12C 32D or 2 C SDi It is easy to solve and nd C 71 and D 11 So we now have 1 3 3n 7 1 IOgQQnhn n n 27 A So now solving for 9 we have 9n gang23 Finally let us look at how to deal with a recurrence relation which is nonhomogeneous ie a recurrence relation of the formi an Clan71 52an72 Ckanik fn ln differential equations there are several techniques to deal with this situation We will be interested in look ing at the technique known as the method of undeter mined coef cients or as I like to call it the method of good guessinglli This technique has de nite limita tions in that we need to assume that is of a very speci c form name y Zpolynomialp ie that looks like what is possible as a homoge neous solution This is the same principle when doing the method of undetermined coef cients in differential equations The outline of how to solve a nonhomogeneous equation is as follows 1 Solve the homogeneous part ie the recurrence without the E0 Solve the nonhomogeneous part by setting up a solution for an with some coef cients to be deter mined by the recurrence 9 Combine the above two part to get the general solution Solve for the constants using the initial conditions Note that the order of operations is important That is we need to solve for the homogeneous part before we can do the nonhomogeneous part and we need to solve both parts before we can use initial conditions The reason that we need to solve the homogenous part rst is that it can in uence how we solve the non homogeneous parti So now let us look at step 2 a little more closely So suppose that we have jth degree polynomial in np i We look at the homogeneous part and see if p is a root iiei part of the homogeneous solution If it is not a root then we guess that the nonhomogeneous solution will be of the form an Bjnj Bj71nj 1 30 where BjBv 1 B0 are constants which will be determined by putting this into the recursion group ing coef cients and then making sure each coef cient is zero See the examples below fp is a root then part of the above guess actually is in the homogeneous part and cannot contribute to the nonhomogeneous part In this case we need to gently nudge our solution To do this suppose that p occurs as a root m timesi Then we modify our guess for the nonhomogeneous solution so that it is now of the form an Bjnmj Bj1nmj 1 Bonmpni That is we multiply by a power of nm to push the terms outside of the homogeneous solution If has several parts added together we essen tially do each part seperately and combine them to getheri We now illustrate the approach with some examples Example Solve for 4 where qo 71 L11 1 and L1 qnig 3 for n 2 2 Solution The term 37 shows that this is a non homogeneous recurrence and further 3 is of the form that we can do something with So we rst solve the homogeneous part 4 4772 which turns into the polynomial 7 2 1 so that the roots are 7 ill So the homogeneous portion has the form 4 or DHn c DH Now neither of the roots are 3 and so we now set up the form for the nonhomogeneous parti Namely an E3 we now need to determine E To do this we substitute into the recursion This gives E3 E3 23n or E7 E 7 U3 0 The second part comes from moving everything to one side and collecting the coef cients In order for this last statement to hold ie in order for it to be a solution to the nonhomogeneous part we need to have that the coef cient is 0 This means that we need 89E71 0 so that we need to choose E 981 So the solution for the nonhomogeneous part is 9 4n ggnA Combining the two parts the general solution to this recurrence is 9 4n 0 D71n g3 We now take care of the initial conditions We have 9 71 qo CD g 1 4 1 C 7 D 2877 Rearranging this gives 7 7 0D 19 7 7 C7D Adding the two we get 2C 7368 792 so that C 794 taking the difference we get 2D 28 14 so that D 181 So our desired solution is 9 1 47777 9 if n in 48 1 831 Example Let a0 11 a1 8 and an 3an71 272 1n 271 Solve for uni Solution Again we have a nonhomogeneous equa tion and it is of the form that we can do something with So we rst solve the homogeneous part an San1 7 2angi This will translate into the polynomial 7 2 7 37 2 0 which factors as 7 7 2 7 7 1 0 So that the roots are 7 121 So the solution to the homogeneous part is an Cl D2 CD2ni We now turn to the nonhomogeneous portioni Since 71 is not a root of the homogeneous solution then that part of the solution will be of the form E71 i Unfortunately 2 is a root of the homogeneous solution with multiplicity one and so we will need to modify our guess so instead of FnG2 we will use Fn2 Gn2 i So our nonhomogeneous solution has the form an E71n Fn2 Gn2ni We now substitute this in and get E71 Fn2 Gn2 3E71 1 Fn 71 Cn 712 H 7 2E71 2 Fn 7 22 Cn 7 22 71 n2ni The next step is to expand and collect coef cients If we do this we get the following 0 7E73E72E171 SF 7 SC 7 2F G 7G73F G2F7 G1n2 7F F7 FMQZ Each of these coef cients must be zero in order for this to be a solution This leads us to the following system of equations note that the last coef cient is automatically zero and so we will drop it 1 6E 0 F G 1 F This is an easy system to solve Giving E 16 F 1 and G 71 so the solution to the nonhomogeneous part is 1 an 671 n2 7 n2 i So the general solutions is an 7 C 7 D2n 71n 7 n2 7 702 It remains to use the initial conditions to nd the con stants C and Di Plugging in the initial conditions we have 11a0 CD 1 8a1 C2D7g Giving CD 656 and C2D 4961 Subtracting the second from the rst we have that D 7166 783 and so C 816 2721 So our nal solution is 7 27 8 n 1 n 2 n an72 32 6 1 n n2i Using this formula we get a0 11 a1 8 a2 11 a3 40 a4 163 which is what the recurrence says we should get Wohool Lecture 15 7 May 4 We can use generating functions to help solve re currencesi The idea is that we are given a recurrence for an and we want to solve for uni This is done by letting 91 Z aux n20 we then translate the recurrence into a relationship for 91 which lets us solve for We nally take the function 91 and expand it to nd the coef cient for In Broken into steps we would do the following for a recurrence with initial conditions ao al 1 1 1 9161 and a recurrence an fnan1an2i 1 for n 2 kl 1 Write 91 Zan1ni n20 H E0 Break off the initial conditions and use the recur rence to replace the remaining terms iiei so we have 91 ao all ak711k 1 1 Z fn7an7170 n72 1 1 712k 9 Hard stepl rewrite the right hand side in terms of 91 andor other functions Usually done by shifting sums multiplying series and identifying common seriesi g 1 Now solve for 91 and then expand this into a series to read off the coef cient to get ani For example this can be done using general binomial theorem or partial fractions The best way to see this is through lots of examples E1ample Use a generating function to solve the re currence anan1 an721 with 901 and 912 Solution Following the procedure for nding 91 given above we have 91 2 971 n20 ao 911 2971 n22 1 21 2 9771 29772 11 ngt2 121 Z an11n2 Z an721n Z 1 n22 n22 n22 I 2 12119171 2129117Ii Before continuing we should see how the last step hap pened We have E an11 9112 9213 9313 n22 1al1ag12ag13 1917ao and similarly Z an721n a012 9113 213 n22 12a0 all 1212 1291 This can also be done by factoring out an 12 and then shifting the index Finally since 1 1 12 11 7 1 then 1 E1 1QE1 212 1 171 n22 n22 We now solve for 91 doing that we get the follow ing 12 1 171171 17172129111 Dividing we nally have the generating function IL 1 7 1 9 71 7 117 1 7 2x2 1 7 11 117 21 We now want to break this up which we can do using the techniques of partial fractions 1 A B C 7 7 71 171111721 171 11 1721 Clearing denominators this becomes 1 A111721B1711721C11171i We can now expand and collect the coef cient of pow ers of 1 and set up a system of equations which works great but before we do that let us observe that this must be true for all values of 11 So let us choose some nice values of 1 namely values where most of the terms drop out So for instance we have 1 1 1 becomes 1 72A giving A if 2 1 1 71 becomes 1 6B giving B E 1 3 4 1 E becomes 1 1C g1v1ng C The nal ingredient will be using 1222237 11 171 611 31721 2 i 1 g 2P1 g 2006 n20 n20 n20 7 1 1 n 4n n 72lt7 g71 2 n20 So we have that 7 1 1 n 4 an772671 32i Example Let ZFnzn where Fn are the n20 Fibonacci numbers F0 07 F 1 and Fn Fn1 Fn2 for n 2 2 Find a simple expression for Solution We proceed as before We have ZFnzn n20 F0 F11 Z Fn71 Fn72gt1n n22 z I Z Fn71zn 1 12 ZFn721n 2 n22 n22 So we have 171 7 z or 9017 1712 We can actually use this to nd an expression for the Fibonacci numbers similar to what we got pre viously To do this we will let 45 1 and lt15 1 7 then it can be checked that lt17 z 7 12gt lt17 zgtlt1 76111 We now have 7i1i 1717127174151 17 clearing denominators we have at A1 74131B1 7 tat AB 7 Altman We can conclude that A 73 and that 71AB B 743 733 so B 4N3 and A 1N3 giving fa 1 n7 7 Egan or substituting for 45 and 413 we get F 1 1 3 n 1 17 J3 n A 2 l A 2 l v as we have found previously To be careful we should point out that what we have done only makes sense if our function is analytic around some value of 1 near 0 In our case the nearest pole for the function is at z 45 so that near I 0 everything that we have done is ne We will not worry about such matters in our course7 but if you are interested in nding more about this topic read Analytic Combinatorics by Flajolet and Sedgewickl Example Let an be the number of regions that n lines divide the plane into Assume that no two lines are parallel and no three meet at a point Solve for an using generating functionsl Solution Let us start by looking at a few simple cases From the pictures below we see that no l7 a12a24anda37l In general when we draw in the nth line we start drawing it in from 007 every time we cross one of the n 7 1 lines we will create one additional region7 and then as we head to 00 we will create one last region So we have the recurrence an an71 717 with initial condition no 1 Checking we see that this gives the right answer for al a2 a3 and a4 which is good Now we have 91 Z anz n20 ao Z an71 701 n21 1 1 Z an71znil 2 n1 n21 n21 1 191 Z nznl ngt The hard part about this is the second part of the sumi To handle we start wit 1 1712In n20 Taking the derivative of both sides we get 1 n71 2 Em 7 1 z n20 almost what we want7 we just multiply by z to get I 7L 1 z n20 Note of course that it doesnlt matter whether we start our sum at 0 or 17 the result is the same So we have I 1 1 l W7 gltzgt71iI 1 1 1gt 7171 1712 1713 From when we started using generating functions we saw that 1 ltnk71gt n 7 17 171k n20 n and so we have 91 EH7 n20 n20 7 2 1 2 lt17 n1 n2 gtzn n20 2 2 Z n n20 2 2 So we can conclude that an n T T 1 So far we have looked at examples that we could already solve using other methods Let us try an ex ample that we could not solve or at least would be very hard with our previous methods The following example is taken from the book generatingfunctionol ogyi Example A block fountain of coins is a arrangement of coins in rows such that each row of coins forms a single contiguous block and each coin in the second or higher row touches two coins below an example is shown below Let denote the number of block fountains with n coins in the bottom rowi Find the generating function for 1 Solution We let 1 corresponding to the empty con guration Clearly we have 1 and f2 2 The case 5 is shown belowi mamacgaa Our next step is to nd a recurrence The fountain block either consists only of the single bottom row one con guration or it has another fountain block stacked on top of the bottom rowi Suppose that the bottom row has length n and the second row has length j7 then the second row can go in any of n 7j positionsi Putting it altogether we have fn 71 2017 mm The 1 corresponds to the single row solution7 the sum corresponds to when we have multiple rows Note that whenj n the contribution will be 0 in the sum So we have 91 Z n n20 7 ND 7 Z 17 2m 7 jfjgtz n21 j1 1 21 Z lt n21 n21 I n 1 2 n21 11 The difficult step is determining what to do with 7 mm j1 1ltn 7 jfjgtz S looking at it the inside reminds us of aobn albn1 unbo iiei7 where we multiply two series together It is not too hard to check that n7 39 f 39 I glt lt J 1 1212313f1zf2z2f3zgn 1712gz71i So combining we have I 91117 gltzgt71 i7 171 171 Multiplying both sides by l 7 z2 and simplifying we have 1721 7 2 7 1 31z 1 2x or 91 1731I2i Lecture 16 Arhday 6 We now return to some good old fashioned countingi We will be looking at setsi We have a collection of elements and we will let M denote the univers of all possible elements for the problem that we are counting We will let A denote a subset of M lAl denote the number of elements in the set A and A MA denote the complement of A the set of all elements in M not in A Since every element is either in A or not in A we can conclude WWW Pictorially we have the following picture This is a simple example of a Venn diagram which gives a visual way to represent setsi We will look at Venn diagrams for 1 2 and 3 sets after that it gets more dif cult to draw Venn diagrams but not impos sibleli Example There are 35 students in the class If 15 students come to of ce hours then how many student s didn t come Solution The set M is the set of all students A the set of students who came to of ce hours so by the above formula we have EM7Wimm Not surprisingly there is not much interesting to do with only one set So now let us consider the situation when we have two set A and B The Venn diagram for this situation is shown belowi Notice that this picture implies the possibility that the sets intersecti We 0 this because we ant enn diagrams to be as general as possible so the actual intersection can be empty do not assume that sets always intersecti We let A U B denote the union of A and B where AUBzleAorzEB and A N B denote the intersection of A and B where A BzleAandz Bi de Morgan s laws MN MW AUB In words de Morgan7s laws says that the complement of the union is the intersection of the complements and that the complement of the intersection is the union of the complementsi To prove A N B A U B we show that they have the same elements z E A N B 42gt z A N B ltgt z A or z B 42gt z E A or z E B 42gt z e A U B The other half of the law is proved similarly Suppose that we wanted to count the number of el ements in lA U Bl a natural rst guess is lAl The problem is that we are double counting elements in the intersection of A and B so we need to correct this overcounting by subtracting out So we have lAUBl AHlBlilA Bl We can also count this by breaking A U B into three pieces namely A N F elements in A but not in B A B elements in A and in B and A N B elements not in A but in B So we also have lAUBl lA Fl A BHZ Bl We now turn to the three set case This is illustrated in the Venn diagram belowi Notice that we have split M into eight pieces which is what we should expect because we are either in or not in each of the three sets The eight pieces are A B C A B C A F C AOFOC A B C AOBOC Z F C Erwin The last set by de Morgan7s law is A N F N C A U B U C which are the points outside of the sets A B and Cl Similarly as with the two set case we may want to count the union of the sets and as before we have to be careful not to overcounti So we have lAUBUCllAllBllCl ilA BlilA ClileCHlAmBmOl Example At a local college there is a language pro gram which has the three languages Russian R Chi nese C and Java There are 34 students attend ing the Russian class 31 students taking the Chinese class 36 students taking the Java class 13 students taking both Russian and Chinese 9 students taking Russian and Java and 11 students taking Chinese and Java When this is reported to the dean they look at it and say Wait 1 also need to know how many stu dents are in all three77 How many students attend all three classes Solution Thinking of these as sets then we are looking for 1R N C N Jli Plugging in the information we have into the formula above we have 7334313671379711lR C Jl 68lRmC Jli So lR C Jl 5 ie there are 5 students taking all three classes Example How many n digit ternary sequences with at least one 0 one 1 and one 2 Solution Let us use sets to represent the situation Let A denote the set of sequences without 0 B denote the sequences without 1 and 0 denote the sequences without 2 We could alternatively let them denote the sets with the elements but this is more fun Phrased this way we are looking for ZnFndAuBum milAuBucl On the one hand we have lAl lBl lCl 2 since elements in these sets are formed only using two let tersi We also have lA Bl lA Cl lB Bl 1 since elements in these sets are formed only using one letter so they look like 000 0 111 1 and 222 2i Fi nally we have lA N B N Cl 0 since we don7t have any letters to form the sequencer Putting this altogether ave ManG S L 32 7310 3 732 Si It is always a good idea to check so let us try 0 plug ging it in we get 1 but that is not the right answer we should have gotten 0 there are no sequences of length 0 with at least one 0 one 1 and one 2 So where was our mistake Looking back over what we did we see that lA B Cl will be 1 when n 0 and 0 otherwise This is because the empty string the string with no letters has no 0 no 1 and no 2 and so is an element in lA B Cli So if we put this back in we see that we do get the correct answer So we have that the number of such ternary sequences is 3 732 3 ifn21 0 ifn0i What we have just done is a simple example of a more basic principle InclusionExclusion Principle Let A1A2HiAn Q Hi Then lAimAjmmfnl 1111 Zenlll l QM 1w A1 jEI Before we try to prove this we rst should work on trying to understand what this says We have 1 2 i i i n so what we are doing is summing over all nonempty subsets of What this is really doing is summing over all possible ways that we can intersect the sets Ail Where we either add or subtract based on how many sets we are intersecting For example for n 3 this corresponds to the following lAT Ainsl Wli lAll 7 Md 7 lAsl H V 11 12 1s lA1 A2llA1 AgllA2 Agl 112 113 12s ilAl Ag Agli I123 Since lAlUAQU UAnl lulilAlUAgUHUAn lulilE E WTA we automatically have the following variation of the inclusionexclusion principlei InclusionExclusion Principle U Let A1A2 i i i An Q Hi Then AluAgunuAnl Zenlll l i Igm 121 A1 jEI The proof of the inclusionexclusion principle is based on a binomial identity that we encountered ear lier namely gew 1 The way to do this is to go through every element in M and see how many times it gets counted on each side of the equation We have two cases to consider ifm0 ifmZ 1 o z E lAil Aig H fnl note that z is in none of the sets Ail On the left hand side this gets counted and so contributes 1 On the right hand side this gets counted when we look at the term VA and since it is in none of the Ai it will not get counted any other time so the total contribution is 1 o z lAil Aig Ainl now I is in some of the sets Ai let us suppose it is in m setsi On the left hand side this does not get counted and so contributes 0 On the right hand side this will get counted many times once for the VA then times for each subset it is in then times for each pair of subsets it is in then times for each triple of subsets it is in and so on In particular the contribution on the right hand side using signs 1ltigtlt21gtlt2gtc0 In both cases the left and right sides are equal for each element establishing the result Lecture 17 7 May 8 We now look at some applications of how to use the inclusionexclusion principlei A classic example is counting derangement A derangement can be thought of as a permutation a function 7r A with no xed point an i so that This is of ten rephrased as a hatcheck problem where it people go out to eat and check in their hats but when they leave the person in charge of giving back their hats has forgotten who goes with which hat and so gives them back randomly a derangement then corresponds to the situation where no person gets their own hat backi Example How many derangement on n elements are there Solution To use the inclusionexclusion principle we want to rst identify the sets Ail There are many possibilities but we keep in mind two criteria First we want to nd the intersection of the complement of the Air Second we want to nd sets which are easy to count when we look at their intersectionsi Given these two criteria we are led to Ai ith person gets their hat so that Ai denotes arrangements where Ai does not get their hat backi Since no one should get their hat back we want to look at the intersection of these sets So the number of derangements is lE E fnl M Z 71 l Aj Igm 13961 121 Going through these terms we have VA is the number of ways to distribute the hats which is nli Now let us consider a term of the form jeIAji This corre sponds to arrangements that are simultaneously sat isfying that elements in I get their hat back The remaining n ij can be distributed arbitrarilyi So we 3V6 A1 jeI lmportantly we see that the only thing that is im portant is the number of elements of I and not which n7 um elements they are If we now group the sum by the size of the index set we have Emiler m Tnl M Z 71 l 1 1 a 1w n 416 nl lk nklnl 7 g gt kgtlt gt M Then term shows up because there are ways to choose k out of 71 sets to intersect A1 jEI Note that the sum that shows up in the number of derangements looks familiar In particular since ex DOE 71k we have DOE ink e 1 7 kl kl 7 160 160 So the number of derangements is m nlei In fact it can be shown that the number of derangements is the integer nearest to nlei Using this we can conclude that the probability that if we collect hats from 71 people and redistribute them randomly that no one gets their hat back is W Va Example Suppose that there are 71 couples that go to a theatre and sit in a row with 271 chairs a How many ways can the couples sit down if each person sits next to the person they came with b How many ways can the couples sit down if no person sits next to the person they came with Solution For part a we think of pairing the couples together and then arrange the couples which can be done in 71 ways Now each couple sits down and we need to decide who sits on the left and who sits on the right which can be done in 2 ways per couple so in total there are 27171 ways for the couples to sit down For part b we use inclusionexclusioni If we let Ai seatings with ith couple together then what we are looking for is X1 X2 A7 just right for inclusionexclusioni The total number of ways to seat the 271 people is 2nli Now let us focus on a term of the from jeIAji This corresponds to the situation where the couples in I are sitting together and maybe some more as well To count this we now think of there as being lIl couples and 271 2m singles for us to arrange or combined 271 lIl people to arrange Once we are done arranging the order of the people we then again have to decide for each couple who sits on the left and who sits on the right So altogether we have that m A1 jEI 271 7 1 12 1 Again it is important that it is the number of elements in I and not which elements in I that matters So as in the last example if we group by the size of the index set we have Ail Aj annl law 2 71 l quotl 7 271 7 gawk 7 W216 gawk 271 7 1m Again the term shows up because there are ways to choose k of the 71 sets to intersect Also we can absorb the 271 term into the sum since this cor responds to the case i Unfortunately there does not seem to be any nice way to condense this formula but at least we have a way to count it Using a computer we see that A1 jEI to 0138241263360168422400m i V V W W 2 713 714 715 716 7 7 lt0 lt00 71171 Finally let us look at some more variations of the inclusionexclusion principle Variation of the InclusionExclusion P7inciple Let A1A2 i i i An Q U and let Bm z in exactly 712 of the Al Then lel 7 eminentw Isz 4 1396 The case B0 where we translate the empty intersec tion as the entire M gives us back the original form of the inclusionexclusion principlei Our method to prove this is similar as before namely to consider cases for individual elements in M and show that each elements contributes the same to both sides 0 z in fewer than 712 of the Air In this case z Bm so the contribution on the left is 0 while on the right it will not show up in any of the intersections and so its contribution is again i o z in exactly 712 of the Air In this case I 6 EM so the contribution on the left is 1 while on the right it will show up exactly once namely in the intersection of the 712 sets it lies in It cannot show up in any other term so the contribution on the right is 1 o z in T gt m of the Air In this case z Bm so the contribution on the left is 0 While on the right it will show up times in the intersection of m sets times in the intersection of ml sets r m1 7712 times in the intersection of m 2 sets i H In particular the contribution on the right hand 81 33 lt gtltm11gt lt22 ltm2gtltm2gt Digging back to when we practiced identities for binomial coefficients we nd the identity Ggt So applying this to our situation we have MM fgt In particular we can rewrite our sum where we use this identity on every term and factor out the now common to get that the contribution on the right is T T 7 m T 7 m T 7 m m 0 1 2 which by the same reasoning as last time is 0 Closely related to this we have the following VaTz39atz39oTL 0f the InclusionExclusion PTz39Tch39ple U Let A1A2 i An Q U and let Cm z in at least m of the Ai Then 7 lIl7m l1l71 V le ICElt 1 m1 mini 16 The case m 1 corresponds to the variation that we gave in the last lecturer We will not give the proof here This brings us to the end of the enumerative com binatorics part of the course Starting with the next lecture we turn to graph theory Lecture 18 7 May 11 We now start a new area of combinatorics namely graph theory Graphs are at a basic level a set of ob jects and connections between themi As such they can be used to model all sorts of real world and mathemat ical objects We start with some of the basic properties of graphs A gmph G consists of two sets a vertex set V and an edge set E we sometimes will write this as G The vertex set represents our objects and the edge set represents our connections between objects we will visually denote vertices by 077 The edge set can have several different ways of describing how we connect vertices which leads to different types of graphs The most common are 0 The set E consists of unordered pairs of vertices iiei uvi These graphs are the most studied and are known as undiTected gTaphsi Visually we represent the edges as 77 The set E consists of an ordered list of two ver tices iiei u 1 These graphs are known as di Tected gTaphsi Visually we represent the edges as c 77 o The set E consists of subsets of vertices usually of some xed size ie v1 v2 i i 11k These graphs are known as hypeTgTaphsi These are hard to rep resent visually perhaps this is one of the reasons that we do not study them as much in beginning combinatoric coursesi Usually when we think of a graph we do not think of two sets but rather as a visual drawing of points and lines connecting the points This is great for building intuition but can also be deceiving in that the same graph can be drawn in many different ways we will look at this problem shortlyi Another problem is that many graphs that are interesting have a laTge number of vertices in the billions so that if we were to draw them as points and lines the end result would be a black piece of paper So it is good to be able to not have to rely on pictures An example of an undirected graph is a handshake graph which corresponds to a party with several peo ple present and we connect an edge between two people if they shake hands As a graph the vertices are the people and the edges correspond to handshakesi Be cause there is symmetry in the relationship ie if I shake your hand you also shake mine the undirected graph is the appropriate one to use These also can be used to model social networks in addition they are fre quently used to model groups these graphs are known as Cayley graphsi An example of a directed graph is the internet some times known as the web graphi Here every vertex cor responds to a webpage and edges are hyperlinks from one webpage to another webpagei Because there does not have to be symmetry ie I might link to awebsite about kittens but that does not mean the kitten web site links to me the directed graph is the appropriate one to use The web graph is one of the most stud ied and probably one of the most lucrative graphsi Companies such as Google make a lot of money mining information from this graph An example of a hypergraph is the Fano plane This is the smallest discrete geometry it consists of seven points seven lines where each line contains exactly three points any two lines intersect in exactly one point and any two points are contained in one unique line This is shown belowi We can represent the Fano plane as a hypergraph by letting the points of the Fano plane be the vertices and the edges of the hypergraphs be the lines So in this case every edge consists of three points One reason that we do not study hypergraphs is that we can model them using undirected bipartite graphsi A graph is bipartite if the vertices can be split into two parts V UUW where U and W are disjoint and such that all the edges in the graph connect a vertex in U to a vertex in W1 A hypergraph G E can then be associated with a bipartite graph H VUE 5 where 5 connects v E V to e E E if and only if the vertex v is in the edge e So for example the hypergraph for the Fano plane can be represented using the following bipartite graph where points are on the top lines are on the bottomi While not as nice a picture as the Fano plane it still has all of the same information and we can still use it to determine properties of the Fano plane Because of their ability to model interaction between two groups bipartite graphs are an important area of study in graph theory As another example suppose that we want to model the social interaction between a group of ve boys and ve girlsi There have been various relationships formed over the years and some people get along great and have fun dating while other couples don7t work at all We can model this by a bipartite graph where on the left we have the girls on the right we have the boys and we put an edge between two people if they can date Suppose that doing this we get the graph shown below on the left We might then ask the question is it possible for all the people to have a date for this Friday In this case we need to nd a way to pair people up so that every person is in exactly one pairing and they get along with the person they are paired with So looking at the graph we see that the rst girl would have to be paired with the second boy the second and fourth girls would then decide how to go with the rst and third boys while the third and fth girls would then decide how to go with the fourth and fth boysi In particular there are four ways that people can be paired up for dates we show one of them above on the right This is an example of a matching A matching of a graph is a subset of edges so that each vertex is in exactly one edge Note that this de nition does not require the graph is bipartite 1n the graph above there is a matching but not all graphs have matchingsi For example consider the following graphi It is easy to see that there is no way to match up the vertices in this graph since there is an odd number of vertices if there were a matching then the number of vertices would have to be a multiple of two This graph is a special type of graph known as a cycle A cycle on n vertices denoted On consists of the vertex set 121 1 i n with edges ii1 for i 1 i i i n71 and Lil If we do not include the last edge the 1 then the graph is a path on n vertices denoted P W Another well studied graph is the complete graph Kn which consists of the vertex set 12 l i i n and has all possible edgesi Since edges consist of subsets of size two then there are edges in the complete graph The graph K5 is shown below on the left Closely related to the complete graph is the com plete bipartite graph Kmm which has as its vertex set v1 1 i i vmu1i i i an and as edges all edges of the form 1 uj In other word we have a bipartite graph with one part of size m one part of size n and all pos sible edges going between the two parts so in total mn edges The graph 34 is shown above on the right One of the most famous graphs the Fabio of graph theory if you will is the Petersen graph This graph consists of 10 vertices and 15 edges as shown belowi This graph is a classic examplecounterexample to many problems in graph theory and is a good graph to have around when testing a new idea we will use this as an example in a later lecturer Another important graphs are hypercubes Q7 here the hyper refers to high dimensions these graphs are not themselves hypergraphsi The vertex set of these graphs consist of all binary strings of length n so that there are 2 vertices Two vertices are con nected if the strings differ in exactly one entry So for example Q1 consists of vertices 0 and 1 with an edge connecting them Q2 consists of the four vertices 00 01 10 and 11 and form a four cycle note that there will be no edge connecting 00 and 11 since they dif fer in both entries and similarly no edge connecting 01 and 10 The graph Q3 is shown below you should try to label the vertices with the eight binary strings of length three that would give this graph The name hypercube comes from the idea of the vertices denot ing the corners of an ndimensional cube sitting at the origin because binary strings are used in computers these graphs frequently arise in computer science Note that the hypercube is a bipartite graph To see this we need to tell how to break up the vertices into two sets so that edges go only between these sets This is done by letting U be the set of binary strings of length n with an odd number of 1s and W the set of binary strings of length n with an even number of 1s Since an edge connects two vertices which differ by exactly one entry we will either increase or decrease the number of 1s by one so that edges must go between U and W1 Let us now look at how many edges are in the hyper cubei Before we do that we rst need a few de nitions Two vertices u and v are adjacent if there is an edge connecting them this is denoted as uwvi An edge e and a vertex v are incident if the vertex v is contained in the edge e pictorially the edge connects to the ver texi The degree of a vertex is the number of edges incident to the vertex equivalently the number of ver tices adjacent to the vertex assuming we do not allow loops and multiple edges we denote the degree of a vertex by d1 or v 1 1n the hypercube graph Qn every vertex corresponds to a string of length n To connect to this vertex we must differ in exactly one letter since there are n pos sible letters then there are n different vertices that connect to the graph In other words every vertex in the graph has degree no If we add up all the degrees then we get n2 But adding up all the degrees we will count each edge exactly twice so that twice the num ber of edges is n2 or the number of edges is n2n 1i As an example in Q3 there are 322 12 edgesi A graph where all of the vertices have the same de gree is known as a regular graph The Petersen graph is a regular graph of degree 3 the hypercube is a reg ular graph of degree n the complete graph Kn is a regular graph of degree n 7 1 and the cycle On is reg ular of degree 2 Of course there are many others regular graphs have nice properties particularly when approaching graphs using linear algebra Looking at our derivation for the number of edges in Qn we noted that by adding up the sum of the degrees that we got twice the number of edges This is the rst theorem of graph theory Handshake Theorem For a graph G let denote the number of edges then Eda 2113 veV In particular this implies that the sum of the degrees must be an even num err So we have the following immediate corollaryi Corollary of the Handshake Theorem The number of vertices with odd degree must be even Example Does there exist a graph on six vertices where the vertices have degree 1 2 3 3 4 4 Solution Nor Summing up the degrees we get 17 which is an odd number but by the handshake theo rem if such a graph existed the sum would have to be even Of course just because the sum of the degrees of a graph is even does not mean that a graph existsi Example Does there exist a graph on six vertices where the vertices have degree 1 2 3 4 5 5 Solution Nor Summing up the degrees we get 20 so the handshake theorem does not rule it out However if there were such a graph then it would have two vertices of degree 5 in particular these two vertices would have to be adjacent to every vertex in the graph Or put another way every vertex in the graph would have to be adjacent to the two vertices of degree 5 but this would imply that no vertex can have degree less than 2 in particular we could not have a degree 1 vertex as desired Finally we turn to a problem mentioned earlier Namely we like to represent graphs visually but the way that we can draw the graph is not unique as we can place vertices where we like and draw edges as we want For example consider the following two graphs 5 4 C These graphs have the same number of vertices 7 the same number of edges 14 all the degrees are the same but are they two different drawings of the same graph or two different graphs altogether To answer this question we have to decide what we mean to say that they are the same graph or rather they have the same structure We say two graphs G and H are isomorphic iso same mor phic77 structure if there is a bijective oneto one and onto map 45 VG A VH so that uv in G if and only if in Hi Or in other words we can map the vertices of one graph to the other in a way that preserves adjacency n terms of the picture above the question is can we relabel the vertices of one graph and produce the other graphi Careful checking will see that if we relabel as follows1gt gta2Hc3gt gte4gt gtg5gt gtb6gt gtdand 7 gt gt f then we preserve adjacency In other words these two graphs are isomorphic so are two drawings of the same graphi To show that two graphs are isomorphic then it suf ces for us to nd a way to relabel the vertices of one graph to produce the other graphi To nd a rule for relabeling we often try to identify some vertices that must be mapped one to the other ie because of de gree considerations and slowly build up the relation sh39 To show that two graphs are not isomorphic we need to nd some structure that one graph has that the other does not showing they cannot be the same graphi We will pick this topic up again in the next lecturer Lecture 19 7 May 13 Our main focus in graph theory will be simple undi rected graphsi Simple graphs refer to graphs without loops or multiple edgesi A loop is an edge that con nects a vertex to itself ie multiple edge is several edges going between the same two vertices iiei In other words we want to eliminate the possibility of having a repeated element in our sets A useful technique in proving statements is proof by contradiction The underlying idea is to assume the opposite of what we are trying to prove and show that this leads to an impossible situation This implies that our assumption is wrong well our assumption was the opposite of what we are trying to prove so this means what we want to prove is true In other words we are proving something is not not true Example Show that in any simple graph on two or more vertices there must be two vertices which have the same degree Solution Suppose that it is not true iiei suppose that there is a graph where all vertices have different degrees Also for convenience let us suppose that we have n vertices Then the possible degrees in the graph are 01i i n7 1 Since there are n vertices it possible degrees and all of them are distinct this implies that we must have 0 a vertex of degree 0 ie a vertex not connected to any other vertex and o a vertex of degree n 7 1 ie a vertex connected to every other vertexi But clearly we cannot have both of these vertices in the same graphi Therefore our assumption is false and in particular there must be some two vertices with the same degree In the last lecture we looked at telling if two graphs were isomorphici We saw that the way to show that two graphs were isomorphic was to produce a bijective 45 VG A VH that preserves adjacencyi But now suppose that we want to show that two graphs are not isomorphici To do this we need to nd some structure that one of the graphs have that the other doesn7ti Some possibilities to look for o If the graphs are isomorphic they must have the same number of vertices and the same number of edges 0 The two graphs must have the same degree se quences ie the list of degrees 0 The complement of the graphs must be isomor phici 0 Both graphs must either be connected of not con nected o If the graphs are isomorphic then if G has a sub graph K H must also have a subgraph isomorphic to K i These are only a few of the possibilities of things to look for The list is nearly endless of things to look for The nice thing is that to show two graphs are not isomorphic we only need to nd a single property they donlt agree on so we usually don7t have to go through the whole list of possibilities to show graphs are not isomorphici We have introduced a few terms on this list that we need to go over The complement of a graph G de noted 5 is the graph with the same set of vertices of G and all edges not in Ci So for example the complement of Km would consist of a Km and Kn with no edges between the two complete graphsi As another exam ple consider the complement of the Petersen graph since K10 has degree 9 and the Petersen graph has de gree 3 then the complement will be regular of degree 6 and so in particular will have 30 edges we won7t draw it On a side note the complement of the Pe tersen graph is the complement of the line graph of K5 but that is another story If graphs have many edges sometimes it is easier to work with the complements which can have fewer edgesi A subgraph of a graph G V E is a graph H where V E V and E E El So for example a path on n vertices is a subgraph of a a cycle on n vertices which in turn is a subgraph of Kn in fact every graph on n vertices is a subgraph of A graph is connected if between any two vertices we can get from one vertex to another vertex by going along a series of edges That is for two vertices u 1 there is a sequence of vertices v0v1uivk so that u vowvl 0le2 Hi 1amp4ka of Another type of graph is a planar graph This is a graph which can be drawn in the plane in such a way so that no two edges intersecti Of course every graph can be drawn in the plane the requirement that edges do not intersect though adds some extra constrainti It is important to note in this de nition that a graph is planar if there is some way to draw it in the plane without edges intersecting it does not mean that every way to draw it in the plane avoids edges intersectingi So for example in the last lecture we saw the graph Q3 and drew it as shown below on the left In this drawing we have edges crossing each other twice so that this is not a way to embed it in the plane without edges crossing but we can draw it in a way without edges crossing which is shown below on the right To show a graph is planar we need to nd a way to draw it in the plane without any edges crossingi How do we show a graph is not planari For instance try drawing K33 or K5 in the plane it turns out to be dif cult But is it dif cult because it is impossible or is it dif cult because we are not seeing some clever way to draw it It turns out that in this case it is dif cult because it is impossible as we will soon prover The main tool for dealing with planar graphs is Eu ler s formula Before we state it we rst need to give one more de nitioni So for a drawing of a planar graph we have vertices and edges but we also have subdi vided the plane into pieces which we call facesi If we were drawing the planar graph on a piece of paper then cutting along the edges we would cut our paper into some small pieces each piece corresponds to a face Let V denote the set of vertices E the set of edges and F the set of faces in the drawing of a planar graph Euler s formula For a connected planar graph lVlilEllFl2A As an example in the drawing of Q3 above we have lVl 8 12 and lFl 6 remember to count the outer face So 8 7 12 6 2 as the formula predictedi In the next lecture we will prove Eulerls formula and use it to show that the graphs K5 and K33 are not planar as well as give some other applications Lecture 20 7 May 15 We now prove Eulerls formula The key fact is the following Every connected planar graph can be drawn by rst starting with a single isolated vertex and then doing a series of two types of operations namely 1 add a new vertex and an edge connecting the new vertex to the existing graph which does not cross any existing edge and 2 add an edge between two existing vertices which does not cross any existing edger One way to see this is that we can run this backwards iiei starting with our drawing of a planar connected graph we either delete a vertex and its incident edge if it has degree one if no such vertex exists we remove an edge from the graph which will not disconnect the graph There is a subtlety to worry about how do we know that if all vertices have degree two or more that we can remove an edge without disconnecting the graph To see this note that ifthere were a cycle in the graph ie a subgraph which is a cycle or if you prefer a sequence of edges that starts and ends at the same point then removing an edge could not disconnect the graph since we could simply use the rest of the cycle to replace the now missing edger Further we can grow a cycle by the following technique we start with any vertex and move to an adjacent vertex we then move to a new vertex other than the one we came from and continue doing this until we get to a vertex that we have previously visitedi So suppose that we now have a sequence of vertices v1v2v3 ij and that vjwvi for some i lt j Then the desired cycle is viwvi1 ijwvii The key to this is since each vertex has degree two or more whenever we went into a vertex we could also exit along a different edge We now proceed by induction Our base graph con sists of a single vertexi In that case we have lVl l lEl 0 and lFl 1 ie the outer face and so lVl7lEllFl17012i Now suppose that we have shown that we have lVl 7 lEl lFl 2 for our connected planar graph Gr Sup pose that we do the rst type of operation as given above Then when we are adding a new vertex and a new edge but we do not change the number of faces ie this edge does not divide a face and so WENH1lE l7lEH1anle l7lFlso lV l W W lVl 1 lEl 1 lFl lVlilEllFl2 Suppose that we do the second type of operation as given above Then we do not add a vertex but we do add an edge further we must split a face into two faces andso lV l lVl lE l lEll and lF l lFllso lV l lE l W lVl lEl1lFl1 lVlilEllFl2 Concluding the proof Eulerls formula is the main tool for dealing with pla nar graphsi In this lecture we will show how to use it to prove that some graphs are not planar we will also see some additional applications in the next lecturer So let us rst try to prove that the graph K5 is not planari Before we do this we rst need to introduce the idea of counting the bounding edges in a face Every face can be though of as being contained inside of some cycle and so we can count how many edges are in the cycle by starting at a vertex and walking clock wise around the face and counting how many edges we encounter before we return to our starting position this will be the number of edges in the face There is a small bit of subtlety to be aware of namely consider the following graph a planar graph on three verticesi 0 0 0 This graph has two edges and a single face so as predicted by Eulerls formula 37 21 2 How many edges are in the face Our natural instinct is to say two but the correct answer is four That is because as we walk around we will encounter each edge twice and we count an edge each time we encounter it Put another way if we had cut along the edges we could not distinguish between this graph and what would have happened if we started with a four cycle The reason that we are using this de nition is be cause we want to be able to count edges by using in formation about facesi Namely since each edge will be used in two faces or twice in a single face if we add up the number of edges in each face we will have double counted all the edges in the graph iiei ZlEl Z fEF edges in face f We now make an observation for every simple con nected planar graph on at least three vertices each face has at least three edges in it The reason that we limit ourselves to simple graphs is that a loop would be a face with a single edge while a pair of vertices connected by two edges would give a face bounded by two edges Plugging this into the above formula we have edges in face f 2m Z fEF 2 233m fEF so that lFl S Putting this into Eulerls for mula we have 2 2lVl7lEllFl S lVlilEHglEl or rearranging we have El 3 3m 76 We are now ready to prove the following K5 is not planari Suppose that K5 were planari Since it a simple con nected graph on ve vertices this would then imply by the above inequality that S SlVl 7 6 but for K5 we have 10 and SlVl 7 6 9 so this is impossible So K5 is not planari Another graph that is dif cult to draw in the plane is K33 if we apply the above inequality we see that lEl 9 and SlVl76 12 From this we can7t conclude anything just because a graph satis es the above in equality does not automatically imply planari We will have to work a little harder for K3 One thing that we might be able to use is that the graph K33 is bipartite and bipartite graphs have nice structure In particular we have the following A graph is bipartite if and only if every cycle al lowing for repetition of edges in the graph has even lengthi The assumption that we allow for edges to be re peated is not important and can be removed from the following arguments with a little carer Since it is an if and only if statement we need to prove both directions First let us suppose that our graph is bipartitei So we have that the vertices are in sets U and W with all edges going between U and Wi Suppose that we start our cycle at a vertex in U then after the rst step we must be in a vertex in W then after the next step we are back in U and so on So our cycle keeps going back and forth between the two sets After an odd number of steps we will be in W and after an even number of steps we will be in Ur Since a cycle must begin and end at the same vertex our cycle must have even lengt Now let us suppose that every cycle in our graph has even lengthi Without loss of generality we may assume that our graph is connected ie we can work on each component a maximal connected subgraph show that each is bipartite and so the whole graph is bipartitei e x a vertex 5 and partition the vertices into V0010 and Veven by putting a vertex 1 into V0010 if there is a path of odd length between 5 and v and putting a vertex 1 into Veven if there is a path of even length between 5 and vi We claim that this is well de ned ie no vertex could be in both sets since if there were a path of even length and a path of odd length between 5 and v we could form a cycle by starting along the path of even length from 5 to v and then follow the path of odd length backwards from v to 5 ie we are concatenating the paths This new cycle would have an odd number of edges but by our assumption this is impossible Similarly there cannot be an edge connecting two vertices v w in V0010 similarly for Veven since we could then form an odd cycle by going from 5 to 1 from v to w and from w to E So this shows that we can split the vertices into two sets and all edges in the graph go between these sets by de nition this is a bipartite graph Since the edges bounding a face correspond to a cy cle we must now be able to conclude that in a simple connected planar bipartite graph on at least three ver tices each face has at least four edges iiei edges in ZlElZ 244m feF face f feF so that lFl S Putting this into Eulerls for a we have 1 2 M 7 E F s M 7 E ilEl or rearranging we have El 3 2m 7 4 We are now ready to prove the following K33 is not planari Suppose that K33 were planari Since it a simple connected bipartite graph on six vertices this would then imply by the above inequality that S QlVl 74 but for K33 we have 9 and QlVl 7 4 8 so this is impossible So K33 is not planari We have now shown that K33 and K5 are not pla nari In some sense these are the problem graphs for planarityi We will make this more precise in the next lecturer Lecture 21 7 May 20 In the last lecture we saw that K5 and K33 are not planari Clearly any graph which contains K5 or K33 as a subgraph cannot be planar since any subgraph of a planar graph must be planar But that is not the only possibility for ruling out planar graphs for instance consider the graph shown belowi This graph is found by taking K33 and subdividing an edge into two edges The resulting graph is not K33 but we see that it cannot be planar because if it were we could replace the subdivided edge by a new single edge to recover a way to draw K33 in the plane So it is not just the graph K33 but rather any graph sharing similar structure or in topology homeomorphici We say that a graph G contains a topological K5 or K33 if starting with G we can do three operations and form K5 or K33 namely H Remove an edge 2 Remove a vertex and any edge incident to the vertex 3 Contract an edge to a single vertexi That is if uv then we remove the edge joining u and v and combine the two vertices u and 1 into a new vertex uv this new vertex is adjacent to any vertex that was previously adjacent to either u or vi The rst two operations correspond to what it takes to form a subgraph so it is this last operation that is of the most interest to us This is the one that allows for us to take the graph K33 with a subdivided edge and contract one of the two edges to from K331 It is not hard to see that if a graph contains a topo logical K5 or K33 that it cannot be planar ie if it were we could use it to embed K5 or K33 Amazingly this turns out to be the only situation that we need to avoid Kumtowski s Theorem A graph G is planar if and only if it does not contain a topological K5 or 33 Example Show that the Petersen graph is not planarl Solution To show that the Petersen graph is not pla nar we must nd a topological K5 or K33 inside of it Looking at the Petersen graph it is easy to see that if we contract the edges between the outer pentagon and the inner star below highlighted in red that the re sulting graph is K5l Therefore it contains a topological 5 and so is not planarl We now give one nal application of Eulerls formula A Platonic solid is a polyhedra equivalent of a three dimensional polygon where each face is composed of a regular ngon an n sided polygon with each side and each interior angle equal and at every corner there are exactly m faces that meet Two examples of Platonic solids are the tetrahedron faces are triangles and at every corner three triangles meet and cubes faces are squares and at every corner three squares meetl Our goal is to determine how many Platonic solids there are The rst thing we need to do is to relate this to planar graphs Imagine that we are holding a poly hedra in our hand that is made out of a very stretch able rubberl Then we can puncture a small hole in one of the faces of the polyhedra and start pulling it apart stretching it out until we have attened out the rubber Then the corners and edges of the polyhedra form a planar graph with the corners becoming ver tices and the edges becoming well edges The faces of the polyhedra become the faces of the planar graph For example if we had started with a cube we would get the following graphl This connection between planar graphs and poly hedra is one reason that planar graphs are interesting to study So let us now translate the conditions to be a Pla tonic solid into conditions on the corresponding planar graph Each face being a regular ngon means that each face is bounded by exactly n edgesl As before we can double count edges by adding up the number of edges in each face and so we have 2lEl anl or lFl n The requirement that m faces meet at each corner tells us that at every vertex we have exactly m edges coming in So by the handshake theorem we have 2 2lEl lel or lVl m Putting this into Eulerls formula we have 2 2 ElEl 7 El glEl 7 2 or dividing everything by 2lEl 1 1 1 1 7 7 7 7 0 m n 2 gt So in order to be a Platonic solid we need to have 1 1 gt 1 m n 2 7 and we must also have that m n 2 3 This only gives us ve possibilitiesl Platonic solid Tetrahedron Octahedron lcosahedron Cube Dodecahedron U1gtJgtCA3CA3CA33 An octahedron has eight triangular faces an icosahe dron has twenty triangular faces and a dodecahedron has twelve pentagonal facesl Therefore the number of faces on Platonic solids are 46531220 For people familiar with role playing you might notice that these numbers are on the most common type of dice that are available Finally let us prove the following theoreml Mantel s Theorem If a simple graph on 2n vertices contains n2 1 edges then G must contain a triang el To contain a triangle means that there are three ver tices u vw so that uNUNwNu ie the three vertices form a triangle Note that this result is the best pos sible since the graph Kan has 2n vertices and n2 edges but no triangle since a triangle would give a cycle of odd length which we know cannot happen in a bipar tite graphl Also not how general this is we are saying that no matter how you draw the graph if it has 2n vertices and n2 1 edges it must contain a triangle and in fact contain many triangles To prove this we will make use of one of the funda mental principles in combinatoricsl Pigeon hole principle If you distribute 7 balls among n bins and 7 gt n then some bin has more than one bal The proof is by contradiction suppose not then the total number of balls is less than the number of bins which by assumption is impossible This principle seems so obvious that it is amazing that it can be used to prove anything but in fact it is used in many beautiful proofs including the proof we are about to give for Mantel s theoreml We proceed by induction For n 1 it is vacuously true since there is no graph on 2 vertices with 2 edges This is enough to get our induction started but sup pose that we are no comfortable with this case then for n 2 it is also true since the only graph on 4 ver tices with 5 edges is found by taking an edge out of a K4 and it is easy to check that this graph has two triangles ow let us suppose that we have shown that any graph on 2n vertices with n2 1 edges has a triangle Consider now a graph G on 2n 1 2n 2 vertices with n 12 1 n2 2n 2 edgesl Let u and v be two vertices in G joined by an edge Then we can draw G in the following way Namely as two vertices connected to an edge and then connected to the rest of the graph Consider the graph on the vertices other than u and 1 this has 2n vertices and so if there are n2 1 edges in this part of the graph then by the induction hypothesis it must contain a triangle and we are done 0 we may now assume that there are S n2 edges in the part of the graph not containing u and vi Since there is 1 edge connecting u and 1 that says that there are 2 2n1 edges between the vertices u v and the other 2n verticesl So by the pigeon hole principle there must be some vertex that is connected by two edges to the vertices u and 1 ie there is a vertex w so that wNu and wwv but since we already have uv then we have our triangle and this concludes the proof Lecture 22 7 May 22 Before we return to graph theory let us look at a nice application of the pigeon hole principlel Let 121122 12 be a rearrangement of 1 21 n so for example when n 7 one such rearrangement is 35214761 A subsequence of this rearrangement is billy2 bi where i1 lt i2 lt lt ik ie we pick some elements of the rearrangement and still preserve their order Some examples of subsequences in the ar rangement for n 7 given above include 3146 5247 35 246 and so on A subsequence is said to be in creasing ifbi1 lt 12 lt lt 12 for example 146 in the above while a subsequence is said to be decreasing if 12 gt 12 gt bik for example 521 in the above For every rearrangement of 1 21 l l n2 1 there is always an increasing subsequence of length n 1 or a decreasing subsequence of length n 1 This result is the best possible since if we rearrange 121 1 l n2 it is possible to have no increasing or de creasing subsequence of length n 1 For example for n 9 the only two sequences that do this are 321654987 and 789456123 We divide it2 into it blocks of n then we either reverse each block and put them in order or reverse the order of the blocks Obviously we are going to use the pigeon hole prin ciple to prove the result The idea behind proofs which use the pigeon hole principle is to show that there is some meaningful description of the objects bins so that the number of objects balls is more than the number of ways to describe them and so two of the objects must satisfy the same description We then use this fact to either derive a contradiction or con struct a desired objectl Suppose we have a rearrangement of 1 21 l l n2 11 Then for each i 1 21 n 1 we associate a pair Ii Di where Ii is the length of the longest increasing subsequence that ends at bi and Di is the length of the longest decreasing subsequence that ends at bil so for example for the rearrangement 3521476 we get the following pairsl 11 21 12 13 22 31 32 3 5 2 1 4 7 6 Note that all of the pairs listed above are distinct To see this suppose that i lt j then if bi lt bj we can take an increasing sequence ending at bi and tack on bj to get a longer increasing sequence ending at bj showing Ii lt I similarly if bi gt bj then Di lt Djl In any case we have that ifi a j then IiD IjDjl If there is no increasing and decreasing sequence of length n 1 or more than we must ave that 1 S IiDi S n ie there are at most n2 possible IiDli On the other hand there are n2 1 points and so there are n2 1 pairs IiDl so that by the pigeon hole principle two would have to be the same This is impossible And so we can conclude that there must be an increasing or decreasing sequence of length n 1 or more We now return to graph theory We start with the rst major result in graph theory given by Euler in 1736 It is based on the following story In Konigsberg now called Kaliningrad there was a large river that ran through the city and in the middle of the river were two large islands Between the islands and the shore were seven bridges arranged as be owl As the story goes it was fashionable on Sunday evenings for the citizens of Konigsberg to dress in their nest and walk about the city People tried to nd a route where they would return to the place they started at and cross each bridge exactly oncei Try as they might people could not gure a route that would accomplish this Euler learned of the problem and he approached it by rst translating it into a question about graph the ory He let each piece of land be a vertex and each bridge an edge connecting two vertices This gives us the following multigraph a multigraph because it has two edges between two vertices Translating this into graph theory we are looking for a cycle in the graph ie we start at a vertex and move along edges and end at the vertex we started at which visits each vertex at least once and uses each edge exactly once the main condition is that we are using each edge exactly oncei Such a cycle is called an Euler cyclei Euler made two observations rst if the graph is to have an Euler cycle then it must be connected because we can get from any vertex to any other vertex by using the cycle The second observa tion is that the degree of each vertex must be even To see this if we look at each vertex we will at some point come in and then we will leave via a different edge the idea here is that we can pair up the edge we came in with the edge that we came out and we do this every time we return to the vertex Now looking at the graph above it is easy to see that it is impossible to have an Euler cycle because the degrees of the graph are 3335 not even one even degree 0 we now know when a graph does not have an Euler cycle ie it is not connected or has odd degree vertices but when does a graph have an Euler cycle Amazingly the necessary conditions are also suf cient conditions A graph has an Euler cycle if and only if it is con nected and every vertex has even degreei We have already seen that if a graph has an Euler cycle that it is connected and every vertex has even degreei So we need to go in the opposite direction ie we need to show that if the graph is connected and every vertex has even degree that it has an Euler cycle We do this by giving a construction that will make an Euler cycle and show that the requirements for the construction are precisely those that the graph is connected and every vertex has even degreei We start with our graph and pick a vertex vi We start by forming a cycle by going out along an edge and then once we get to a new vertex we go along a previously unused edge The important part is that we will always use a previously unused edge We keep doing this until we get to a vertex that has no previ ously unused edger Since every vertex has even degree every time we come into a vertex we can exit along a different edge ie we can pair edges up the only ver tex where this is not true is the vertex that we started at and so we now have a cycle where each edge is used at most once If we have used all of the edges then we are done So suppose that we have not used all of the edges Since the graph is connected there must be some vertex w in the cycle that is incident to a previously unused edge We start the process again at this vertex and create another cycle that uses each edge at most once We now glue the two cycles together iiei go from v to w along part of the rst cycle use the second cycle to get from w to w and then nally use the remaining part of the rst cycle to get from w to vi hus we have a longer cycle where each edge is used at most once We continue this process until we create a cycle which uses each edge exactly once our desired Euler cyclei Related to Euler cycles are Euler paths the only difference being that we do not return to the vertex that we started at ie we form a path not a cycle It is easy to see that we have the following condition A graph has an Euler path if and only if it is con nected and exactly two vertices have odd degreei Note that the Euler path must start and end at the vertices with odd degree1 Example Can the following gure be drawn without lifting a pencil or crossing each edge twice Solution Making this a graph by putting a vertex where any edges come together we get the following In particular we see that the degrees of this graph are 2 3 3 4 4 41 Since it has exactly two vertices with odd degree this graph has an Euler path which would correspond to a drawing of the graph where we draw each edge exactly once and we never lift our pencil off the paper1 We can even see that if we wanted to be able to draw it we must start at either the lower left or the lower right corner ie the vertices with odd degree1 Lecture 23 erhday 27 There is a directed analog for Eulerian cycles1 Recall that in a directed graph each edge has an orientation which we marked with an arrow1 So an Eulerian cycle for a directed graph is one that uses each edge exactly once visits each vertex and also on each edge goes in the direction indicated by the orientation For the undirected graphs we used the fact that every time we came in we also had to leave so that we paired up edges and so the degree at each vertex had to be even For directed graphs we have the same situation except now we have that when we pair edges up we pair an edge going in t0 the vertex with one going away from the vertex This gives us the directed analog for Eulerian cycles1 A directed graph has an Euler cycle if and only if it is connected and at every vertex the number of edges directed into the vertex equals the number of edges directed away from the vertex We can use the directed Euler cycles to construct de Bruijn sequences1 A de Bruijn sequence is a way to pack all 2 binary words of length n into a single binary word of length 2 where each binary word of length n occurs exactly once as n consecutive digits where we also allow for wrapping around1 For exam ple or n 1 we ave the binary words 0 and 1 so a de Bruijn sequence in this case is 011 For n 2 we have the binary words 00 01 10 and 11 and it can be checked that 0011 is a de Bruijn sequence For n 8 there are two possible de Bruijn sequences 00011101 and 00010111 below we check that the rst one is a de Bruijn sequence remember that we allow for wrap aroundl1 location 11101 001 00011101 010 00011101 011 00011101 100 00011101 101 00011101 110 00011101 111 00011101 The rst question that should be asked is do such se quences always exist and if so how to construct them1 They always exist and the method to construct them involves directed Eulerian cycles which conveniently we just discussedl1 To make a de Bruijn sequence for binary words of length n we de ne a directed graph 39Dn1 The vertices of 3913 are binary words of length n 7 1 so that there are 2 1 vertices and we have directed edges going from a1a2a3111an1 A a2a3111an1an1 In other words we put a directed edge if the last n 7 2 digits of the rst vertex matches the rst n72 digits of the second vertex1 Note in particular that each edge is associated with a binary word on n letters and each binary word on n letters is associated with a unique edge1 So de Bruijn sequences then say that we need to use all of the edges The graphs D3 and D4 are shown below1 000 1 n39 H 1U AUl 00 313 01 4 10 l01 4 1 0 0 1 11 111 We now make some observations about this graph 0 The graph 3913 is connected To see this we have to describe a way to get from any vertex to any other vertex1 Suppose that we have ver tices a1a2a3111an2an1 and 21122123 1 1 1 bn2bn1 then we can use the following edges to connect the vertices 041042043 ian72an71 7gt agag i an72an71b1 agag i an72an71b1 7 a3 1 i an72an71b1b2 anqblbgbg 11272 a b1b2b3mbn2bn1 Basically at each step we take off one term from the rst vertex and add on a term from the sec ond vertexi So after n 7 1 steps we can get from any vertex to any other vertex so the graph is connected The number of edges going into a vertex is equal to the number of edges going out of a vertex More precisely there are 2 edges coming in and 2 edges going out For a vertex alag ian72an71 the edges coming in are 0a1a2 i an2 7gt alag i an72an71 1a1a2 i an2 7gt alag i an72an71 while the edges going out are alag i an72an1 7gt a i i an2an10 alag i an72an1 7gt a i i an72an711 By the above two items we see that the graph 3913 has an Euler cycle in fact it can be shown that it has 22n71 Euler cycles The last thing to note is that every Euler cycle corresponds to a de Bruijn sequence and viceversa For example in the graph D3 it is easy to nd an Euler cycle 007007017117gt117gt107gt017gt107gt001 To turn it into a de Bruijn sequence we take each edge and record the letter that it adds onto the end of the word Doing that for the above sequence we get 01110100 which is a de Bruijn sequence note that this is the same as the de Bruijn sequence listed ear lier where we have shifted the entries but since we are dealing with an Euler cycle shifting the entries only corresponds to changing the starting location of our Euler cycle it is still the same cycle The way to see that this works is that every edge is coded by a word of length n namely the rst n71 digits tells us the loca tion of the originating vertex and the last n 7 1 digits tells us the location of the terminal vertexi Looking at a term and the previous n 7 1 terms where we cycle back tells us the edge we are currently on Since we use each edge exactly once each binary word of length n must show up exactly oncei de Bruijn sequences have an interesting application as part of a magic trick 1 learned this from Ron Gra ham and Persi Diaconis who are writing a book about magic and mathematics Namely a magician is per forming a magic show and he throws a deck of cards out into the back of the audience The person who catches it is told to cut the deck which is to split the deck in half and then put the top half on the bottom then hand it to the person to their right this is re peated until ve people have cut the deck This is to show that their is no one in cahoots with the magi cian ie the magician now has no idea what card is on top He now has the fth person take off the top card and hand it back to the fourth person who again takes off the top card and hands it back to the third person and so on until the last person He now looks at the ve people holding cards and he tells them he is going to read their minds and tell them which card they have and asks them to each focus on the card that they have He stares intensely for a fes second and then declares 1 am having a little trouble receiving your mental signals 1 have discovered that sometimes the signals from the red cards overpower the black cards could everyone holding a red card please sit down77 At this point anyone holding a red card sits down He continues Ah much better 1 now can see the cards clearly and you have a Mr at which point he lists everyones card So what happened Well one possibility is that the magician can actually read minds but there is an eas ier explanationi Noticed that he asked for people to sit down this was a way to send a signal to him about the order of the black and red cards The magician actually planned ahead and did not toss out a random deck but instead had a deck where he had arranged 32 cards note that 25 32 in a speci c order so that any ve consecutive cards had a unique pattern of red and black cards this is easily done using a de Bruijn sequence for n 5 The fact that he had them cut cards did not change the de Bruijn sequence the only important thing was that he had ve consecutive cards and he was able to determine the order of the red and black cardsi Once he knew this he knew where he was in the de Bruijn sequence and he could then say which cards they were by memorizing the locations or having a cheat sheet to look off The idea behind Euler cycles is that we have a cy cle in the graph which uses each edge exactly once We can ask a similar question about a cycle which uses each vertex exactly oncei Such a cycle is called a Hamilton cycle after a mathematician who studied these cycles and also invented a related game about trying to nd a way to visit twenty different cities so that each city is visited exactly once 1 While it is easy to characterize graphs which have Euler cycles it is dif cult to characterize graphs which have Hamilton cycles also known as hamiltonian graphsi There are some clearly necessary conditions ie the graph must be connected and it cannot have any bridges on the other hand there are also some suf cient conditionsi But there are no set of conditions which are necessary and suf cient that work for all graphsi An example of a suf cient condition is Diracls Theorem we will not prove it but its proof can be found in most graph theory textbooksi Dime s Theorem If G is a graph on n 2 3 vertices and the degree of each vertex is 2 n2 then G is hamiltoniani In general to show a graph is hamiltonian we only need to nd a cycle that uses each vertex exactly oncei To show a graph is not hamiltonian we need to show that it is impossible to nd a cycle that uses each ver tex exactly once in this case it pays to be clever ie to avoid looking at every possible cyclei Example Show that the graph below is hamiltoniani Solution We only need to nd a hamiltonian cycle This is not too hard and one possibility is shown belowi Example Show that the following graph does not have a hamiltonian cyclei Solution Note that this is almost the same graph as before the only difference is that now we have taken an edge and split it into two edges but apparently even this small change is enough to force us to not be hamil toniani Let us make an observation if the graph has a hamiltonian path then any vertex with degree two must have both edges in the cycle So looking at our graph any hamiltonian cycle must have the following four edges y symmetry we can assume that for the vertex in the middle on the left it connects to the vertex in the top on the left as shown below on the left Once two edges incident to a vertex are used in a hamiltonian path any remaining incident edges to that vertex cannot be used so we can remove it from further consideration as shown above on the right Using this observation we get the following graphsi Looking at the graph on the right it is easy to see that no matter which of the remaining edges we use we will run into a problemi In particular we cannot close up and form a hamiltonian cycle We can make a path that uses all the vertices exactly once such a path is called a hamiltonian pathi Lecture 24 7 May 29 A special case of hamiltonian cycles are hamiltonian cycles on the n dimensional hypercube These are known as Gray codes named after Frank Gray an engineer at Bell Labs Because of their connection to binary words they are studied in computer science They also are useful if we want to look through all pos sible combination of using or not using some collection of objects since the edges in the hypercube only change in one digit so this corresponds to changing the state of just one object at each step We now show how to construct a hamiltonian cycle for First note that this holds for n 1 since we have 0 A 1 A 0 in this case we will allow ourselves to go back over the edge we used For n 2 we have essentially only one cycle that is we can assume that we start at 00 0 and that we pick some direction namely 00H01gt11gt10gt00i In general if we have a hamiltonian cycle for Qn call it R then to construct a hamiltonian cycle for Qn we look at OR and 1E ie we put a 0 in front of everything in R the OR and then we put a 1 in front of everything in R where we run in reverse order the 1 For example using the above Gray code for n 2 we get the following Gray code for n 3 000gt001gt011gt010 H110gt111gt101gt100 H000 x x 0B 1B It is easy to see that this will visit all vertices and that each two consecutive entries are adjacent and so we have a desired hamiltonian cycle Of course this is not the only way to form a Gray code In general there are many ways that we can go about forming a Gray code and we can choose differ ent Gray codes which have different desired properties One natural question to ask is how many are there for n 3 there are essentially 6 different Gray codes and these are shown For n 4 there are l 344 different Gray codes and for n 5 there are 906545 760 different Gray codes we will not draw them here For n 6 only an approximate number is known We now turn to coloring graphs There are essen tially two things that can be colored in a graph ver tices and edges We will restrict ourselves mostly to the case of coloring the vertices note that coloring edges is usually equivalent to coloring the vertices of the line graph So a coloring is an assignment of col ors usually listed as l 2 i i i k to the vertices Equiv alently a coloring is a function 45 V A 12 l i i Is Our definition of coloring is very general so most of the time we will restrict our colorings so that they are proper colorings which are colorings of a graph where no two adjacent vertices have the same color The minimum number of colors iiei smallest value of k needed to have a proper coloring for a graph G is called the chromatic number of the graph and is denoted xGi Example Find the chromatic number for Kn bipar tite graphs C7 and the graph shown belowi Solution For the complete graph since every vertex is adjacent to every other vertex they must all have different colors and so xKn n We know a graph is bipartite if we can split the vertices into two sets U and W so that all edges go between U and W in particular if we color all the vertices in U blue and all the vertices in W red then we have a proper coloring so a bipartite graph only needs two colors This gives another characterization of bipartite graphsi A graph G is bipartite if and only if xG 2 For the graph On we note that if n is even that we have a bipartite graph and so we only need two colors If n is odd then the graph is not bipartite so we need more than two colors it is not hard to see that we can use only three namely we go around and alternate redibluekrediblueh H and then when we get to the last vertex we see that it can neither be red or blue so we color it using a third color In particular we have 2 if n is even XCn 3 if n is odd Finally for the last graph we note that it contains the graph C5 on the outer edge Just to color those vertices we need at least three colors then finally the central vertex is adjacent to all the other vertices so it must be a different color then those used on the outer cycle so we need at least four colors and it is not hard to color the vertices of the graph using four colors so the chromatic number is 4 The chromatic number has some interesting appli cations If we look at a graph with a proper color ing then grouping the vertices together with the same color known as the color classes we see that there are no edges between red vertices no edges between blue vertices and so on In graph terminology that says that the vertices in each color class form an indepen dent set a set where no two vertices are adjacent So finding the chromatic number of a graph is the same as finding the minimum number of sets that we can group vertices into so in each set no two vertices are adjacent For example suppose that we want to set up a schedule for committee meetings We want to have as few meeting times as possible but there are some people who serve on more than one committeei In the latter case any two committees with more than one person serving on them cannot meet at the same time Let us represent our situation using a graph where each vertex is a committee and we raw an edge between any two committees that share a member iiei com mittees that cannot meet simultaneouslyi Then the chromatic number of the graph is the minimal number of committee meeting times needed so that each com mittee can meet oncei Further each color class tells us what committees should be meeting simultaneouslyi As another example suppose that we want to store chemicals in warehousesi Some chemicals interact and so must be stored in separate warehouses while other chemicals do not and can safely be stored togetheri Again let us represent the situation using a graph where each vertex is a chemical and we draw an edge between two chemicals if they interact Then the chro matic number is the minimal number of warehouses needed to safely store all the chemicals Further each color class tells us what chemicals should be stored together to achieve the minimuml Given that the chromatic number is a useful prop erty of a graph we would like to have a way to nd it This is a nontrivial problem in general but there are some easy estimates though generally speaking these are quite poor Let AG be the maximum degree of a vertex in a graph G Then xG S AG 11 The proof of this is very easy We start coloring and we color greedily in that at every vertex we use the smallest color not used on any vertex adjacent to the current vertexl Since each vertex is adjacent to at most AG other vertices iiei so it is adjacent to at most AG 1 other colors we only need to use AG 1 colors to make a proper coloring of the graph This Bound is far from best possible and it can be shown that the only graphs for which xG AG 1 are Kn and odd cycles On with n oddl To get a lower bound we rst make the following observationl If H is a subgraph of G then xH S xGl This is easy to see since any proper coloring of G au tomatically gives a proper coloring of Hi So H would never need more colors than it takes to color G and depending on the graph can sometimes use far fewer Clearly one type of graph which has a high chromatic number are complete graphs so one way to look for a lower bound for the chromatic number is to look for large complete graphs inside the graph we are trying to color This gives us the following result Let wG denote the clique number of the graph G ie the size of the largest complete graph that is a subgraph of G1 Then xG 2 wGl Looking at the last result it is tempting to think that the chromatic number of a graph is somehow a lo cal property In other words the main force in giving us a high chromatic number is to have a large clique This is not the case and in fact the opposite counter intuitive fact is true Namely that there are graphs which have high chromatic number but locally look like trees which are simple bipartite graphs we will talk about in the next lecturel More precisely let the girth of a graph to be the length of the smallest cycle without repeated edgesl Theorem Erd s For any Is there exists graphs with xG 2 k and girth at least kl The most famous problem in graph theory which became the driving force of graph theory for more than a century is the four color probleml This dates back to the 1850s when someone noticed that when col oring the counties of England that they only needed four colors so that no two adjacent counties had the same color Adjacent meant that they shared some positive length of distance For instance in the United States the four corners is a point where four states meet at a point namely Utah Colorado New Mex ico and Arizona we would not consider Arizona and Colorado adjacentl We also make the basic assump tion that counties are contiguous The question then became is this always possible for any map We can relate this to graph theory by putting a ver tex for every county or state country whatever and connect two vertices when two counties share a border The resulting graph is planar and so the question be came can every planar graph be colored with four or fewer colors Since every planar graph has a vertex of degree at most 5 it is not hard to show by induction that the chromatic number for a planar graph is at most 6 1n the late 1800s Kempe found a proof that the chromatic number of the planar graph was 4 but it was later shown to have a defect and was modi ed to show that the chromatic number was at most 5 The nal proof was nally settled in the 1970s by Appel and Hakenl Theorem Appel and Haken If G is a planar graph then xG S 4 This was one of the most controversial proofs in mathematics because it heavily relied on computers and could not be veri ed by hand A shorter proof that still relied on computers was subsequently found and most people generally accept the four color theo rem as true Interestingly enough there are similar statements for other surfaces For instance any graph drawn on the surface of the torus with no edges crossing can be col ored in seven or fewer colors but you can also draw K7 on the torus so there is a graph which needs at least seven Surprisingly this was known well before the fact that the plane which we would expect to be the simplest case needs at most four colors and also the proof is much simpler and does not require com putersl Finally we give an application for coloringl The art gallery problem asks the following question Suppose that we have an art gallery which is in the shape of a polygon with n sides we will assume that there are no holes What is the minimal number of guards which need to be positioned inside the art gallery so that the entire gallery is under surveillance 1f the polygon is convex then we only need one guard who can be posi tioned anywhere But the layout for the art galleries might not be arranged in a convex polygon for exam ple consider the gallery below which has 18 sidesi In the art gallery problem for a polygon with n sides with no holes then you need no more than guards to protect the gallery The notation means that you take nS and round down So for instance we know that in the gallery above we need at most 6 guardsi We also note that there are examples where we need at least 3 guards to protect the gallery we do not give them here so this result is the best possible To prove this we rst take out gallery and trian gulate it ie add edges between the corners so that the resulting oor layout is a collection of triangles In general there are many ways to do this it is not imme diately obvious that this can be done it is not dif cult to show but we will omit that step One example for the gallery shown above is the following We now think of this as a graph where the lines are edges and the vertices are polygonsi We claim that we can color the corners in three colors so that in any triangle there is one red corner one blue corner and one green corneri This is easily seen for the case when we start with three sided polygoni lnductively we can take an interior edge and split the gallery into two halves By induction we know that we can color each half satisfying the requirement and then we can combine the two halves to get the desired coloringi For example for the gallery above we get the essen tially unique desired coloring belowi Here essentially unique means that given a triangulation there is only one coloring up to permutation of colors different tri angulations lead to different coloringsi Now we choose the color that is used least often since there are n corners to color and we only use three colors there is some corner used at most timesi Position the guards at the vertices with the color used least ofteni Note that each triangle has a corner with each color and so each triangle is now under surveil lance But of course once all of the triangles are under surveillance the entire gallery is under surveillance and we are done In our case it turns out that based on our trian gulation each color was used exactly 6 times and so we can position guards at either the corners with the blue vertices the corners with the red vertices or the corners with the green vertices and protect the entire galleryi Lecture 25 7 June 1 The art gallery problem from the last lecture has a nice applicationi Fans Theorem Every planar graph can be drawn in the plane with no edges crossing and as all edges as straight lines Previously we said that a planar graph is one which can be drawn in the plane so that no two edges inter sect but we make no requirement about the shape of the edges so they can bend and go around as needed This says that every planar graph can be drawn so that all the edges are straight We sketch the proof of this result here First we note that we can limit ourselves to the case that we are dealing with maximally planar graphs iiei these are graphs where the addition of any edge would make the graph nonplanari The important thing about these graphs is that each face is a triangle if not then we could add edges inside the face to tri angulate it and still stay planari We x one triangle to act as the outer triangular face and we now proceed by induction to show that we can draw the rest of the graph with straight lines Clearly we can draw the triangle with straight lines Suppose we have shown that we can draw a planar graph with n vertices with straight lines Now consider the case with n1 verticesi We know that there is some vertex of degree S 5 in the graph and in particular we can also assume it is not one of the vertices involved in the outer triangular facei Remove the vertex and the incident edges to give a graph on n vertices and we now triangulate the face note that the face will be either a triangle a quadrilat eral or a pentagoni By induction we can now embed the graph on n vertices in the plane with all edges as straight lines Finally remove the edges that we added in earlier we now have to position the last vertex in side the face so that it can connect to all of the other edges using a straight line This can be done since the face has at most ve sides and so by the art gallery problem we know that we need at most 53 1 guards to keep the entire gallery under surveillance ie there is some point which sees all of the corners put the n1th vertex in that point and connect with a straight edge to all other verticesi We now have our desired straight line embedding for our graph on n1 verticesi An important type of graph are trees There are a few different ways to characterize a tree A tree is a graph on n vertices whic o is connected and acyclic no cycles or o is connected and has n 7 1 edges or o is acyclic and has n 7 1 edges or 0 between any two vertices there is a unique pathi There are many others as well We note that for a graph on n vertices to be connected we need at least n 7 1 edges so that in some sense these are the small est77 graphs on n vertices Trees are frequently used to model series of deci sions where we start at a root vertex and then have several options then for each option we might have several more options and so on until we get to the end of the process One important example of this are bi nary trees where we have a root vertex and then every vertex has 0 1 or 2 vertices coming down from that vertex only in computer science do trees grow down which are labeled left or right The binary comes from the number of outcomes being at most two Trees get their names because they do bear a re semblance to actual trees in the sense that trees have nodes branching off into smaller branches which then branch off and unless through some devious topiary the tree does not come back in onto itself An impor tant terminology about trees are leaves These are the vertices of degree 1 in a tree so the end of the tree Every tree on n 2 2 vertices has at least one leaf To prove this we make use of an averaging argumenti Given numbers n1 n2 1 i i nk let 5 denote their av erage Then there is some i andj so that ni S n and nj 2 E In other words unlike the children in Lake Wobe gon not all the numbers can be above average In our case let us note that since the graph is connected the degree of each vertex is at least one ie dv 2 1 for all 1 in the tree By considering the average of the degrees we have that for some vertex 2 dv dvLm22 TL 7 lt 2 n n Here we used the fact that the sum of the degrees is twice the number of edges and that in a tree there are n 7 1 edges So this shows that some vertex has degree less than 2 which combined with the fact that all vertices have degree at least 1 we can conclude that there is a vertex with degree exactly one ie a leaf We can actually say a little more In particular if a graph has a vertex of degree m then it has at least m leaves One way to see this is we start at the vertex of degree m we go out along each edge and we keep walking until we hit a leaf since there are no cycles each leaf that we end up at is distinct and so we must have at least m leaves Alternatively suppose that we have k leaves in the graph so that the remaining n 7 k 7 1 vertices have degree at least 2 the k leaves and the 1 vertex of degree Then we have 2n71 Zdv2 km2n7k71 UEV which simplifying gives k 2 m the desired result Lecture 26 7 June 3 1n the last lecture we discussed binary trees These are trees with a rooted vertex and every vertex has 0 1 or 2 children where each child is labeled left or right Binary here re ects that we have two options at each stage A natural question to ask is how many binary trees are there before we do that we need to say that two binary trees are the same if and only if when we map the root of one tree to the other the trees and labeling iiei leftright remain the same To get an idea we can look at the rst few cases these are shown be ow In particular we see that we have 11 2 5 141 H bi nary treesi These numbers might look familiar and they should they are the Catalan numbersl of trees 31 gt j hf y To see why we should get the Catalan numbers we note that to make a binary tree on n 1 vertices we have a root and then on the left child we have a binary tree on k vertices and on the right child we have a binary tree on n 7 k vertices see picture below1 7 k 7 nik 7 vertices 1 vertices 739 In particular if we let Bn be the number of binary trees on n vertices then we have Bk choices for the binary tree on the left and B7771c choices for the binary tree on the right or Bank ways to make a binary tree But then we can also let k 07171117 n and so we add them all up to get all the possible binary trees on n 1 vertices7 i1e17 Bn1 Ban Banil 39 39 39 BnBO 23137111 k0 Note that this is an example of convolution and when ever we get a recurrence of this type it can often be related back to the Catalan numbers1 More generally we can ask how many trees on n vertices there are We will not answer that question since it is not triviall7 instead we will look at another problem7 how many labelled trees on n there are A labelled tree on n vertices is a tree where we have assigned a label to each vertex7 we will use the labels 7 71 1 1 7 n1 Two labeled trees are the same if and only if vertices labeled 239 and j are adjacent in one tree if and only if they are adjacent in the other tree for all pairs 239 and j1 Again we can start by listing them all for a few small values We have the following ntrees 1 1 2 1 3 3 416 Certainly the rst thing we notice is that there are a lot of labelled trees1 For instance for n 5 there would be 125 which explains why we stopped at 41 It turns out that there is a simple expression for the number of labelled trees on n vertices Cayley s Theorem There are nn 2 labelled trees on n vertices This is certainly a simple expression and the form nn 2 is highly suggestive It is not hard to nd some thing else that has the form nn 27 namely consider words of length me where each letter in the word is in 17 2711 17 One method to prove Cayleyls Theorem is to show that there is a onetoone correspondence between labelled trees on n vertices and these words of length n 7 21 Conveniently enough there is a nice correspondence known as Priifer Codes1 Prilfer Codes Given a labelled tree on n vertices we construct a word using the following procedure For the current tree nd the leaf which has the lowest label7 remove the leaf and write down the label of the vertex that it was adjacent to Repeat this until there are no leafs1 As an example7 consider the following labelled tree on 7 vertices The lowest labelled leaf is 1 and it is adjacent to 21 So we remove the leaf and record 21 We now have the tree The lowest labelled leaf is now 3 and it is adjacent to 2 So we remove the leaf and record 2 so our word is currently 22 We now have the tree The lowest labelled leaf is now 4 and it is adjacent to 6 So we remove the leaf and record 6 so our word is currently 226 We now have the tree The lowest labelled leaf is now 5 and it is adjacent to 2 So we remove the leaf and record 2 so our word is currently 2262 We now have the tree The lowest labelled leaf is now 2 and it is adjacent to 6 So we remove the leaf and record 6 so our word is currently 226261 We now have the tree The lowest labelled leaf is now 6 and it is adjacent to 7 So we remove the leaf and record 7 so our word is currently 2262671 We now have the tree 3 This tree has no leaves note that the only tree with out leaves are the trees on one or fewer vertices and so we stop So this tree is associated with the word 2262671 Now at this point we notice that this has 6 letters In particular this procedure produces a word of length n 7 1 and since each letter in the word is a label on a vertex each letter is one of 1 2 i i i We wanted to have a word of length n7 2 not n71 but let us make an observation In the last lecture we showed that every tree on n 2 2 vertices has a leaf in fact it is easy to show that every tree on n 2 2 vertices has at least two leaves Since we will always be taking the smallest leaf out we will never take out n as we build our code In particular the last letter in the sequence of length n 7 1 must always be n so we can ignore it and just work with the rst n 7 2 digits We see that for every tree that we can make a Priifer code but to be complete we also need to check that there is a onetoone correspondence In particular given a sequence of length n 7 1 where the rst n 7 2 digits are in 1 2 i i i n and the last digit is n we need to be able to construct the tree that it came fromi Deconstructing Prilfer Codes Given a sequence a1amp2 39 39 39 an72an71 where ai E 12iiin forig n72 and an1 n construct the sequence 12le bn1 recursively by letting bi min kl k 1211Hbi1aiuian1i Then form a tree on n labeled vertices with edges joining ai and b fori12 in 71 The idea is that the Priifer code was recording the vertices adjacent to the leaf that we removed if we new the corresponding labels of what was removed then we could form all the edges of the tree So what we are doing with the bi is determining the labels of the leafs that were removed The idea being that bi cannot be one of 121 i i i Ii1 since those vertices were already removed and it cannot be one of ai i i i an1 since they need to stay in the graph after the current step so then bi must be the smallest number not on the list Let us work back through our example above Ap plying the above procedure to the word 226267 we see that the smallest number not seen is 1 so we have 1211 We now cover up a1 and see that the smallest number not seen is 3 so 122 3i We now cover up a and see that the smallest number not seen is 4 so 123 4i We now cover up a3 and see that the smallest number not seen is 5 so 124 5i Lecture 6 7 April 10 As another application of the binomial theorem we have the following FornZl 24 0 k In other words starting with the second row and going down if we sum along the rows alternating sign as we go the result is 0 Given the symmetry it trivially holds when k is odd it is not trivial to show that it holds when k is even Algebraic proof In the binomial theorem set I fl and y l to get n a k0 Combinatorial proof First note that this is equivalent to showing the following lt3gtltZgtltZgtltTgtlt gtltZgt The left hand side counts the number of subsets of 12Hin with an even number of elements while the right hand side counts the number of subsets with an odd number of elements To show that we have an equal number of these two types we will use an involution argument An involution on a set X is a mapping 45 z X A X so that 1 Given an involution 45 the elements then naturally split into xed points elements with z or pairs two elements I f y where y and My as In our case our involution will act on 2 the set of all subsets of 1 2 i i i and is de ned for a subset A as follows Al iflis in A 4514 AUl 1fl 1s not 1n Al In other words we take a set and if 1 is in it we re move it and if 1 is not in it we add it We now make some observations First for any subset A we have A so that it is an involutioni Further there are no xed points since 1 must either be in or not in a set So we can now break the collection of subsets into pairs A Finally by the involution A and 45A will differ by exactly one element so one of them is even and one of them is odd So we now have a way to pair every subset with an even number of elements with a subset with an odd number of elements So the number of such subsets must be equali 1 We now give two identities which are useful for sim plifying sums of binomial coef cients n k l k 7 n n1 nk 7 ltogtlt1gtltkgt and k kl n n1 9 k gtmltkaJ To prove the rst one we will count the number of walks from 0 0 to n1 16 using right steps and up steps in two ways 1k 0 We must make n 1 steps to the right and k steps up So the number of ways to walk from one corner to the other is the number of ways to choose when to make the up steps which is nkl k i We can also count the number of walks by grouping them according to which line segment is used in the last step to the right in the picture above this cor responds to grouping according to the line segment which intersects the dotted line These line segments go from to n li where i 0 i i i b Once we have crossed the line segment there is only one way to nish the walk to the corner straight up the side On the other hand the number of ways to get to n is So by the rule of addition we have that the total number of walks is n 0 n l n 2 n k ltogtlt1gtlt2gtmltkl Combining these two different ways to count the paths gives the identity A proof of the other result can be done similarly us ing the following picture we leave it to the interested reader to ll in the details 7kk1 These identities can also be proved by using i For example we have the following ltZgtltkZ1gt ltZgtltTgtlt211gt lt2gtltnsgtltk1gtlt1gt lt2gtltngtltkgtltgt When I was taught these identities they were called the hockey stick77 identitiesl This name comes from the pattern that they form in Pascalls triangle For instance we have that shown below in blue is the shown below in red The other identity corresponds to looking at the mirror image of Pascalls triangle We now give an application of the hockey stick iden tity if nnl62nl 390 In the rst lecture we saw how to add up the sum ofi by counting dots in two different ways Here we want to sum up i2 the problem is that we don7t have an easy method to do that We do have an easy method to add up the binomial coef cients so if we can rewrite i2 in terms of binomial coef cients then we can easily answer this question So consider the following The ability to rewrite i2 as a combination of binomial coef cients can also be used for any other polynomial expression of if The trick is to nd the coef cients involved For the case of polynomials of the form if we have that the coef cient of is kl i where are the Stirling numbers of the second kind which we will discuss in a later lecturer Now using this new way to write 2392 we have FMS o N m H WM o A Q ION V Jr A HN V V n lnn 71 n ln 2fT 2n 71 3 n ln2n 1 6 i n ln 6 The only dif cult step now is going from the second to the third line which is done using the hockey stick identityl There is a more general form of the binomial the orem known as the multinomial theorem multino mial77 referring to many variables as compared to bi nomial77 which refers to two It states 1112quot391kn n n1 n2 nk E n n ngt1112quot391k7 n1n2 quotkquot 1 27 k nlzomzo mkzo where n 7 nl n1n2iunk nllnglnnkl is the multinomial coef cient we have seen in previous lectures Returning to the binomial theorem we have that 1z In particular for n xed all of the binomial coef cients are stored as coef cients inside of the function 11 In general given any sequence of num bers a0a1a2ui possibly in nitely many we can store these as coef cients of a function which we call the generating function as follows 91a0alzagz2l There are different ways that we can store the se quence as coef cients leading to different classes of generating functions This method is what is known as an ordinary generating function in a later lecture we will see what are known as exponential generating functionsi Generally speaking we will treat the function as a formal series ie as an algebraic rather than ana lytic structure This makes it convenient to work with when we do not need to worry about convergence Nevertheless we will make extensive use of analytic techniques when we do that is when we will start to worry about convergence Let us now consider the problem of nding the gen erating function for the sequence an where k is xed In other words we want to nd a function so that its series expansion note that there are in nitely many an in this case is 99 Zn y We can do this by actually investigating a much more general functioni Namely we will use a generating function with two variables I and y and is de ned as follows it h17yi 1m Using the binomial theorem we have HEW ynltltgtzkgt gynmw ZMHIW n 1 7 1 17y1z 17yizy Note that this function stores the entire Pascalls tri angle inside of it In the above derivation we used the following im portant identity 00 1 1222sz7 Analytically this is true for lt 1 formally this is always true Now to nd our desired gy we are looking for the coefficient of zki So we now rewrite hz y as a power series in z and get 1 7 1 1 m iltlt1eylgtkllzi k0 h if any liyli x H Finally reading off the coefficient for 1k in hz y gives us our desired function name y k 99 Zn Lecture 7 7 April 13 Today we look at one motivation for studying gen erating functions namely a connection between poly nomials and distribution problems Let us start with a simple example Example Give an interpretation for the coefficient of 111 for the polynomi 91 1 12 13 15 Solution First note that we can write 91 as 1z2zgz51z2zgz51z2zgz5 and that a typical term which we will get when we expand has the form 171117121713 where the term 17 comes from picking a term from the rst polynomial so n1 6 0235 the term I comes from pick ing a term from the second polynomial so it E 0235 and the term 1 comes from picking a term from the third polynomial so n3 6 0 2 351 Since we are interested in the coefficient of In then we need n1 n2 n3 111 So this can be rephrased as a balls and bins problem where we are trying to distribute 11 balls among three bins where in each bin we can have either 0 2 3 or 5 balls Example Give an interpretation for the coefficient of IT for the function 91 1zz21zz2 zzgz5 Solution By the same reasoning as we have before a typical term in the expansion looks like 1711171217 with n1 being 0 1 or 2 n2 2 0 and n3 2 0 and even So this can be rephrased as a balls and bins problem where we are trying to distribute 7 balls among three bins where in the rst bin we put 0 1 or 2 balls in the second bin we put any number of balls we want in the third bin we put in an odd number of balls In general given a polynomial 91 91Iy21 9161 with each gi a sum of some power of Is iiei 14 I Then the coef cient of IT in 91 is the number of ways to place 7 balls into k bins so that in the ith bin the number of balls is g for some 1 The idea is that the term tells you the restrictions about the kind of balls that can be placed into that bini It is important that the coef cients of the are all 17s We can also start with a balls and bins problem and translate it into nding the coef cient of some appropriate polynomial Example Translate the following problem into nding a coef cient of some function How many ways are there to put 12 balls into four bins so that the rst two bins have between 2 and 5 balls the third bin has at least 3 balls and the last bin has an odd number of balls77 Solution Since there will be 12 balls we will be look ing for the coef cient of 1121 Now let us translate the condition on each bin For the rst two bins there are between 2 and 5 balls so 91W Q2I I2 ISI4I5 remember the powers list the number of balls that can be put in the bin For the third bin we have to have at least 3 balls so 93113z41 We could also use the function g z zgz4zl27 the difference being that we stop and have a poly nomial instead of an in nite series The reason we can do this is that we are only interested in the co ef cient of 112 anything which will not contribute to that coef cient can be dropped without changing the answer However by keeping the series we can use the same function to answer the question for any arbitrary number of balls and so the rst option is more general Finally for the last bin we have 941z1315m Putting it altogether we are trying to nd the coef cient of 112 for the function 1213z4z5213z4zzsz51 Of course translating one problem to another is only good if we have a technique to solve the second prob lemi So our next natural step is to nd ways to deter mine the coef cient of functions of this type To help us do this we will make use of the following identitiesi 17 m1 1x 1z12 zm 1 1 2 17 lzz forlzlltl 1 nilk k new 2lt k kgo The rst two are simple applications of the binomial theoremi The third is easily veri able by multiplying both sides by l 7 z and simplifying The fourth one is a well known sum and can be considered the limiting case of the third one Note that as a function of 1 ie analytically this makes sense only when lt 11 Formally there is no restriction on I this is because formally 1k is acting as a placeholder To see why the last one holds we note that this is 1 1 1 1 W m ntimes 1z121zz2 n times Translating this into a balls and bins problem the co ef cient of Elk would correspond to the number of so lutions of 1 2 nk where each ei 2 01 We have already solved this prob lem using bars and stars namely this can be done in firk ways giving us the desired result We will need one more tool and that is a way to multiply functions We have the following which is a simple exercise in expanding and grouping coef cientsi Given fr aoa11a212w 91 b0b11b212quot391 Then 9091 a0170 0171 a1b01 aobk albkil akb01k 1 The key is that the coefficient of 1k is found by combining elements aizi bkizk 1 for i 0 i i i kl We now show how to use these various rules to solve a combinatorial problemi Example How many ways are there to put 25 balls into 7 boxes so that each box has between 2 and 6 balls Solution First we translate this into a polynomial problemi We are looking for 25 balls so we will be looking for a coefficient of 125 The constraint on each box is the same namely the between 2 and 6 balls so that the function we will be considering is 91 I2 13 I4 I5 157 1141 z 12 13 14 Here we pulled out an 12 out of the inside which then becomes 114 in front Now since we are looking for the coefficient of I25 and we have a factor of 114 in front our problem is equivalent to finding the coefficient of 1 in gz 1 1 12 13 14 Combinatorially this is also what we would do Namely distribute two balls into each bin fourteen balls in total and then decide how to deal with the remaining 11 Using our identities we have gz 11 12 13 I47 1715 7 1 1 5 77 Hal I 14gt 7 7 7 5 7 10 6k k 6040J Z k kgo Finally we use the rule for multiplying functions to gether to find the coefficient of 111 In particular note that in the first part of the product only three terms can be used as all the rest will not contribute to the 11 coefficient of z 7 So multiplying we have that the coefficient to In is 7 611 7 66 7 61 ltJltugt GX6gtGX1gt This can also be done combinatoriallyi The first term counts the numbers without restriction The second term then takes off the exceptional cases but it takes off too much and so the third term is there to add it back in Lecture 8 7 April 15 We can use the rule for multiplying functions to gether to prove various results For instance let M lt1zgtm amigo lt1zgtmhen fltzgtgltzgt l zm i We now compute the coefficient of IT of in two different ways to get if3lt gt 63 160 k 7 7 k 7 The left hand side follows by using the rule of multi plying and 91 while the right hand side is the binomial theorem for We turn to a problem of finding a generating func tion Example Show that the generating function for the number of integer solutions to 1 2 3 4n with0 61 62 63 64is 1 f lt17zgtlt1ez2gtlt1ez3gtlt17z41 Solution First note that we can rewrite the function as lz12zg1z2z415 gtlt 1zgz 3zg1z4zgzu1 Note that translating this back into a balls and bins problem this says that we have four binsi In the first bin we have any number of balls in the second bin we have a multiple of two number of balls in the third bin we have a multiple of three number of balls and in the fourth bin we have a multiple of four number of balls In other words the generating function counts the number of solutions to f12f23f34f4n with f1 f2 f3 f4 2 0 We now need to show that these two problems have the same number of solutions To do this let us start with a solution of 61626364 n and pictorially represent our solution by putting four row of s with 64 stars in the first row 63 stars in the second row 62 stars in the third row and 61 stars in the fourth rowi Finally let f4 be the number of columns with four s f3 the number of columns with three s f2 the number of columns with two s and f1 the number of columns with one 9a This gives a solution to f1 2f2 3f3 4f4 n This gives a onetoone correspondence between solutions to the two different problems so they have an equal number of solutions giving the result As an example of the last step suppose we start with 35911281 Then pictorially this corresponds to the following picture we have marked the number of s in each row column 1 11 9 5 3 44433222211 So translating this gives us the solution 2 24 32 43 28 to the second problemi This problem says that the number of ways to break n into a sum of at most four parts is the same as the number of ways to break n into a sum of parts where each part has size at most fouri We will generalize this idea in the next lecturer For now we start by looking at partitions A partition of a number n is a way to break n up as a sum of smaller pieces For instance 111111213224 are the ways to break four into pieces We do not care about the order of the pieces so that l l 2 and l 2 l and 2 l l are considered the same partitioni This corresponds to the number of ways to distribute identical balls among identical bins for now we will suppose that we have an unlimited number of bins so that we can have any number of parts in the partition Let pn denote the number of partitions of n n partitions ofn pn 0 0 l l l l 2 11 2 2 3 111 12 3 3 4 111111213 5 22 4 5 lllll lll2 7 11312214 23 5 6 llllll ll llll2 lll3 1122114123 15 222 24 33 6 The function pn has been well studied but is highly nontrivial One of the greatest mathematical geniuses of the twentieth century was the Indian math ematician Srinivasa Ramanujani Originally a clerk in India he was able through personal study discover dozens of previously unknown relationships about par titionsi He sent these along with other discoveries to mathematicians in England and one of them G1 H1 Hardy was able to recognize the writings as some thing new and exciting which caused him to bring Ra manujan to England which resulted in one of the great mathematical collaborations of the twentieth century Examples of facts that Ramanujan discovered include that p5n 4 is divisible by 5 p7n 5 is divisible by 7 and plln 6 is divisible by 111 One natural question is to whether the exact value of pn is known There is a nice formula for pn name y 1 d Sinh1I2 14 1071 i ZAMnME where Ak is a specific sum of 24kth roots of unity Proving this is beyond the scope of our class We now turn to the much easier problem of finding the generating function for pn that is we want to find 2 n20 The first thing is to observe that a partition of size n corresponds to a solution of 12523 3quot39k k 39 717 where each ei represents the number of parts of size i1 Notice in particular the the contribution of 6k will be a multiple of k1 So turning this back into balls and bins we have n balls and infinitely many binsi So the number of solutions using what we did last time is Zpnzn lzz2zg x gt0 e1 term gtlt 112z415 gtlt 11315I9 e2 term e3 term gtlt gtlt 1zk12kzgkX1 ek term Since l 7 2k 7 we can rewrite the generating function as 1Zkz2kzskm l l l l n 7 7777 gmn 7 17117121713 171k 1 HW 321 We can do variations on this For instance we can look at partitions of n where no part is repeated In other words we want to restrict our partitions so that ek 0 or 1 for each kl If we denote these partitions by pd then 2mm lt1zgtlt1z2gtlt1zkgt n20 Hawk k21 Similarly we can count partitions with each part oddi In other words we want to restrict out parti tions so that 62k 0 for each kl If we denote these partitions by p0n then it is easy to modify our con struction for pn to get 1 Emm H1 1241 n20 kZI We can combine these two generating functions to derive a remarkable resulti For n 2 1 we have pdn p0ni Remarkably we do not know in general what pd or p0n is nevertheless we do know that they are equal As an example of this we have that 1006 4 because of the partitions 11111L 1113 15 33 while pa 6 4 because of the partitions 123 15 24 6 1t suffices for us to show that the two generating functions are identical 1f the functions are the same then the coefficients must be the same giving us the desired result So we have that Zpdm HO 116 n20 kgi 2k 171k kgi 1712171417151718 171171217131713 1 1 1 171171339171539H 1 H 1 12171 Emm n k21 n20 We can also give a bijective proofi To do this we need to give a way to take a partition with odd parts and produce a unique partition with distinct parts and vice versa This can be done by repeatedly apply ing the following rule until it cannot be done anymore 0 With the current partition if any two parts are equal combine them into a single part For example for the partition 111111 21111 2211 411 42 A A A A This rule takes a partition with odd parts and produces a partition with distinct parts To go in the opposite direction this cane be done by applying the following rule until it cannot be done anymore 0 With the current partition if any part is even then split it into two equal parts For example for the partition 346 A 2236 a 11236 a 111136 a 1111333 These two rules give a bijective relationship between partitions with an odd number of parts and partitions with distinct parts Lecture 9 7 April 17 We can visually represent a partition as a series of rows of dots much like we did in the example in the previous lecturei This representation is known as a FerreT s diagrami The number of dots in each row is the size of the part and we arrange the rows in weakly decreasing order The partition 4 3 11 would be represented by the following diagrami We can use Ferrer s diagrams to gain insight into properties of partitions For instance one simple op eration that we can do is to take the transpose or the conjugate of the partition This is done by flip ping77 across the line in the picture below so that the columns become rows and rows become columnsi o l o a o ob a o 0 ix 00 Since we do not change the number of dots by taking the transpose this takes a partition and makes a new partition So in this case we get the new partition 4 2 2 1 Note that if we take the transpose of the transpose that we get back the original diagrami There are some partitions such that the transpose ofthe partition gives back the partition such partitions are called self con jugatei For instance there are two self conjugate par titions for n 8 namely 4211 and 332i A famous result says that the number of self conjugate partitions is equal to the number of partitions with distinct odd partsi So for example for n 8 there are two partitions with distinct odd parts namely 7 1 and 5 3 One proof of this relationship is based on using Ferrer s diagrams We will not ll in all of the details here but give the following hint for n 8 o o o o r Also note that when we take the transposition that the number of rows becomes the size of the largest part in the transposition while the size of the largest part becomes the number of rows So mapping a partition to its transpose establishes the following facti There is a onetoone correspondence between the number of partitions of n into exactly m parts and the number of partitions of n into parts of size at most m with at least one part of size ml It is easy to count partitions with parts of size at most m with at least one part of size ml In particular if we let l denote the number of partitions of n into exactly m parts then we have using the techniques from the last lecture 7L1 m I39m 7 7 2 7 m 20 lt1 zgtlt1 z lt1 z gt Another object associated with a Ferrer s diagram is the Durfee square which is the largest square of dots that is in the upper left corner of the Ferrer s diagrami For example for the partition 6 6 4 3 2 11 we have a 3X3 Durfee square as shown in the following picture It should be noted that every partition can be de composed into three parts Namely a Durfee square and then two partitions one on the right of the Durfee square and one below the Durfee square as illustrated belowi i gtlt i partition with square at most 139 parts quotEa 30 ES 04 7 56 7m g 156 a If we group partitions according to the size of the largest Durfee square and then use generating func tions for partitions with at most 239 parts and partitions with parts at most 239 which by transposition are the same generating function we get the following iden tity 2 n 1 7 1 MW 7 Hanging n20 n20 squarek1 k1 left bottom partition pamuon Z 7 2 7 22 7 n2 n201z1 z 1 I There are a lot more fascinating and interesting things that we can talk about in regards to partitionsi We nish our discussion with the following H1izi172722252772127215ltH n21 Z 1izs jgt2 fooltjltoo This is very similar to what we encountered in the previous lecture namely H1 We saw that this last expression was used to count the number of par titions with distinct parts In the current expression something similar is going on the difference is that previously every partition of n with distinct parts con tributed 1 to the coef cient of I now the contribu tion of a partition of n with distinct parts depends on whether the number of parts is even or odd Namely if the number of parts is even then the contribution is 1 and if the number of parts is odd the contribution is 71 In particular it is not hard to see that H 1 Ii 2 EM 001 n21 n20 where is the number of partitions of n into an even number of distinct parts and 0n is the num ber of partitions of n into an odd number of distinct partsi So to determine the product we need to deter mine 7 0n7 we will see that this value is 71 or 1 To do this we give a bijection between the num ber of partitions of it into an even number of distinct parts and the number of partitions of it into an odd number of distinct parts This is done by taking the Ferrer s diagram of a partition into distinct parts and comparing the size of the smallest part call it 4 and the size of the largest 45 run in the upper left corner call it T 1f 4 gt T then take the points from the 45 run and make it into a new part 1f 4 2 T then take the smallest part and put it in at the end as the 45 runi An example of what this is doing is shown belowi 1n the partition on the left we take the smallest part and put it at the end of the rst few rows while in the partition on the right we take the small 45 run at the end of the rst few rows and turn it into the smallest part 000 000000 a oooooooy 000 000000 on m E In particular this gives an involution between par titions of it into an odd number of distinct parts and partitions of it into an even number of distinct parts All that remains is to nd the xed points of the in volution7 namely those partitions into distinct parts where this operation failsi It is not too hard to see that the only way that this can fail is if we have one of the two following types of partitions 1n the one on the left we have 4 T but we cannot move 4 down to the 45 line because of the overlap 1n the one on the right we have 4 lt T but if we take the points on the 45 line it will create a partition which does not have distinct parts Counting these exceptional cases are partitions of size 3139 i j 2 1 Putting all of this together along with a little bit of playing with terms explains the form of the product This is known as Eulerls pentagonal theorem be cause the numbers that come up in the powers with nonzero coef cients are pentagonal numbers which can be formed by stacking a square on top of a tri angle 1 The pentagonal theorem has a nice application which is useful for quickly generating the number of partitions of no We have 1001 10011on2Pn5710n7 where the terms on the right hand side are those from the pentagonal theoremi This follows by noting that 1 g kgwo ltpnzngtlt Z 1jz312jgt2gt fooltjltoltgt Now using the rule for multiplying functions together and comparing coef cients on the left and right hand sides we see that for n 2 1 that 0 100170ni1Pn2pn5pni7 7 rearranging now gives the desired result We now return to generating functions The type of generating functions that we have encountered are what are called oninaTy geneTating functions which are useful in problems involving combinationsi But there is another class of generating functions known as exponential geneTating functions which are useful in problems involving arrangementsi T eof eneratin yp g g form used to count nctlon ordinary E anzn combinations n20 In exponential E uniy arrangements no n20 The term exponential comes from the fact that if a1 a2 1 then the resulting function 1s In 24765 n21 no A typical problem involving combinations looks at counting the number of nonnegative solutions to an equation of the form n1n2quot39nkn where we have restrictions on the nil In particular for each solution that we nd we add 1 to the count for the number of combinations For arrangements we start with the same basic problem7 namely we must rst choose what to arrange so we have to have a non negative solution to an equation similar to the form n1n2quot39nkn where again we have restriction on the nil But now after we have chosen our terms we still need to arrange or order themi From a previous lecture if we have n1 objects of type 1 n2 objects of type 2 and so on then the number of ways to arrange them is nl nllngl nkl7 so now for each solution to n1 n2 nk n this is what will be contributed to the count for the number of arrangements The exponential function is perfectly set up to count the number of exponential functions To see this consider 2W2 2 651 652 65k where S is the possible values for nil Then a typical product will be of the form x 1 x 2 x nTl39ngl nkl if n1n2 nk n then the contribution to xnnl 1s nl x n1ln2l nkl l the number of arrangements just like we wanted Let us look at two related problems to compare the differences of the two types of generating functionsi Example Find a generating function which counts the number of ways to pick it digits from 0s 1s and 2s so that there is at least one 0 chosen and an odd number of 1s Solution Using techniques from preVious lectures we have that the ordinary generating function is xx2x3 xx3x5 1xx2 x x 1 x2 17x17x217x17x31x Example Find a generating function which counts the number of ternary sequences sequences formed using the digits 0 1 and 2 of length n with at least one 0 and an odd number of 1s Solution This problem is related to the preVious except that after we pick out which digits we will be using we still need to arrange the digits So we will use an exponential generating function to count thesei In our case we have I3 5 x7 7x e75 71e1 e3 7 e27 7e 71 2 3 5 2 z7z 271z127 Note that the approach is nearly identical for both problems the only difference in the initial setup for the generating functions is the introduction of the fac torial termsi So the same techniques and skills that we learned in setting up problems before still holds The only real trick is to decide when to use an expo nential generating function and when not to use it In the end it boils down for now to whether or not we need to account for ordering in what we choose If we don7t then go with an ordinary generating function if we do go with an exponential generating function Lecture 10 7 April 20 In the last lecture we saw how to set up an expo nential generating function to solve an arrangement problemi As with ordinary generating functions if we want to use exponential generating functions we need to be able to nd coefficients of the functions that we set up To do this we list some identitiesi 7 bob ip 160 k exe7x 12 I4 16 2 1 IHm 6x764 3 5 7 T z m k 2 3 n71 kzni i i n7 Example Find the number of ternary sequences se quences formed using the digits 0 1 and 2 of length n with at least one 0 and an odd number of 1s Solution From last time we know that the exponen tial generating function gx which counts the number of ternary sequences is 1 am w7w7e4gt 1 x x x 7 lt23ng722ng7zg71gt n20 n20 n20 1 n 2437172717 1 2 nl ngt1 So reading off the coefficient of xnnl we have that the number of such solutions is 3 7 2 7 12 for n 2 1 and 0 for n 0i Lecture 16 7 May 6 We now return to some good old fashioned countingi We will be looking at setsi We have a collection of elements and we will let M denote the univers of all possible elements for the problem that we are counting We will let A denote a subset of M lAl denote the number of elements in the set A and A MA denote the complement of A the set of all elements in M not in A Since every element is either in A or not in A we can conclude Wl W W Pictorially we have the following picture This is a simple example of a Venn diagram which gives a visual way to represent setsi We will look at Venn diagrams for l 2 and 3 sets after that it gets more dif cult to draw Venn diagrams but not impos sibleli Example There are 35 students in the class If 15 students come to of ce hours then how many student s didn t come Solution The set M is the set of all students A the set of students who came to of ce hours so by the above formula we have 2 M7 lAl 35715 20 Not surprisingly there is not much interesting to do with only one set So now let us consider the situation when we have two set A and B The Venn diagram for this situation is shown belowi Notice that this picture implies the possibility that the sets intersecti We do this because we ant Venn diagrams to be as general as possible so the actual intersection can be empty do not assume that sets always intersecti We let A U B denote the union of A and B where AUBzleAorzEB and A N B denote the intersection of A and B where A BzlzeAandz Bi de Morgan s laws A B AUB M M D C Dal Dal ln words de Morgan7s laws says that the complement of the union is the intersection of the complements and that the complement of the intersection is the union of the complementsi To prove A N B A U B we show that they have the same elements rem gt z A B ltgt z Aorz B 42gt zerrzEB 42gt zeAUB The other half of the law is proved similarly Suppose that we wanted to count the number of el ements in lA U Bl a natural rst guess is lAl The problem is that we are double counting elements in the intersection of A and B so we need to correct this overcounting by subtracting out So we have lAUBl lAl lBl ilA Bli We can also count this by breaking A U B into three pieces namely A NB elements in A but not in B A B elements in A and in B and A N B elements not in A but in B So we also have lAUBl AnFHlAmBHZnBl We now turn to the three set case This is illustrated in the Venn diagram belowi Notice that we have split M into eight pieces which is what we should expect because we are either in or not in each of the three sets The eight pieces are A B m0 A B C A F C Armin Z B m0 XmB C ZmF C Erwin The last set by de Morgan7s law is Z F C A U B U C which are the points outside of the sets A B and Cl Similarly as with the two set case we may want to count the union of the sets and as before we have to be careful not to overcounti So we have lAUBUCllAllBllCl ilA BlilA ClileCHlAmBmCl Example At a local college there is a language pro gram which has the three languages Russian R Chi nese C and Java There are 34 students attend ing the Russian class 31 students taking the Chinese class 36 students taking the Java class 13 students taking both Russian and Chinese 9 students taking Russian and Java and 11 students taking Chinese and Java When this is reported to the dean they look at it and say Wait 1 also need to know how many stu dents are in all three77 How many students attend all three classes Solution Thinking ofthese as sets thenwe are looking for 1R N C N Jli Plugging in the information we have into the formula above we have 7334313671379711lR C Jl 68lR CmJli So lR C Jl 5 ie there are 5 students taking all three classes Example How many it digit ternary sequences with at least one 0 one 1 and one 2 Solution Let us use sets to represent the situation Let A denote the set of sequences without 0 B denote the sequences without 1 and C denote the sequences without 2 We could alternatively let them denote the sets with the elements but this is more fun Phrased this way we are looking for lZmFOUl lAUBfCl ZlilAUBUCL On the one hand we have 1A1 lBl lCl 2 since elements in these sets are formed only using two let tersi We also have lA Bl lA Cl lB Bl 1 since elements in these sets are formed only using one letter so they look like 000 0 1111 and 222 2i Fi nally we have 1A N B N Cl 0 since we don7t have any letters to form the sequencer Putting this altogether we have ZnFna 3 L 32 73103 732n3i It is always a good idea to check so let us try 0 plug ging it in we get 1 but that is not the right answer we should have gotten 0 there are no sequences of length 0 with at least one 0 one 1 and one 2 So where was our mistake Looking back over what we did we see that lA B Cl will be 1 when n 0 and 0 otherwise This is because the empty string the string with no letters has no 0 no 1 and no 2 and so is an element in lA B Cli So if we put this back in we see that we do get the correct answer So we have that the number of such ternary sequences is 3 732 3 ifnZl 0 ifn0i What we have just done is a simple example of a more basic principle InclusionExclusion Principle Let A1A2 i i 1 An Q Hi Then KNEWmm WM Zen 2 I n 121 A1 jEI Before we try to prove this we rst should work on trying to understand what this says We have 2 i i i n so what we are doing is summing over all nonempty subsets of What this is really doing is summing over all possible ways that we can intersect the sets Ail Where we either add or subtract based on how many sets we are intersecting For example for n 3 this corresponds to the following lATNTmATl Wli VM 7 lA2l 7 lAsl v 11 12 I3 lA1 A2llA1 AgllA2 Agl 112 113 12s ilAl Ag Agli W Since lAlUAQU UAnl MAW lulilAimAi WAT we automatically have the following variation of the inclusionexclusion princip ei InclusionExclusion Principle U Let A1A2HiAn Q Hi Then AluAgunuAnl E 70 1quot1 Igm 1w m A1 jEI The proof of the inclusionexclusion principle is based on a binomial identity that we encountered ear lier namely m m 1 ZHN 160 k 0 The way to do this is to go through every element in M and see how many times it gets counted on each side of the equation We have two cases to consider ifm0 ifmZ 1 o z E lAil Aig 39H Ainl note that z is in none of the sets Ail On the left hand side this gets counted and so contributes 1 On the right hand side this gets counted when we look at the term VA and since it is in none of the Ai it will not get counted any other time so the total contribution is 1 z lAil Aig 39 Ainl now I is in some of the sets Ai let us suppose it is in m setsi On the left hand side this does not get counted and so contributes On the right hand side this will get counted many times once for the VA then times for each subset it is in then times for each pair of subsets it is in then times for each triple of subsets it is in and so on In particular the contribution on the right hand side using signs 1ltigtlt21gtlt2gtc0 In both cases the left and right sides are equal for each element establishing the result Lecture 17 7 May 8 We now look at some applications of how to use the inclusionexclusion principlei A classic example is counting derangement A derangement can be thought of as a permutation a function 7r A with no xed point an i so that This is of ten rephrased as a hatcheck problem where it people go out to eat and check in their hats but when they leave the person in charge of giving back their hats has forgotten who goes with which hat and so gives them back randomly a derangement then corresponds to the situation where no person gets their own hat back Example How many derangement on n elements are there Solution To use the inclusionexclusion principle we want to rst identify the sets Ail There are many possibilities but we keep in mind two criteria First we want to nd the intersection of the complement of the Air Second we want to nd sets which are easy to count when we look at their intersectionsi Given these two criteria we are led to Ai ith person gets their hat so that Ai denotes arrangements where Ai does not get their hat backi Since no one should get their hat back we want to look at the intersection of these sets So the number of derangements is Z E fnl M Z 71 l Aj ISM jEI 121 Going through these terms we have VA is the number of ways to distribute the hats which is nli Now let us consider a term of the form jeIAji This corre sponds to arrangements that are simultaneously sat isfying that elements in I get their hat back The remaining n ij can be distributed arbitrarilyi So we 3V6 A1 jeI lmportantly we see that the only thing that is im portant is the number of elements of I and not which elements they are If we now group the sum by the size of the index set we have n7 um Ail Aj annl law 2 71 l 1 n 121 A1 jEI n n n 7 k nlZilkltkgtniklan k1 161 160 Then term shows up because there are ways to choose 10 out of 71 sets to intersect Note that the sum that shows up in the number of derangements looks familiar1 In particular since ex DOE i we have DOE e71 7 kl kl 7 160 160 So the number of derangements is m nle1 In fact it can be shown that the number of derangements is the integer nearest to nle1 Using this we can conclude that the probability that if we collect hats from 71 people and redistribute them randomly that no one gets their hat back is W Va Example Suppose that there are 71 couples that go to a theatre and sit in a row with 271 chairs a How many ways can the couples sit down if each person sits next to the person they came with b How many ways can the couples sit down if no person sits next to the person they came with Solution For part a we think of pairing the couples together and then arrange the couples which can be done in 71 ways1 Now each couple sits down and we need to decide who sits on the left and who sits on the right which can be done in 2 ways per couple so in total there are 27171 ways for the couples to sit down For part b we use inclusionexclusion1 If we let Ai seatings with 2th couple together then what we are looking for is X1 X2 A7 just right for inclusionexclusion1 The total number of ways to seat the 271 people is 2nl1 Now let us focus on a term of the from jejAJx This corresponds to the situation where the couples in I are sitting together and maybe some more as well1 To count this we now think of there as being lIl couples and 2717 2m singles for us to arrange or combined 271 7 lIl people to arrange Once we are done arranging the order of the people we then again have to decide for each couple who sits on the left and who sits on the right So altogether we have that H A1 jEI 271 711012 1 1 Again it is important that it is the number of elements in I and not which elements in I that matters So as in the last example if we group by the size of the index set we have A1 jEI Ail Aig n Ainl 1111 Z 71 l El 2n1n1k 271716121c H g gtkgtlt gt 71 Zap 271 7 1011 160 k Again the term shows up because there are ways to choose 10 of the 71 sets to intersect Also we can absorb the 271 term into the sum since this cor responds to the case 10 01 Unfortunately there does not seem to be any nice way to condense this formula but at least we have a way to count it Using a computer we see that 8 2401382412633601684224001111 v v V W W 711 712 713 714 715 716 Finally let us look at some more variations of the inclusionexclusion principle Variation of the InclusionExclusion P nciple Let A1A2111An Q 1 and let Bm z in exactly 712 of the Ai1 Then AJ 161 lel 2 70111471073 Igm mzm The case B0 where we translate the empty intersec tion as the entire M gives us back the original form of the inclusionexclusion principle1 Our method to prove this is similar as before namely to consider cases for individual elements in M and show that each elements contributes the same to both sides 0 z in fewer than 712 of the Ala In this case z Bm so the contribution on the left is 0 while on the right it will not show up in any of the intersections and so its contribution is again 01 o z in exactly 712 of the Ala In this case I E Bm so the contribution on the left is 1 while on the right it will show up exactly once namely in the intersection of the 712 sets it lies in It cannot show up in any other term so the contribution on the right is 11 o z in 7 gt m of the Ala In this case z Bm so the contribution on the left is 01 While on the right it will show up times in the intersection of m sets r mil times in the intersection of ml sets 2 times in the intersection of m 2 sets i H In particular the contribution on the right hand SI ES ltigtltm11gt lt22 ltm2gtltm2gt Digging back to when we practiced identities for binomial coef cients we nd the identity Ggt So applying this to our situation we have MM fgt In particular we can rewrite our sum where we use this identity on every term and factor out the now common to get that the contribution on the right is T T 7 m T 7 m T 7 m m 0 1 2 which by the same reasoning as last time is 0 Closely related to this we have the following VaTz39atz39oTL 0f the InclusionExclusion PTz39Tch39ple U Let A1A2 i An Q U and let Cmzl zin atleastmofthe Ai Then 7 lIl7m lIlil le 21 m1 Igm m2 A1 jEI The case m 1 corresponds to the variation that we gave in the last lecturer We will not give the proof here This brings us to the end of the enumerative com binatorics part of the course Starting with the next lecture we turn to graph theory Lecture 18 7 May 11 We now start a new area of combinatorics namely graph theory Graphs are at a basic level a set of ob jects and connections between themi As such they can be used to model all sorts of real world and mathemat ical objects We start with some of the basic properties of graphs A gTaph G consists of two sets a vertex set V and an edge set E we sometimes will write this as G The vertex set represents our objects and the edge set represents our connections between objects we will visually denote vertices by 077 The edge set can have several different ways of describing how we connect vertices which leads to different types of graphs The most common are 0 The set E consists of unordered pairs of vertices iiei uvi These graphs are the most studied and are known as undiTected gTaphsi Visually we represent the edges as 77 The set E consists of an ordered list of two ver tices iiei u 1 These graphs are known as di Tected gTaphsi Visually we represent the edges as c 77 o The set E consists of subsets of vertices usually of some xed size ie v1 v2 i i 11k These graphs are known as hypeTgTaphsi These are hard to rep resent visually perhaps this is one of the reasons that we do not study them as much in beginning combinatoric coursesi Usually when we think of a graph we do not think of two sets but rather as a visual drawing of points and lines connecting the points This is great for building intuition but can also be deceiving in that the same graph can be drawn in many different ways we will look at this problem shortlyi Another problem is that many graphs that are interesting have a laTge number of vertices in the billions so that if we were to draw them as points and lines the end result would be a black piece of paper So it is good to be able to not have to rely on pictures An example of an undirected graph is a handshake graph which corresponds to a party with several peo ple present and we connect an edge between two people if they shake hands As a graph the vertices are the people and the edges correspond to handshakes Be cause there is symmetry in the relationship ie if I shake your hand you also shake mine the undirected graph is the appropriate one to use These also can be used to model social networks in addition they are fre quently used to model groups these graphs are known as Cayley graphsi An example of a directed graph is the internet some times known as the web graphi Here every vertex cor responds to a webpage and edges are hyperlinks from one webpage to another webpagei Because there does not have to be symmetry ie I might link to awebsite about kittens but that does not mean the kitten web site links to me the directed graph is the appropriate one to use The web graph is one of the most stud ied and probably one of the most lucrative graphsi Companies such as Google make a lot of money mining information from this graph An example of a hypergraph is the Fano plane This is the smallest discrete geometry it consists of seven points seven lines where each line contains exactly three points any two lines intersect in exactly one point and any two points are contained in one unique line This is shown belowi We can represent the Fano plane as a hypergraph by letting the points of the Fano plane be the vertices and the edges of the hypergraphs be the lines So in this case every edge consists of three points One reason that we do not study hypergraphs is that we can model them using undirected bipartite graphsi A graph is bipartite if the vertices can be split into two parts V UUW where U and W are disjoint and such that all the edges in the graph connect a vertex in U to a vertex in W1 A hypergraph G E can then be associated with a bipartite graph H VUE 5 where 5 connects v E V to e E E if and only if the vertex v is in the edge e So for example the hypergraph for the Fano plane can be represented using the following bipartite graph where points are on the top lines are on the bottomi While not as nice a picture as the Fano plane it still has all of the same information and we can still use it to determine properties of the Fano plane Because of their ability to model interaction between two groups bipartite graphs are an important area of study in graph theory As another example suppose that we want to model the social interaction between a group of ve boys and ve girlsi There have been various relationships formed over the years and some people get along great and have fun dating while other couples don7t work at all We can model this by a bipartite graph where on the left we have the girls on the right we have the boys and we put an edge between two people if they can date Suppose that doing this we get the graph shown below on the left We might then ask the question is it possible for all the people to have a date for this Friday In this case we need to nd a way to pair people up so that every person is in exactly one pairing and they get along with the person they are paired with So looking at the graph we see that the rst girl would have to be paired with the second boy the second and fourth girls would then decide how to go with the rst and third boys while the third and fth girls would then decide how to go with the fourth and fth boysi In particular there are four ways that people can be paired up for dates we show one of them above on the right This is an example of a matching A matching of a graph is a subset of edges so that each vertex is in exactly one edge Note that this de nition does not require the graph is bipartite 1n the graph above there is a matching but not all graphs have matchingsi For example consider the following graphi It is easy to see that there is no way to match up the vertices in this graph since there is an odd number of vertices if there were a matching then the number of vertices would have to be a multiple of two This graph is a special type of graph known as a cycle A cycle on n vertices denoted On consists of the vertex set 121 1 i n with edges ii1 for i 1 i i i n71 and Lil If we do not include the last edge the 1 then the graph is a path on n vertices denoted P W Another well studied graph is the complete graph Kn which consists of the vertex set 12 l i i n and has all possible edgesi Since edges consist of subsets of size two then there are edges in the complete graph The graph K5 is shown below on the left Closely related to the complete graph is the com plete bipartite graph Kmm which has as its vertex set v1 1 i i vmu1i i i an and as edges all edges of the form 1 uj In other word we have a bipartite graph with one part of size m one part of size n and all pos sible edges going between the two parts so in total mn edges The graph 34 is shown above on the right One of the most famous graphs the Fabio of graph theory if you will is the Petersen graph This graph consists of 10 vertices and 15 edges as shown belowi This graph is a classic examplecounterexample to many problems in graph theory and is a good graph to have around when testing a new idea we will use this as an example in a later lecturer Another important graphs are hypercubes Q7 here the hyper refers to high dimensions these graphs are not themselves hypergraphsi The vertex set of these graphs consist of all binary strings of length n so that there are 2 vertices Two vertices are con nected if the strings differ in exactly one entry So for example Q1 consists of vertices 0 and 1 with an edge connecting them Q2 consists of the four vertices 00 01 10 and 11 and form a four cycle note that there will be no edge connecting 00 and 11 since they dif fer in both entries and similarly no edge connecting 01 and 10 The graph Q3 is shown below you should try to label the vertices with the eight binary strings of length three that would give this graph The name hypercube comes from the idea of the vertices denot ing the corners of an ndimensional cube sitting at the origin because binary strings are used in computers these graphs frequently arise in computer science Note that the hypercube is a bipartite graph To see this we need to tell how to break up the vertices into two sets so that edges go only between these sets This is done by letting U be the set of binary strings of length n with an odd number of 1s and W the set of binary strings of length n with an even number of 1s Since an edge connects two vertices which differ by exactly one entry we will either increase or decrease the number of 1s by one so that edges must go between U and W1 Let us now look at how many edges are in the hyper cubei Before we do that we rst need a few de nitions Two vertices u and v are adjacent if there is an edge connecting them this is denoted as uwvi An edge e and a vertex v are incident if the vertex v is contained in the edge e pictorially the edge connects to the ver texi The degree of a vertex is the number of edges incident to the vertex equivalently the number of ver tices adjacent to the vertex assuming we do not allow loops and multiple edges we denote the degree of a vertex by d1 or v 1 1n the hypercube graph Qn every vertex corresponds to a string of length n To connect to this vertex we must differ in exactly one letter since there are n pos sible letters then there are n different vertices that connect to the graph In other words every vertex in the graph has degree no If we add up all the degrees then we get n2 But adding up all the degrees we will count each edge exactly twice so that twice the num ber of edges is n2 or the number of edges is n2n 1i As an example in Q3 there are 322 12 edgesi A graph where all of the vertices have the same de gree is known as a regular graph The Petersen graph is a regular graph of degree 3 the hypercube is a reg ular graph of degree n the complete graph Kn is a regular graph of degree n 7 1 and the cycle On is reg ular of degree 2 Of course there are many others regular graphs have nice properties particularly when approaching graphs using linear algebra Looking at our derivation for the number of edges in Qn we noted that by adding up the sum of the degrees that we got twice the number of edges This is the rst theorem of graph theory Handshake Theorem For a graph G let denote the number of edges then Eda 2113 veV In particular this implies that the sum of the degrees must be an even num err So we have the following immediate corollaryi Corollary of the Handshake Theorem The number of vertices with odd degree must be even Example Does there exist a graph on six vertices where the vertices have degree 1 2 3 3 4 4 Solution Nor Summing up the degrees we get 17 which is an odd number but by the handshake theo rem if such a graph existed the sum would have to be even Of course just because the sum of the degrees of a graph is even does not mean that a graph existsi Example Does there exist a graph on six vertices where the vertices have degree 1 2 3 4 5 5 Solution Nor Summing up the degrees we get 20 so the handshake theorem does not rule it out However if there were such a graph then it would have two vertices of degree 5 in particular these two vertices would have to be adjacent to every vertex in the graph Or put another way every vertex in the graph would have to be adjacent to the two vertices of degree 5 but this would imply that no vertex can have degree less than 2 in particular we could not have a degree 1 vertex as desired Finally we turn to a problem mentioned earlier Namely we like to represent graphs visually but the way that we can draw the graph is not unique as we can place vertices where we like and draw edges as we want For example consider the following two graphs 5 4 C These graphs have the same number of vertices 7 the same number of edges 14 all the degrees are the same but are they two different drawings of the same graph or two different graphs altogether To answer this question we have to decide what we mean to say that they are the same graph or rather they have the same structure We say two graphs G and H are isomorphic iso same mor phic77 structure if there is a bijective oneto one and onto map 45 VG A VH so that uv in G if and only if in Hi Or in other words we can map the vertices of one graph to the other in a way that preserves adjacency n terms of the picture above the question is can we relabel the vertices of one graph and produce the other graphi Careful checking will see that if we relabel as follows1gt gta2Hc3gt gte4gt gtg5gt gtb6gt gtdand 7 gt gt f then we preserve adjacency In other words these two graphs are isomorphic so are two drawings of the same graphi To show that two graphs are isomorphic then it suf ces for us to nd a way to relabel the vertices of one graph to produce the other graphi To nd a rule for relabeling we often try to identify some vertices that must be mapped one to the other ie because of de gree considerations and slowly build up the relation sh39 To show that two graphs are not isomorphic we need to nd some structure that one graph has that the other does not showing they cannot be the same graphi We will pick this topic up again in the next lecturer Lecture 19 7 May 13 Our main focus in graph theory will be simple undi rected graphsi Simple graphs refer to graphs without loops or multiple edgesi A loop is an edge that con nects a vertex to itself ie multiple edge is several edges going between the same two vertices iiei In other words we want to eliminate the possibility of having a repeated element in our sets A useful technique in proving statements is proof by contradiction The underlying idea is to assume the opposite of what we are trying to prove and show that this leads to an impossible situation This implies that our assumption is wrong well our assumption was the opposite of what we are trying to prove so this means what we want to prove is true In other words we are proving something is not not true Example Show that in any simple graph on two or more vertices there must be two vertices which have the same degree Solution Suppose that it is not true iiei suppose that there is a graph where all vertices have different degrees Also for convenience let us suppose that we have n vertices Then the possible degrees in the graph are 01i i n7 1 Since there are n vertices it possible degrees and all of them are distinct this implies that we must have 0 a vertex of degree 0 ie a vertex not connected to any other vertex and o a vertex of degree n 7 1 ie a vertex connected to every other vertexi But clearly we cannot have both of these vertices in the same graphi Therefore our assumption is false and in particular there must be some two vertices with the same degree In the last lecture we looked at telling if two graphs were isomorphici We saw that the way to show that two graphs were isomorphic was to produce a bijective 45 VG A VH that preserves adjacencyi But now suppose that we want to show that two graphs are not isomorphici To do this we need to nd some structure that one of the graphs have that the other doesn7ti Some possibilities to look for o If the graphs are isomorphic they must have the same number of vertices and the same number of edges 0 The two graphs must have the same degree se quences ie the list of degrees 0 The complement of the graphs must be isomor phici 0 Both graphs must either be connected of not con nected o If the graphs are isomorphic then if G has a sub graph K H must also have a subgraph isomorphic to K i These are only a few of the possibilities of things to look for The list is nearly endless of things to look for The nice thing is that to show two graphs are not isomorphic we only need to nd a single property they donlt agree on so we usually don7t have to go through the whole list of possibilities to show graphs are not isomorphici We have introduced a few terms on this list that we need to go over The complement of a graph G de noted 5 is the graph with the same set of vertices of G and all edges not in Ci So for example the complement of Km would consist of a Km and Kn with no edges between the two complete graphsi As another exam ple consider the complement of the Petersen graph since K10 has degree 9 and the Petersen graph has de gree 3 then the complement will be regular of degree 6 and so in particular will have 30 edges we won7t draw it On a side note the complement of the Pe tersen graph is the complement of the line graph of K5 but that is another story If graphs have many edges sometimes it is easier to work with the complements which can have fewer edgesi A subgraph of a graph G V E is a graph H where V E V and E E El So for example a path on n vertices is a subgraph of a a cycle on n vertices which in turn is a subgraph of Kn in fact every graph on n vertices is a subgraph of A graph is connected if between any two vertices we can get from one vertex to another vertex by going along a series of edges That is for two vertices u 1 there is a sequence of vertices v0v1uivk so that u vowvl 0le2 Hi 1amp4ka of Another type of graph is a planar graph This is a graph which can be drawn in the plane in such a way so that no two edges intersecti Of course every graph can be drawn in the plane the requirement that edges do not intersect though adds some extra constrainti It is important to note in this de nition that a graph is planar if there is some way to draw it in the plane without edges intersecting it does not mean that every way to draw it in the plane avoids edges intersectingi So for example in the last lecture we saw the graph Q3 and drew it as shown below on the left In this drawing we have edges crossing each other twice so that this is not a way to embed it in the plane without edges crossing but we can draw it in a way without edges crossing which is shown below on the right To show a graph is planar we need to nd a way to draw it in the plane without any edges crossingi How do we show a graph is not planari For instance try drawing K33 or K5 in the plane it turns out to be dif cult But is it dif cult because it is impossible or is it dif cult because we are not seeing some clever way to draw it It turns out that in this case it is dif cult because it is impossible as we will soon prover The main tool for dealing with planar graphs is Eu ler s formula Before we state it we rst need to give one more de nitioni So for a drawing of a planar graph we have vertices and edges but we also have subdi vided the plane into pieces which we call facesi If we were drawing the planar graph on a piece of paper then cutting along the edges we would cut our paper into some small pieces each piece corresponds to a face Let V denote the set of vertices E the set of edges and F the set of faces in the drawing of a planar graph Euler s formula For a connected planar graph lVlilEllFl2A As an example in the drawing of Q3 above we have lVl 8 12 and lFl 6 remember to count the outer face So 8 7 12 6 2 as the formula predictedi In the next lecture we will prove Eulerls formula and use it to show that the graphs K5 and K33 are not planar as well as give some other applications Lecture 20 7 May 15 We now prove Eulerls formula The key fact is the following Every connected planar graph can be drawn by rst starting with a single isolated vertex and then doing a series of two types of operations namely 1 add a new vertex and an edge connecting the new vertex to the existing graph which does not cross any existing edge and 2 add an edge between two existing vertices which does not cross any existing edger One way to see this is that we can run this backwards iiei starting with our drawing of a planar connected graph we either delete a vertex and its incident edge if it has degree one if no such vertex exists we remove an edge from the graph which will not disconnect the graph There is a subtlety to worry about how do we know that if all vertices have degree two or more that we can remove an edge without disconnecting the graph To see this note that ifthere were a cycle in the graph ie a subgraph which is a cycle or if you prefer a sequence of edges that starts and ends at the same point then removing an edge could not disconnect the graph since we could simply use the rest of the cycle to replace the now missing edger Further we can grow a cycle by the following technique we start with any vertex and move to an adjacent vertex we then move to a new vertex other than the one we came from and continue doing this until we get to a vertex that we have previously visitedi So suppose that we now have a sequence of vertices v1v2v3 ij and that vjwvi for some i lt j Then the desired cycle is viwvi1 ijwvii The key to this is since each vertex has degree two or more whenever we went into a vertex we could also exit along a different edge We now proceed by induction Our base graph con sists of a single vertexi In that case we have lVl l lEl 0 and lFl 1 ie the outer face and so lVl7lEllFl17012i Now suppose that we have shown that we have lVl 7 lEl lFl 2 for our connected planar graph Gr Sup pose that we do the rst type of operation as given above Then when we are adding a new vertex and a new edge but we do not change the number of faces ie this edge does not divide a face and so WENH1lE l7lEH1anle l7lFlso lV l W W lVl 1 lEl 1 lFl lVlilEllFl2 Suppose that we do the second type of operation as given above Then we do not add a vertex but we do add an edge further we must split a face into two faces andso lV l lVl lE l lEll and lF l lFllso lV l lE l W lVl lEl1lFl1 lVlilEllFl2 Concluding the proof Eulerls formula is the main tool for dealing with pla nar graphsi In this lecture we will show how to use it to prove that some graphs are not planar we will also see some additional applications in the next lecturer So let us rst try to prove that the graph K5 is not planari Before we do this we rst need to introduce the idea of counting the bounding edges in a face Every face can be though of as being contained inside of some cycle and so we can count how many edges are in the cycle by starting at a vertex and walking clock wise around the face and counting how many edges we encounter before we return to our starting position this will be the number of edges in the face There is a small bit of subtlety to be aware of namely consider the following graph a planar graph on three verticesi 0 0 0 This graph has two edges and a single face so as predicted by Eulerls formula 37 21 2 How many edges are in the face Our natural instinct is to say two but the correct answer is four That is because as we walk around we will encounter each edge twice and we count an edge each time we encounter it Put another way if we had cut along the edges we could not distinguish between this graph and what would have happened if we started with a four cycle The reason that we are using this de nition is be cause we want to be able to count edges by using in formation about facesi Namely since each edge will be used in two faces or twice in a single face if we add up the number of edges in each face we will have double counted all the edges in the graph iiei ZlEl Z fEF edges in face f We now make an observation for every simple con nected planar graph on at least three vertices each face has at least three edges in it The reason that we limit ourselves to simple graphs is that a loop would be a face with a single edge while a pair of vertices connected by two edges would give a face bounded by two edges Plugging this into the above formula we have edges in face f 2m Z fEF 2 233m fEF so that lFl S Putting this into Eulerls for mula we have 2 2lVl7lEllFl S lVlilEHglEl or rearranging we have El 3 3m 76 We are now ready to prove the following K5 is not planari Suppose that K5 were planari Since it a simple con nected graph on ve vertices this would then imply by the above inequality that S SlVl 7 6 but for K5 we have 10 and SlVl 7 6 9 so this is impossible So K5 is not planari Another graph that is dif cult to draw in the plane is K33 if we apply the above inequality we see that lEl 9 and SlVl76 12 From this we can7t conclude anything just because a graph satis es the above in equality does not automatically imply planari We will have to work a little harder for K3 One thing that we might be able to use is that the graph K33 is Lecture 21 7 May 20 In the last lecture we saw that K5 and K33 are not planari Clearly any graph which contains K5 or K33 as a subgraph cannot be planar since any subgraph of a planar graph must be planar But that is not the only possibility for ruling out planar graphs for instance consider the graph shown belowi This graph is found by taking K33 and subdividing an edge into two edges The resulting graph is not K33 but we see that it cannot be planar because if it were we could replace the subdivided edge by a new single edge to recover a way to draw K33 in the plane So it is not just the graph K33 but rather any graph sharing similar structure or in topology homeomorphici We say that a graph G contains a topological K5 or K33 if starting with G we can do three operations and form K5 or K33 namely 1 Remove an edge 2 Remove a vertex and any edge incident to the vertex 3 Contract an edge to a single vertexi That is if uv then we remove the edge joining u and v and combine the two vertices u and 1 into a new vertex uv this new vertex is adjacent to any vertex that was previously adjacent to either u or vi The rst two operations correspond to what it takes to form a subgraph so it is this last operation that is of the most interest to us This is the one that allows for us to take the graph K33 with a subdivided edge and contract one of the two edges to from K33i It is not hard to see that if a graph contains a topo logical K5 or K33 that it cannot be planar ie if it were we could use it to embed K5 or K33i Amazingly this turns out to be the only situation that we need to av01 i Kuratowski s Theorem A graph G is planar if and only if it does not contain a topological K5 or 33 Example Show that the Petersen graph is not planari Solution To show that the Petersen graph is not pla nar we must nd a topological K5 or K33 inside of it Looking at the Petersen graph it is easy to see that if we contract the edges between the outer pentagon and the inner star below highlighted in red that the re sulting graph is K5i Therefore it contains a topological K5 and so is not planari We now give one nal application of Eulerls formulai A Platonic solid is a polyhedra equivalent of a three dimensional polygon where each face is composed of a regular ngon an n sided polygon with each side and each interior angle equal and at every corner there are exactly m faces that meet Two examples of Platonic solids are the tetrahedron faces are triangles and at every corner three triangles meet and cubes faces are squares and at every corner three squares meeti Our goal is to determine how many Platonic solids there are The rst thing we need to do is to relate this to planar graphs Imagine that we are holding a poly hedra in our hand that is made out of a very stretch able rubberi Then we can puncture a small hole in one of the faces of the polyhedra and start pulling it apart stretching it out until we have attened out the rubber Then the corners and edges of the polyhedra form a planar graph with the corners becoming ver tices and the edges becoming well edges The faces of the polyhedra become the faces of the planar graph For example if we had started with a cube we would get the following graphi This connection between planar graphs and poly hedra is one reason that planar graphs are interesting to study So let us now translate the conditions to be a Pla tonic solid into conditions on the corresponding planar graph Each face being a regular ngon means that each face is bounded by exactly it edgesi As before we can double count edges by adding up the number of edges in each face and so we have 2 ZlEl anl or lFl n The requirement that m faces meet at each corner tells us that at every vertex we have exactly m edges coming in So by the handshake theorem we have ZlEllel or V3El m Putting this into Eulerls formula we have 2 2 ElEl 7 E glEl 2 or dividing everything by 2lEl 1 1 a 1 1 L gt 0 m n 2 7 So in order to be a Platonic solid we need to have 1 1 gt 1 m n 2 7 and we must also have that m n 2 3 This only gives us ve possibilitiesi Platonic solid Tetrahedron Octahedron lcosahedron Cube Dodecahedron U1gtJgtCA3CA3CA33 An octahedron has eight triangular faces an icosahe dron has twenty triangular faces and a dodecahedron has twelve pentagonal facesi Therefore the number of faces on Platonic solids are 46531220 For people familiar with role playing you might notice that these numbers are on the most common type of dice that are available Finally let us prove the following theoremi Mantel s Theorem If a simple graph on 2n vertices contains n2 1 edges then G must contain a triang er To contain a triangle means that there are three ver tices u vw so that uNUNwNu ie the three vertices form a triangle Note that this result is the best pos sible since the graph Kan has 2n vertices and n2 edges but no triangle since a triangle would give a cycle of odd length which we know cannot happen in a bipar tite graphi Also not how general this is we are saying that no matter how you draw the graph if it has 2n vertices and n2 1 edges it must contain a triangle and in fact contain many trianglesi To prove this we will make use of one of the funda mental principles in combinatoricsi Pigeon hole principle If you distribute 7 balls among n bins and 7 gt n then some bin has more than one bal The proof is by contradiction suppose not then the total number of balls is less than the number of bins which by assumption is impossible This principle seems so obvious that it is amazing that it can be used to prove anything but in fact it is used in many beautiful proofs including the proof we are about to give for Mantel s theoremi We proceed by induction For n 1 it is vacuously true since there is no graph on 2 vertices with 2 edges This is enough to get our induction started but sup pose that we are no comfortable with this case then for n 2 it is also true since the only graph on 4 ver tices with 5 edges is found by taking an edge out of a K4 and it is easy to check that this graph has two triangles Now let us suppose that we have shown that any graph on 2n vertices with n2 1 edges has a triangle Consider now a graph G on 2n 1 2n 2 vertices with n 12 1 n2 2n 2 edgesi Let u and v be two vertices in G joined by an edge Then we can draw G in the following way Namely as two vertices connected to an edge and then connected to the rest of the graph Consider the graph on the vertices other than u and 1 this has 2n vertices and so if there are n2 1 edges in this part of the graph then by the induction hypothesis it must contain a triangle and we are done So we may now assume that there are S n2 edges in the part of the graph not containing u and vi Since there is 1 edge connecting u and 1 that says that there are 2 2n1 edges between the vertices u v and the other 2n verticesi So by the pigeon hole principle there must be some vertex that is connected by two edges to the vertices u and 1 ie there is a vertex w so that wNu and wwv but since we already have uv then we have our triangle and this concludes the proo Lecture 22 7 May 22 Before we return to graph theory let us look at a nice application of the pigeon hole principlei Let 121122 12 be a rearrangement of 1 2 i i i n so for example when n 7 one such rearrangement is 35214761 A subsequence of this rearrangement is billy2 bik where i1 lt i2 lt lt ik ie we pick some elements of the rearrangement and still preserve their order Some examples of subsequences in the ar rangement for n 7 given above include 3146 5247 35 246 and so on A subsequence is said to be in creasing ifbi1 lt biz lt lt bik for example 146 in the above while a subsequence is said to be decreasing if 12 gt biz gt bik for example 521 in the above For every rearrangement of 1 2 i i i n2 1 there is always an increasing subsequence of length n 1 or a decreasing subsequence of length n 1 This result is the best possible since if we rearrange 1 i i n it is possible to have no increasing or de creasing subsequence of length n 1 For example for n 9 the only two sequences that do this are 321654987 and 789456123 We divide n2 into n blocks of n then we either reverse each block and put them in order or reverse the order of the blocks Obviously we are going to use the pigeon hole prin ciple to prove the result The idea behind proofs which use the pigeon hole principle is to show that there is some meaningful description of the objects bins so that the number of objects balls is more than the number of ways to describe them and so two of the objects must satisfy the same description We then use this fact to either derive a contradiction or con struct a desired objecti Suppose we have a rearrangement of 1 2p 1 i n2 1i Then for each i 1 2 i i i n 1 we associate a pair Ii Di where Ii is the length of the longest increasing subsequence that ends at bi and Di is the length of the longest decreasing subsequence that ends at bin so for example for the rearrangement 3521476 we get the following pairs 11 21 12 13 22 31 32 3 5 2 1 4 7 6 Note that all of the pairs listed above are distinct To see this suppose that i lt j then if bi lt bj we can take an increasing sequence ending at b and tack on bj to get a longer increasing sequence ending at bj showing Ii lt I similarly if bi gt bj then Di lt Dji In any case we have that ifi j then IiDi IjDji If there is no increasing and decreasing sequence of length n 1 or more than we must have that 1 S IiDi S n ie there are at most n2 possible IiDli On the other hand there are n2 1 points and so there are n2 1 pairs IiDl so that by the pigeon hole principle two would have to be the same This is impossible And so we can conclude that there must be an increasing or decreasing sequence of length n 1 or more We now return to graph theory We start with the rst major result in graph theory given by Euler in 1736 It is based on the following story In Konigsberg now called Kaliningrad there was a large river that ran through the city and in the middle of the river were two large islandsi Between the islands and the shore were seven bridges arranged as belowi As the story goes it was fashionable on Sunday evenings for the citizens of Konigsberg to dress in their nest and walk about the city People tried to nd a route where they would return to the place they started at and cross each bridge exactly oncei Try as they might people could not gure a route that would accomplish this Euler learned of the problem and he approached it by rst translating it into a question about graph the ory He let each piece of land be a vertex and each bridge an edge connecting two vertices This gives us the following multigraph a multigraph because it has two edges between two vertices Translating this into graph theory we are looking for a cycle in the graph ie we start at a vertex and move along edges and end at the vertex we started at which visits each vertex at least once and uses each edge exactly once the main condition is that we are using each edge exactly oncei Such a cycle is called an Euler cycle Euler made two observations rst if the graph is to have an Euler cycle then it must be connected because we can get from any vertex to any other vertex by using the cycle The second observa tion is that the degree of each vertex must be even To see this if we look at each vertex we will at some point come in and then we will leave via a different edge the idea here is that we can pair up the edge we came in with the edge that we came out and we do this every time we return to the vertex Now looking at the graph above it is easy to see that it is impossible to have an Euler cycle because the degrees of the graph are 3335 not even one even degreel So we now know when a graph does not have an Euler cycle ie it is not connected or has odd degree vertices but when does a graph have an Euler cycle Amazingly the necessary conditions are also suf cient conditions A graph has an Euler cycle if and only if it is con nected and every vertex has even degreei We have already seen that if a graph has an Euler cycle that it is connected and every vertex has even

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.