### Create a StudySoup account

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

Already have a StudySoup account? Login here

# SEM IN SELECTED TOPICS MA 502

UK

GPA 3.54

### View Full Document

## 5

## 0

## Popular in Course

## Popular in Mathematics (M)

This 40 page Class Notes was uploaded by Kennith Herman on Friday October 23, 2015. The Class Notes belongs to MA 502 at University of Kentucky taught by C. Lee in Fall. Since its upload, it has received 5 views. For similar materials see /class/228141/ma-502-university-of-kentucky in Mathematics (M) at University of Kentucky.

## Reviews for SEM IN SELECTED TOPICS

### 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: 10/23/15

Discrete Math Notes 1 The TwelveFold Way Count the numbers of ways to place a collection X of m 2 1 balls into a collection Y of n 2 1 boxes7 with the following options 0 The balls are either distinguishable labeled or indistinguishable unlabeled o The boxes are either distinguishable labeled or indistinguishable unlabeled o The placement is either unrestricted7 injective one to one7 or surjective onto Some questions to think about 0 Can you interpret the problem in another way 0 ls there a closed formula 0 ls there a recursive formula 0 Over what values of m and 71 do these formulas hold 0 What are some related problems 1 X m Labeled Balls Y n Labeled Boxes Unrestricted Placement a lnterpretation A 7 V A O A CL V Counts the number of functions from X into Y We get a one to one matching of ball placements and functions 9 by placing ball 239 into boxj if and only if 9239 j Closed Formula Solved the problem with 3 balls and 5 boxes by considering possible con gurations all three in one box two in one and one in another and all three in separate boxes Call the number of placements fmn Proved fmn nm using the mul tiplication counting principle This principle can be proved by mathematical induction Yields 1 if m 0 and n gt 0 and 0 if m gt 0 and n 0 both of which make sense77 Motivates the notation of YX for the set of functions from X into Y of which there are lYlle Recursive Formula fmn n if m 1 fmn n nm 1 if m gt1 Proved this by induction on m Wondered if it would be possible to prove this by induction on n Discussed using the recursive formula to make a spreadsheet of values Related Problems If n 2 this problem is isomorphic to counting the number of subsets of X denoted 2X of which there are 2le 2 quot Think of 277 as representing a set with two elements eg 01 Discussed a direct inductive proof that the number of subsets of X 1 m is 2 by looking at all of the subsets 1 m 71 and then either adding or not adding the element m to each How many ways are there to partition X into 71 labeled subsets of size 11 an respectively where 11 an m and a1 an 2 0 The answer is the multinomz39al coe cient We saw two proofs of this formula So over all choices of 11 an which are weak compositions of m into 71 parts see these must sum to n m E a1vvvan6Z a1an20 a1anm 117 7 17 2 D V Also we discussed the Multinomial Theorem which states that m 11 an E a a 1 95 11l1n6Z a1an20 a1anm 17 39 39 397 n We started constructing Pascal7s tetrahedron using the trinomial coef cients ltz1zngtm Additional Comments Discussed the connection between recursive formulas and recursive programming For example 711 can be de ned to be 1 if n 0 and n n 71 if n gt 0 Also the Towers of Hanoi puzzle to move 71 disks from peg a to peg b using peg c can be solved recursively as i If n 1 then move disk 71 from a to b ii If n gt 1 then move 71 7 1 disks from a to c using b move disk 71 from a to b move 71 7 1 disks from c to b using a Discussed the de nition of a relation between X and Y as a collection of subsets of X gtlt Y and of a function from X into Y as a relation between X and Y in which every element of X appears as the rst coordinate of exactly one ordered pair With this de nition the number of functions from X into Y is 1 if X is empty and 0 if Y is empty but X is not Discussed the notion of statements about elements of the empty set being vacu ously true motivated for example by the equivalence of an implication and the contrapositive statement For example given an integer m if z is in the empty set then x is even is equivalent to if z is odd then x is not in the empty set Another recursive formula Group the possible placements of balls into boxes ac cording to how many balls are placed into box 71 There are fm n71 placements with no balls in box 71 There are Tgtfm7 171 71 placements with exactly one ball in box n7 rst choose the ball to go into box 71 and then place the remaining m 71 balls in the remaining 71 71 boxes There are fm 7 2 n 71 placements with exactly two balls in box n7 rst choose the two balls to go into box 71 and then place the remaining m 7 2 balls in the remaining 71 7 1 boxes And so on This results in the recursive formula man 7 mwm Tgtfltm71n71gt growl We saw how to use the recursive formula to nd a new proof by induction on n that fmn nm This proof used the Binomial Theorem 1 b i 72gtakbm k k0 2 X m Labeled Balls7 Y n Labeled Boxes7 lnjective Placement W A 7 V lnterpretation Counts the number of injective functions from X into Y Closed Formula nn 71n 7 2 n 7 m 1 Denoted or 71 the falling factorial function This is Pm on some calculators Can be proved with the multiplication counting principle7 or induction from the recursive formula Works even if m gt 717 yielding 0 It might be helpful to think of lining up the balls in a xed location and then dragging the boxes over to the balls Recursive Formula Whn mmn this Related Problems Yields n if m 717 the number of bijections from X to Y7 and the number of permutations of X or of Y n 7 1m1 for m gt 1 How can you make a spreadsheet for Additional Comments The Pigezmhole Principle essentially states that there are no injections if m gt n7 that for any function from X into Y in such a case7 there must be at least one box pigeonhole with at least two balls pigeons We saw how the Pigeonhole Principle can be used to prove Given any ve points in a unit square7 there exists at least two of the points that are no more than 2 apart 3 X m Labeled Balls Y n Labeled Boxes Surjective Placement a A 7 V lnterpretation Counts the number of surjective functions from an m element set into an n element set Let7s denote this by Smn We saw several different ways to count these functions in some speci c cases Closed Formula Uses a counting principle related to the Principle of InclusionExclusion eg lAUBUBl 1AllBllOl7 lA Bl7lA Ol7lB OllA B Ol Count all functions from X into Y remove those from X into Z for each possible subset Z of Y of cardinality n 7 1 return those from X into Z for each possible subset Z of Y of cardinality n 7 2 etc mm 7 2717quot 7 n j 1gtn 71 n f 2gtn 7 2w 7 71 1ltTgt1m ln summation notation Why does this work Think of a function from X into Y that is surjective Then it is one of the functions counted by the term 71 and it is not among the functions counted by any of the other terms so this function contributes 1 to the overall sum Now think of a function f from X into Y that is not surjective Suppose the range is R a subset of Y of size 7 lt n The function f is counted once by the term nm It is counted once for every Z of cardinality n 7 1 containing R and there are such Z7we must select the 7 elements of R to place in Z and then we must select 71 7 1 7 7 more of the n 7 7 remaining It is counted once for every Z of cardinality n 7 2 containing R and there are 72 such Z7we must select the 7 elements of R to place in Z and then we must select 71 7 2 7 7 more of the n 7 7 remaining And so on So f contributes the following to the sum 71 7 7 17i2gt7 3 gt This is an alternating sum of binomial coef cients which equals zero We saw two proofs why 7 7 i 0 One involving a pairing bijection between subsets of 1 a of even cardinality and subsets of odd cardinality and another involving the binomial theorem The reasoning shows that the formula must work even if m lt 71 giving a binomial identity since Smn 0 in this case Table of some values smnln12 3 4 5 7711 1 2 12 3 16 6 4 114 36 24 5 1 30 150 240 120 Smn nlSmn where Smn is a Stirling number of the second kind See 9 We can invert this formula and count the total number of functions from X to Y by looking at their potential ranges nm ltggt mn73mn71 m H H o 33071 71 4 239 H H 0 930712 Recursive Formula We can see that 7 171 7 171 7 1 in the following way Think of surjective placements as ordered piles of balls For every surjective placement of m 7 1 balls into n 7 1 piles we can add a single pile containing the mth ball in 71 possible locations with respect to the existing 71 7 1 piles And for every surjective placement of m 7 1 balls into n piles we can add the mth ball to any one of the existing 71 piles hence n choices These placements are reversible by removing the mth ball d Related Problems A O V When we look at nite fli erences7 we will see why the above implies that the numbers Sm7 71 appear as the rst diagonal of the nite di erenoe table for the function 71 quot for xed m n 0 1 2 3 4 5 6 n5 0 1 32 243 1024 3125 7776 1 31 211 781 2101 4651 30 180 570 1320 2550 150 390 750 1230 240 360 480 120 120 0 4 X m Unlabeled Balls7 Y n Labeled Boxes7 Unrestricted Placement a lnterpretation A 7 V A O V V Counts the number of ways of writing in as a sum of n nonnegative integers7 where different orderings are counted as different Let7s call these weak compositions of in into n parts We made a table and saw the appearance of Pascal7s triangle Closed Formula Let7s use the notation gm7 n for the number of ways to do this Think of making a line of m n 7 1 white balls and then choosing n 7 1 of them to color black as spacers7 So the formula is gm7 n This is an example of a bijective proof It also equals mtf l This is sometimes written Recursive Formula One recursive formula is gmn gm 7 Ln gmn 7 17 which we veri ed by substituting the closed formula into this expression Another is gmn gmn71gm717171gm72n71g0n717 which we again veri ed by substituting the closed formula into this expression7 though we had to use the binomial recursion a ail a multiple times 17 i 1271 after changing the last term from 32 to 31 Related Problems Counts the number of multisets of 17 7n of size in Counts the number of monomials of degree in using n variables We observed that 1x1x 1z2z 13 1nzi when formally expanded yields all of the monomials in n variables So7 by re placing each of the 1 with the single variable x the number gm7 n is the 1 coef cient of z in the expansion of 12 This is an example Try typing of a generating function for the sequence 90ng1n2n7 series 11 X 577 or even series 11 X 1177 into wwwwolframalphacom In like manner7 we can think of 1 x as a generating function for the nite sequence lt3 7 n n 5 X m Unlabeled Balls Y n Labeled Boxes lnjective Placement a A 7 V A O V A CL lnterpretation Counts the number of subsets of 1 n of size m Closed Formula We denote this number called a binomial coe cz39ent as or Cnm or Cm We can prove using the multiplication counting principle and permutations or the recursive formula below that 21 We noted the relationship to the closed formula of n1 nn71n72n7m1 mln7ml39 mm71m721 7 ml Recursive Formula 3 1 and 1 n 2 0 121 71 210 lt m lt n This makes sense when thinking of subsets leading to a bijective proof It can also be proved algebraically directly from the closed formula Related Problems The numbers are the entries in Pascal7s Triangle This follows from the recursive formula You can also prove this by counting paths from the apex of Pascal7s triangle to any particular entry which count the number of times the 1 at the apex contributes to that entry We saw a correspondence between the paths and the ways of choosing directions left or right along the path is the coef cient of z in 1 s m These make sense when writing out 1 s 1 s and choosing which terms will contribute to z The recursive formula also makes sense when writing out 1 z 11 s and seeing which terms will contribute to z is the coef cient of an mbm in a b m 1 i m0 ab Zn m0 By substituting z 1 into the above forrnula7 or using that there are 2 subsets of Y7 we have n 71 Z lt gt 2 m m1 By substituting z 71 into the above forrnula7 we have m1lt71gtm lgt 0 which shows that there are equal numbers of subsets of even cardinality and of odd cardinality 6 X m Unlabeled Balls Y n Labeled Boxes Surjective Placement a A 7 V lnterpretation Counts the number of ways of writing m as a sum of 71 positive integers where different orderings are counted as different These are called compositions of m Closed Formula We can place one ball in each box rst leaving m 7 71 balls to place with no restriction in 71 boxes Or we can take a composition of m into 71 positive integers and and subtract 1 from each term to get an expression of m 7 n as a sum of n nonnegative integers Either way by 4 there are ways to do this which i or We can also argue directly Think of making a line of m n 7 1 white balls and then choosing n 7 1 of them to color black as spacers7 But this time we cannot select two spacers side by side and we cannot select an end ball to be a spacer So the rst ball cannot be black and every black ball is followed by a white one Collapse each of the n 7 1 black white pairs of balls into a single red ball Now there is a line of m balls from which you must select 71 7 1 of them but you are not allowed to choose the rst one The number of ways of doing this is equals Recursive Formula If we call the number of surjective placements hmn then the standard bino mial identity implies hmn hm 7 171 7 1 hm 7 171 Can you nd a combinatorial proof of this Related Problems Counts the number of monomials of degree m using 71 variables in which every variable is raised to a positive power z2 z3 or Equals the coef cient of z in 1 The total number of compositions of m equals 2m 1 since i m 71gt 2W1 1 n 7 1 Or use a generating function proof by considering 1xx2x3xx2x32xx2x33 The coef cient of z in this expression equals the total number of compositions of m But this expression simpli es to 1 1117 111f2z 1z12z2z22z3 1z2z222z323z4m For a bijective proof7 map a composition m a1 an to a collection of partial sums 11411 a27a1 412 a37a1 an1 Q 177m 71 How many compositions of m are there using only 17s7 27s7 47s7 and 87s We can solve this problem by looking for the coef cient of z in the series expansion of 1 2 4 8 2 4 8 2 2 4 8 3 1 7 An algebraic calculator like wolframalpha can help us here How many compositions of m are there using only 17s and 27s We saw that the answer was the mth Fibonacci number7 because the compositions of m can be obtained from the compositions of m 7 2 by appending 2 and from the compositions of m 7 1 by appending 1 The number of such compositions is the coef cient of z in the series expansion of 1 1 2 2 2 2 3 39 xzxzzz 17967962 We computed the rst few terms of this using wolframalpha7 and saw the appear ance of the Fibonacci numbers as coef cients 7 X m Labeled Balls7 Y n Unlabeled Boxes7 Unrestricted Placement a lnterpretation This counts the number of partitions of X into at most 71 blocks b Closed Formula By 9 this equals Sm1 Smn c Recursive Formula d Related Problems This counts the number of equivalence relations on X with at most 71 equivalence classes hence the total number of equivalence relations if n 2 m 8 X m Labeled Balls7 Y n Unlabeled Boxes7 lnjective Placement a lnterpretation Either you can do it or you cannot b Closed Formula 1ifm ng0ifmgtn c Recursive Formula d Related Problems 9 X m Labeled Balls7 Y n Unlabeled Boxes7 Surjective Placement a A 7 V A O V lnterpretation This counts the number of partitions of the set X into exactly n nonempty blocks Closed Formula This number is known as Smn7 a Stirling number of the second kind From 3 we get the formula because the order of the boxes which are distinguishable by their nonempty contents is no longer relevant Recursive Formula Thinking of partitions7 Smn Sm 7171 71 nSm 7171 Think about where to insert element in into a partition of m 7 1 elements What is the base case Related Problems This counts the number of equivalence relations on X with exactly n equivalence classes 10 X m Unlabeled Balls Y n Unlabeled Boxes Unrestricted Placement a lnterpretation A 7 AA 0 CL This is the number of ways of writing m as a sum of at most 71 positive integers where the order does not matterithe number of partitions of the number m into at most 71 parts From 12 this equals p1m Closed Formula Recursive Formula Related Problems If n 2 m we get the total number pm of partitions of m A generating function for these numbers is I Z pmm H17 f l mZO 13921 This is explained by thinking of the number m as written as a multiple of 1 plus a multiple of 2 plus a multiple of 3 etc 11 X m Unlabeled Balls7 Y n Unlabeled Boxes7 lnjective Placement a lnterpretation Either you can do it7 or you cannot b Closed Formula 1ifm ng0ifmgtn C Recursive Formula d Related Problems 12 X m Unlabeled Balls Y n Unlabeled Boxes Surjective Placement a lnterpretation A 7 V A O V V This is the number of ways of writing in as a sum of exactly 71 positive integers where the order does not matter These are called partitions of the number in into 71 parts This number is denoted Closed Formula Recursive Formula Either the smallest part equals 1 or it does not If it does remove that part If it does not subtract 1 from all parts Thus 10W 107L710 1pnm 7 Related Problems We used the cubes to make Ferrers diagrams of partitions and saw how ipping them77 shows that the number of partitions of in into 71 parts equals the number of partitions of in into an unrestricted number of parts with the largest part equaling n 2 The Pigeonhole Principle Quite simply7 the pigeonhole principle states that if le gt lYl then there are no one to one functions from X into Y So if m gt n and there are m pigeons and n pigeonholes in which they roost7 there must be at least one pigeonhole with more than one pigeon This obvious principle can be used to prove some perhaps less than obvious facts H F 9 7 U 03 5 00 p Prove that there are at least two humans on earth with the same number of hairs on their heads There are 100 people at a party Assume that if person A knows person B7 then person B knows person A Prove that there are at least two people at the party who know the same number of people In a bureau drawer there are 60 socks7 all identical except for their color 10 pairs are red7 10 are blue7 and 10 are green The socks are all mixed up in the drawer7 and the room the bureau is in is totally dark What is the smallest number of socks you must remove to be sure you have at least one matching pair Prove that when a fraction ab is expressed in decimal form7 the resulting number will be either a terminating decimal or one that repeats with a period no longer than b Prove that if ve points are placed anywhere on or in a square of side length 17 at least two points will be no farther apart than Prove that if ve points are placed anywhere on or in an equilateral triangle of side length 17 at least two points will be no farther apart than 12 Try counting the edges around the faces of a polyhedron You will nd that there are always two faces somewhere bounded by the same number of edges Why Prove that no matter how a set S of 10 positive integers smaller than 100 is chosen there will always be two completely di ferent selections from S that have the same sum For example7 in the set 37 97 147 217 267 357 427 597 637 76 there are the selections 147 637 and 357 427 both of which add to 77 similarly7 the selection 37 97 14 adds up to 267 a number that is a member of the set A physician testing a new medication instructs a test patient to take 48 pills over a 30 day period The patient is at liberty to distribute the pills however he likes over this period as long as he takes at least one pill a day and nishes all 48 pills by the end of the 30 days Prove that no matter how the patient decides to arrange things7 19 H H H D H 7 there will be some stretch of consecutive days in which the total number of pills taken is 11 Suppose some set of 101 numbers a1a2 a101 is chosen from the numbers 1 2 200 Prove that it is impossible to choose such a set without taking two numbers for which one divides the other evenly that is with no remainder Consider a circle 0 with a radius of 16 and an annulus or ring A with an outer radius of 3 and an inner radius of 2 Prove that wherever one might sprinkle a set S of 650 points inside 0 the annulus A can always be placed on the gure so that it covers at least 10 of the points The next example concerns a marching band whose members are lined up in a rect angular array of m rows and 71 columns Viewing the band from the left side the bandmaster notices that some of the shorter members are hidden in the array He recti es this aesthetic aw by arranging the musicians in each row in nondecreasing order of height from left to right so that each one is of height greater than or equal to that of the person to his left from the viewpoint of the bandmaster When the band master goes around to the front however he nds that once again some of the shorter members are concealed he proceeds to shuf e the musicians within their columns so that they are arranged in nondecreasing order of height from front to back At this point he hesitates to go back to the left side to see what this adjustment has done to his carefully arranged rows When he does go however he is pleasantly surprised to nd that the rows are still arranged in nondecreasing order of height from left to right Shuf ing an array within its columns in this manner does not undo the nondecreasing order in its rows Can you prove this Take the numbers from 1 2 3 nZ 1 and arrange them in a sequence in any order Prove that when the arrangement is scanned from left to right it must contain either an increasing subsequence of length at least 71 1 or a decreasing subsequence of length at least 71 1 For example when n 3 the arrangement 65937 1284 10 includes the decreasing subsequence 653 1 As this example demonstrates a subse quence need not consist of consecutive elements of the arrangement A lattice point is a point in a coordinate plane for which both coordinates are integers Prove that no matter what ve lattice points might be chosen in the plane at least one of the segments that joins two of the chosen points must pass through some lattice point in the plane 15 Six circles including their circumferences and interiors are arranged in the plane so that no one of them contains the center of another Prove that they cannot have a point in common 16 Prove that in any row of mn1 distinct real numbers there must be either an increasing subsequence of length at least m 1 or a decreasing subsequence of length at least 71 1 These problems were taken from Martin Gardner7 The power of the pigeonhole7 The Last Recreations7 chapter 11 The answers to the problems can be found there 3 Guessing Formulas It should be remarked that although the principle of mathematical induction suf ces to prove the formula once this formula has been written down7 the proof gives no indication of how this formula was arrived at in the rst place why precisely the expression 122 should be guessed as an expression for the sum of the rst it cubes7 rather than nn132 or 19n2741n242 or any of the in nitely many expressions of a similar type that could have been considered The fact that the proof of a theorem consists in the application of certain simple rules of logic does not dispose of the creative element in mathematics7 which lies in the choice of the possibilities to be examined The question of the origin of the hypothesis belongs to a domain in which no very general rules can be given experiment7 analogy7 and constructive intuition play their part here But once the correct hypothesis is formulated7 the principle of mathematical induction is often suf cient to provide the proof Inasmuch as such a proof does not give a clue to the act of discovery7 it might more ttingly be called a veri cation icourant and Robbins7 What is Mathematics7 Section l24 In this section we discuss some ways to guess formulas for sequences PS Courant and Robbins is an excellent book to add to your personal library 31 Finite Differences Suppose you are asked to nd a function fx such that W 7 f 0 5 WW 6 fHO 12 f40 0 f50 0 f60 0 We might guess that the function is a polynomial of degree 3 How can we determine the coef cients f co clz 02x2 03x3 f0 co co f0 f 01 202x 303z2 f 0 01 01 f 0 f 95 202 66396 f 0 262 62 f 02 JENx JEN0 f06 In our example 00 7701 5 02 73 and c4 2 so f 77 5x 7 3x2 2x3 In general if you think f is a polynomial of degree m f coclx02xz 0sz then 60 f00l C1 f 01l 62 f 02l omfWmI so rm 0 1 2 jh f m m What is the number of di ferent triangles you can form on a at surface using three toothpicks for the three sides of each triangle given an unlimited supply of toothpicks of n di erent colors number of colors number of triangles 0 0 1 4 11 24 45 Umbcoww We want a formula fn so that f0 f1f2 f3 f4f5 0 14 11 2445 Look for a pattern by subtracting these numbers from each other making a di erence table 0 1 4 11 24 45 1 3 7 13 21 2 4 6 8 2 2 2 0 0 Consider some known formulas 0 1 4 9 16 25 i 2 1 3 5 7 9 n 71 39 2 2 2 2 0 0 0 0 0 6 24 60 120 0 6 18 36 60 fn n3 i n 6 12 18 24 6 6 6 0 0 This suggests that for our problem we seek a formula of degree 3 Let7s call the numbers in the rst row f07f17f27f37f47 and the numbers in the second row f 07f 17f 27f 37f 47 24 and the numbers in the third row W JWMWWLW JW etc These aren7t equal to derivatives in the sense of differential calculus7 but there seems to be a strong analogy mi i fh m h70 fm7 h In differential calculus7 we exploited function derivative x0 0 1 1x0 x2 2x1 x3 3x2 xk kzk l What is the analog for differences De ne n nn71n72n7k1 V kterrns This is the falling factorial that we say before function derivative 1 n9 0 0 n nl 1719 1 nn 71 n2 2nl 2n nn 71n 7 2 mi 3712 3nn 71 nn71n7k1 71E knk l knn71n7k2 Veri cation nn71n7k27nn71n7k2n7k1 nn71n7k2n17n7k1 k Now we can guess formulas fn co 0171 02712 03n f0 co co f0 f n CA1L20271303712 f 0 01 01 f 0 f n 202 60371 f 0 202 02 f 02 JENn 663 JEN0 663 CS f06 In our exarnple7 f0 0 co 7 0 f 0 1 cl 1 f 0 2 02 1 f 0 2 03 13 fn 0 1711 1712 n n Mn 7 1 W n3 271 ft Now we have a formula that we can try to prove7 eg7 by indluction7 or directly In general7 fetch f07 f 07 f 07 fk0 as the rst entries of the rows of the di erence table assuming we have reached a row of zeroes Then 61 f 01l 62 f 0Ql or Mank fn cocln02ngcknE Q l 2 mfg f 0 fquotltogtX fk0 Note that j jltj71gt321 71 nni1nij1ltngt j M W 5 f 0 1quot f 0 fk0 taking 0 if n lt j SO In our exarnple7 f 071 171 271 271 71 0 1 2 3 Here is another way of doing the same thingivia antidlerivatives7 JUNn f n K f 0 2 2 K f n 2 2719 f n 2nl L f 0 2 2 L f n 2nl 2719 fn 712 2711 M fO 1 gt 1 M gt fn 712 2nln9 fn m 712 nl N f0 0 gt 0 N 1 fn gni n2 mi and you can verify that this is equal to 2 which is the formula we had found before As another exarnple7 let7s obtain a formula for fn 02 12 22 712 Make a difference table 0 1 2 3 4 5 0 1 5 14 30 55 1 4 9 16 25 3 5 7 9 2 2 2 0 0 So fn oltggt1ltfgt3ltggt2ltggt mmwmw l 00R 2 717 Oil nn 12n 1 Finally7 recall in Case 3 of the Twelve Fold Way we saw the formula 71 quot L0 Elm 239 Our analysis of nite di erences now shows why we can expect to see the numbers S mz in the rst diagonal of the di erence table for the function 71 quot 32 Exp onentials What about the following sequence 18 72 288 1152 If we take quotients of entries in the last row instead of di erences7 we see that every quotient is 4 So f n is a geometric7 not an arithmetic sequence as in our earlier examples f n 18 4 What is the antiderivative of 4 Maybe we can gure this out if we can determine the derivative of 4 4 1 i 4 4 4 i 1 3 4 So the antiderivative of 4 is ll Now we can nd a formula for the sequence f n 18 41 fn 64nK f 05gt56KgtK71gtf n64 7n0 fn 24 lnl1L f02gt22LgtL0gtfn24nin This method works in general if fkn is geometric 33 Using Series Playing around with series can give more techniques Remember how to gure out the formula for geometric series like h 1 2x 2x2 2x3 h 1 2x 2x2 2x3 72zh 72x 7 2x2 7 2x3 7 17 2xhz 1 1 h 7 1 i 2 1 z 1 7 M lt x We never seem to get a row of zeroes The second row looks like77 twice the rst row ie7 fn 1 fn 2fn 7 1 for n 2 1 The ordinary Fibonacci sequence satis es fn 1 m fn 71gt Let de ne a power series using fn as the coef cient of x g 1x3x25311z4 The relationship fn 1 7 fn 7 2fn 7 1 0 suggests 1x3x25x311x4 7z727337547 72z272z376x47 17 z 7 22g 1 1 gm 7 72 7 z 1 Remember7 fn is the coef cient of x Let7s try to nd it W 1 1 7 23 11 72x271172x1x 17295 30 We did the last step using the method of partial fractions Continuing7 2317 295 1 131 z 1 231 2x 2x2 2x3 1317xx27z3 since we have geometric series So the coef cient of x is 23 131 and this is our guess for the formula for We then also derived a closed formula for the ordinary Fibonacci sequence this way 34 Using Matrices Let7s look at the previous sequence 1 1 3 5 11 21 43 another way Make vectors out of pairs of adjacent elements 5 11 111 11 12 and nd a matrix that transforms each vector into the next using the Fibonacci nature MM of the sequence In general and calculate A by diagonalizing A eigenvalues eigenvectors A SDS 1SDS 1SDS 1 SDnS 1 2 0 i N25 firm e33 So A m i W Jim Jim 232 131 43 131 fn1 Therefore fn 32 171 3 3 Exercise Try to derive a formula for the ordinary Fibonacci sequence this way 4 Principle of InclusionExclusion This relates to Section 37 of the text Summary of class activities 1 Considered the problem of nding the number of integers remaining in the set 1 210 once all numbers that are multiples of 2 3 andor 5 are removed 2 Used this to motivate the Principle of InclusionExclusion PIE a formula to compute lAl U U Anl for a collection of sets We saw three ways to formulate this principle 3 lllustrated the rst proof by induction given in the book with the suf ciently com plicated example77 of lAl U A2 U A3 U 14 4 Went through the second proof given in the book in which the contribution of an arbitrary element x 6 A1 U U An to the sum is computed and shown to be 1 5 Derangements This relates to Section 38 of the text Summary of class activities 1 2 00 7 De ned derangements and computed the number Dn of derangements for small values of n Detected l7 and then proved7 the recursive formula Dn n71Dn71Dn72 Sketch Think of a derangement as a placement of balls 1771 in labeled boxes 1771 for which no ball is placed in a box with the same label You can make a derangement of size n in two ways a Choose a derangement of 17 771 7 1 there are Dn 7 1 ways to do this7 place ball 71 in box 717 and then swap ball 71 with one of the other balls there are n 7 1 choices b Choose a ball k E 17771 7 1 there are n 7 1 choices7 place ball k in box k choose a derangement of balls 17 717 in the boxes 17771 7 1 there are Dn 7 2 ways to do this7 and then nally swap ball 71 with ball k Each derangement of size n is obtainable by exactly one of the above two procedures7 in exactly one way Discussed the closed formula for derangements obtained from the Principle of lnclu sionExclusion Showed that the probability that a random permutation of n elements is a derangement is approximately 6 Graphs Summary of class activities 1 Basic de nitions a bit of graph isomorphism subgraphs connectivity components the adjacency matrix walks paths and cycles Sections 41 and 42 of the text E0 Making random graphs77 by exchanging business cards77 9 Using a queue to carry out breadth rst search on a graph to determine the vertices in a component of a graph 7 Determining the distance between pairs of vertices when the edges have each been as signed a nonnegative cost using a modi cation of matrix multiplication 7 see Home work 4 U Eulerian graphs 7 Section 44 of the text Alternative proof of Theorem 441 Assume that G is a connected graph with each vertex of even degree Begin at any vertex 1 and start walking never reusing an edge Eventually you will return to 1 If all edges have been used then you have found an Eulerian closed walk W Otherwise upon deletion of this walk the remaining components each have Eulerian closed walks by induction on the number of edges Show that each such component shares at least one vertex with W Splice77 the Eulerian closed walks from each component into W This can be turned into an algorithm using a stack CT Traversing mazes using pebbles from Martin Gardner7s book The Second Scienti c American Book of Mathematical Puzzles and Diversions Chapter 10 7 Trees and Spanning Trees Summary of class activities H F 9 7 Cf 03 5 De nitions of trees and spanning trees Every tree has at least two vertices of degree 1 See Section 51 of the text The minimum spanning tree problem and Kruskal7s Greedy77 algorithm though we did not prove the correctness of this algorithm 7 see Section 54 of the text The number of spanning trees in the complete graph Kn is 71 Proof using Priifer codes 7 see Section 84 Matrix Tree Theorem for the number of spanning trees in an arbitrary graph which we did not prove 7 see Section 85 of the text Deletion and contraction formula for the number of spanning trees tG tG e tGe A brief introduction to the relationship between the set of triangulations of a convex polygon7 rooted binary trees7 ways to insert parentheses into a string of symbols7 and certain paths in a square grid Dyck paths Some of this material is in Section 124 of the text An application of triangulations and trees to prove the Art Gallery Theorem 7 the number of guards needed to guard an art gallery in the form of a simple polygon with n vertices is at most 713 8 Matchings Summary of class activities 1 E0 An algorithm by growing alternating trees to nd a maximum cardinality matching in a bipartite graph Konig7s Theorem In a bipartite graph the size of a maximum cardinality matching equals the size of a minimum cardinality set of vertices that col lectively are incident to every edge of the graph a covering of the edges by vertices An algorithm to nd a stable matching in a bipartite graph For example see the website httpwwwamsorgfeaturecolumnarchivemarriagehtml 9 Chromatic Polynomials Summary of class activities 1 Let Xak be the number of ways of coloring the vertices of a graph G using at most k colors7 so that no two vertices of the same color are joined by an edge 2 Proved the formula Xak XG5k 7 Xa5k Used this to prove that if lV 717 then Xak is a polynomial in k of degree 717 with leading term k 10 Combinatorial Games Summary of class activities 1 E0 00 4 9 Brief introduction to nite7 two person combinatorial games If there can be no tie7 then either the rst player or else the second player has a winning strategy A position is good77 if it one that you want to attain otherwise the position is bad7 The nal winning positions are good and the nal losing positions are bad An intermediate position is good if every immediately subsequent position your opponent can attain is bad otherwise it is good With this notion it is possible to analyze some simple games A game is impartial if both players have the same options from any given position Nim values or Sprague Grundy values can be assigned to positions These values are nonnegative integers Final winning positions are labeled 0 Intermediate positions are labeled with the smallest integer absent from the values of immediately subsequent positions the mex or minimum excluded rule You can de ne the addition G1 G2 of two games with the rule that when it is your turn to make a move in G1 G2 you must choose exactly one of the games and make a valid move in that game A useful theorem for the addition of impartial games is that the nim value of the sum of two or more games is the nim sum of the nim values of these games The nim sum of two nonnegative integers is obtained by writing the integers in base two7 adding them without carrying7 and then converting them back to base ten In this way7 for example7 you can win at the game of Nim7 in which there are several piles of chips7 and when it is your turn you must take any positive number of chips from any one pile of your choice The person to take the last chip of all is the winner The value of any position is found by taking the nim sum of the numbers of chips in the various piles The winning strategy is to always move to a position of nim value zero

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "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."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.