4m ago

8 Views

0 Downloads

364.44 KB

5 Pages

Transcription

Combinations with RepetitionCS311H: Discrete MathematicsICombinations help us to answer the question ”In how manyways can we choose r objects from n objects?”INow, consider the slightly different question: ”In how manyways can we choose r objects from n kinds of objects?IThese questions are quite different:Combinatorics 3Instructor: Işıl DilligIInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 31/26ExampleAn ice cream dessert consists of three scoops of ice creamIEach scoop can be one of the flavors: chocolate, vanilla, mint,lemon, raspberryIIn how many different ways can you pick your dessert?IExample of combination with repetition: ”In how many wayscan we pick 3 objects from 5 kinds of objects?”ICaveat: Despite looking deceptively simple, quite difficult tofigure this out (at least for me.)Instructor: Işıl Dillig,IFor second question, once we pick one of the n kinds ofobjects, we can pick the same type of object again!Combination with repetition allows answering the latter typeof question!Instructor: Işıl Dillig,CS311H: Discrete MathematicsCS311H: Discrete MathematicsCombinatorics 3C3/26Example, cont.Combinatorics 32/26VMRLITo solve problem, imagine we have ice cream in boxes.IWe start with leftmost box, and proceed towards right.IAt every box, you can take 0-3 scoops, and then move to next.IDenote taking a scoop by and moving to next box by Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 34/26ResultCVMRLIWe’ll denote the number of ways to choose r objects from nkinds of objects C (n, r ): n r 1C (n, r ) rIExample: In how many ways can we choose 3 scoops of icecream from 5 different flavors?IHere, r 3 and n 5. Thus: 7!7 3533! · 4!Let’s look at some selections and their representation:I3 scoops of chocolate: I1 vanilla, 1 raspberry, 1 lemon: I2 mint, 1 raspberry: IInvariant: r circles and n 1 arrows (here, r 3, n 5)IOur question is equivalent to: ”In how many ways can wearrange r circles and n 1 arrows?”Instructor: Işıl Dillig,For first question, once we pick one of the n objects, wecannot pick the same object againExample, cont.IIICS311H: Discrete MathematicsCombinatorics 35/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 36/26

Example 1IISuppose there is a bowl containing apples, oranges, and pearsIIExample 2There is at least four of each type of fruit in the bowlIHow many ways to select four pieces of fruit from this bowl?IIThere is at least five of each type of bill in the boxHow many ways are there to select 5 bills from this cash box?IInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 37/26Example 3IConsider a cash box containing 1 bills, 2 bills, 5 bills, 10bills, 20 bills, 50 bills, and 100 billsInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 38/26Example 4Assuming x1 , x2 , x3 are non-negative integers, how manysolutions does x1 x2 x3 11 have?ISuppose x1 , x2 , x3 are integers s.t. x1 1, x2 2, x3 3.IThen, how many solutions does x1 x2 x3 11 have?IIIIIInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 39/26Summary of Different Permuations and CombinationsOrder matters?PermutationP (n, r ) CombinationNoC (n, r ) Instructor: Işıl Dillig,Permutation w/ repetitionn!(n r )!n!r !·(n r )!CS311H: Discrete MathematicsHow many different strings can be made by reordering theletters in the word ALL?IThis is not given by 3! because some of the letters in thisword are the sameIDifferent strings: ALL, LAL, LLA 3 possibilities, not 6because relative ordering of L’s doesn’t matterIIn general, how can we compute the number of permutationsof n objects where some of them are indistinguishable?Combination w/ repetitionCombinatorics 3Combinatorics 3IP (n, r ) n rC (n, r ) CS311H: Discrete Mathematics10/26Permutations with Indistinguishable ObjectsQuestion: How many ways to pick r objects from . . .n objectsn types of objectsYesInstructor: Işıl Dillig,(n r 1)!r !·(n 1)!11/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 312/26

Permutations with Indistinguishable Objects, cont.IIProofConsider n objects such that:In1 of them indistingishable of type 1In2 of them indistingishable of type 2IFirst, place all n1 objects of type 1I.IThen all n2 objects of type 2 etc.Ink of them indistinguishable of type kIIThe number of permutations in this case is given by:CS311H: Discrete MathematicsCombinatorics 313/26Proof, cont.ICS311H: Discrete Mathematics Now, how many ways to place n2 objects of type 2?Continuing this way and using product rule, number ofpermutations is: kP 1 nn n1n n1 n2n ni ··. i 1n1n2n3nkInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 315/26Example 1IInstructor: Işıl Dillig,Combinatorics 314/26Proof, cont.IIHow many ways to place n1 indistinguishable objects in nslots?In!n1 !n2 ! . . . nk !Instructor: Işıl Dillig,Let’s decompose using product rule:nn1 kP 1 n n1n ni ·. i 1n2nkILet’s expand this definition:IThis simplifies to:IAnother way to see this: Compute total # of permutations (n!) andthen divide by # of relative orderings between objects of type 1(n1 !), # of relative orderings of objects of type 2 (n2 !) etc.Instructor: Işıl Dillig,n!n1 !n2 ! . . . nk !CS311H: Discrete MathematicsCombinatorics 316/26Example 2How many different strings can be made by ordering theletters of the word SUCCESS?IThere are 3 identical red balls, 5 identical blue balls, and 2identical green balls.IIn how many different ways can these balls be arranged if thefirst ball must be blue?IIIIInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 317/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 318/26

Distributing Objects into BoxesExample: Distinguishable Objects in Distinguishable BoxesIHow many ways are there to distribute 5 cards to each of 4players from a deck of 52 cards?IIIMany counting problems can be thought of as distributingobjects into boxesIIn some cases both objects and boxes are distinguishableIIn some cases, boxes are distinguishable, but objects areindistinguishableInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 3II19/26Example, cont.Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 320/26Indistinguishable Objects Into Distinguishable BoxesIIIIIIHow many ways are there to place 10 indistinguishable ballsinto 8 distinguishable bins?IInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 321/26Distributing Objects into Boxes SummaryInstructor: Işıl Dillig,Distinguishable objects into distinguishable boxes:II22/26How many ways to distribute six distinguishable objects to fivedistinguishable boxes?IInvolves permutationsIIndistinguishable objects into distinguishable boxes:ICombinatorics 3Another ExampleIICS311H: Discrete MathematicsInvolves combinationIIInstructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 323/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 324/26

Example 2IExample 3How many ways to distribute six indistinguishable objects tofive distinguishable boxes?IIIIIIInstructor: Işıl Dillig,How many ways to assign 15 distinguishable objects into 5distinguishable boxes so boxes contain 1, 2, 3, 4, 5 objectsrespectively?CS311H: Discrete MathematicsCombinatorics 325/26Instructor: Işıl Dillig,CS311H: Discrete MathematicsCombinatorics 326/26

Example 1 I Suppose there is a bowl containing apples, oranges, and pears I There is at least four of each type of fruit in the bowl I How many ways to select four pieces of fruit from this bowl? I Instructor: Is l Dillig, CS311H: Discrete Mathematics Combinatorics 3 7/26 Example 2 I Consider a cash box containing 1 bills, 2 bills, 5 bills, 10 bills, 20 bills, 50 bills, and 100 bills