DISCRETE MATH FOR CS
DISCRETE MATH FOR CS CS 3653
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Ms. Bridie Kohler on Sunday November 1, 2015. The Class Notes belongs to CS 3653 at Oklahoma State University taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/232838/cs-3653-oklahoma-state-university in ComputerScienence at Oklahoma State University.
Reviews for DISCRETE MATH FOR CS
Report this Material
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: 11/01/15
Lecture 4 Permutations and Combinations with repetitions Consider a box it has 11 objects In how many ways can one order m objects from this box with replacement ltgt This is equivalent to say that take m selections from 11 items without regard to order and repeats are accepted with the assumption that at least m copies of each of the 11 items is allowed Answer Pnm n39quot Hl Nl L l M Sl rst choice 11 ways second choice 11 ways lh m choice 11 ways Product rule Pn m n n39 il CS 3653 Fall 2002 Lecture 4l T Menhaj Example 41 How many ways can we put m indistinguishable unlabeled balls in n distinguishable labeled containers Note 0ampQGB Qamp In general we may want to put rn balls into 11 boxes Balls can be labeled or unlabeled and boxes may be labeled or unlabeled Labeled implies ordering matters and unlabeled implies ordering does not matter The case in which both balls and boxes are labeled has been solved before and the answer is 11 CS 3653 Fall 2002 Lecture 42 T Menhaj For this example the balls are unlabeled and the boxes are labeled In how many different ways can we put m unlabeled balls into 11 labeled order matters boxes This problem is equivalent to the combination problem with replacement C nm with replacement number of ways to put m indistinguishable unlabeled balls into n distinguishable labeled containers number of nonnegative integer solutions to n Zn m n e N 1 ln il ni the number we choose of type 139 Solution Fact l2n ltgt clcz c1 c2 c3 cn l l l 2 3 11 CS 3653 Fall 2002 Lecture 43 T Menhaj Since the containers are labeled number them from 1 to 11 like below l l l ll l 2 3 n Line up the balls in each container from left to right l 00 l o l 000 l l 2 3 Note Balls can be taken with repetitions because they are unlabeled we lined them up in each container from left to ri ght Now we may look at the problem as a collection of balls and vertical lines separating them in an arbitrary order So we can see the problem as the following how many different strings can be created with m circles and n1 vertical bars oooooooooooooo Solution There are nml positions in the string m are balls Now we need to solve the problem Group m points CS 3653 Fall 2002 Lecture 44 T Menhaj from a set of nml distinct points in all possible ways n m 1 1 Theanswerls Cnm lm m m mn l Example 42 Find the number of different ways to group 2 objects with replacement repetitions from 4 distinct objects in a box 42 l 5 5 2 23 2 1 Q gta gt gt gt a 36gt Qgt5 0gt V CS 3653 Fall 2002 Lecture 45 T Menhaj Example 43 Travel from A to B with restriction of right or upward movements How many different choices do we have Each route consists of 3 right and 3 ups One route shown above RURURU Each route is described by a string of n R s and 11 US Thus there are C2nn possible choices CS 3653 Fall 2002 Lecture 46 T Menhaj Summary From N distinct objects in a box nd the number of ways 1 to group m objects with replacement the answer is N 2 to group 111 objects without replacement the answer is PNm 3 to group 111 objects without replacement and order is not important the answer is CNm 4 to group 111 objects with replacement and the order does matter the answer is CNm1m CS 3653 Fall 2002 Lecture 47 T Menhaj Generalized Combinations Given N objects and wish to group them into m classes A1AZAm such that the ith class consists of objects 71 with N This is equivalent to the following problem From a box ofN balls that has 71 balls of type i il2m how many orderings can we have N N The answerls CN711quot39nm j r11nm Proof Form class A1 from taking 11 out of N objects there exists CN 1 71 different ways for this Next we may choose 712 out of N n1 objects to establish class A2 with CN n1n2 different ways and so on This leads to CS 3653 Fall 2002 Lecture 48 T Menhaj CNnlnm CnnlCN nlnzCN nl nHnm N xv n ltN m39n gt N n1N nl39nz N ranz quotm0 m n Interpretations 1 Have m groups of elements the ith group consists of 71 repetitions of a particular element ei il2 m Place them into N Zni boxes one in i1 each The total no of ways this can be done is N N CNy1nmnvwnm nlnzmnm 2 Suppose S has N elements and that A1AzAm is a partition of S If the ith set A7 consists of n elements the total number of such partitions becomes CS 3653 Fall 2002 Lecture 49 T Menhaj Example 44 Find the total no of Ndigit binary numbers Solution First nd the total no of Ndigit binary numbers consisting ofm 1 s and nm 0 s Identify the 1 s as the objects of group 1 and the 0 s as the objects of group 2 This is equivalent to say that we wish to place these objects into N boxes one in each box The m objects of group 1 are placed in m out of N available boxes and the Nm objects of group 2 in the remaining Nm boxes This yields CNm since there exists these many ways of choosing m out of N objects Now if we wish to put m identical objects in ngtm boxes Cnm1Nm ways exist The total Ndigit binary numbers becomes C N m N ab M2 C Nma39quotbMquotquot 3 H o m 2N CNm m0 Note CS 3653 Fall 2002 Lecture 410 T Menhaj Analogy Now consider a set S consisting of N elements S1sN We can say that the total number of its sub sets including empty set and S is 2N Why Establish a onetoone correspondence between all the N digit binary numbers and the subsets of S in particular S corresponds to llll and empty set to 00 00 CS 3653 Fall 2002 Lecture 4ll T Menhaj Principle of Inclusion and Exclusion Some results related to the cardinality of nite sets Let A amp B nite sets 1 AUB AB 2 A mBl g minAB 3 AGBAB 2AUB AGBA BuB A Am uBmZAUB AmB 4 A B 2 A B CS 3653 Fall 2002 Lecture 412 T Menhaj Generalization Proved before AmB A B AmB Extend this result for three sets lAuBuCl ABC AmB AmC BmC Mmqu General Case 0 An il ZM 2 AZ mAJ Z AimAijk 139 l iltj n 11 iltjltk n 1n391 Ai il Prove by mathematical induction on the number of sets of 11 CS 3653 Fall 2002 Lecture 413 T Menhaj Example 45 How many positive integers 50 are relatively prime to 50 Solution 11 e N is relatively prime to 50 2 X 52 ifn does not have 2 or 5 as a factor So N50 2 1250 TneN50 st 2n F neN50 st Sln T 25 F 10 2 5 T FnEN50 st n2 amp n5neN50 stn10 TmF 5 10 Need to nd Ema Tm zTuFN5O TUFgt ITmF N50 TF TmF50 2510 520 CS 3653 Fall 2002 Lecture 414 T Menhaj
Are you sure you want to buy this material for
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'