### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DISCRETEMATHEMATICS MATH245

SDSU

GPA 3.72

### View Full Document

## 15

## 0

## Popular in Course

## Popular in Mathematics (M)

This 23 page Class Notes was uploaded by Burnice Ratke on Tuesday October 20, 2015. The Class Notes belongs to MATH245 at San Diego State University taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/225273/math245-san-diego-state-university in Mathematics (M) at San Diego State University.

## Reviews for DISCRETEMATHEMATICS

### 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/20/15

C C Counting and Probability Permutations Addition Rule InclusionExclusion Lecture Notes 11 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminusSDSUEDU httpterminusSDSUEDU Id lectureitexv 1 2 20061113 213157 blomgren Exp Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 123 C C Last lecture we started talking about Counting and Probability We introduced the concepts random process sample space 8 all the possible outcomes of a random process event a subset of the sample space and probability the relative size of the event vs the sample space PltEgt element is the event 718 elements in the sample space this formula is valid if and only if all outcomes are equally likely We counted elements in a list looked at the probability of outcomes when tossing coins introduced the concept of a possibility tree which shows all possible combinations of sequential events and in troduced the multiplication rule for independent events Counting and Probability Permutations Addition Rule InclusionExclusion 7 p 223 The previous figure shows all the possible ways the world series can play out but there are multiple ways to reach some most states eg the scenario A wins B wins and B wins A wins end up in the same state one win for each team In a possibility tree these two paths are differen tiated the possibility tree for the first 5 games looks like this Figure to the right The possibility tree forthe first 5 games of the world series Note that 2 out of 16 paths terminate af ter4 games An additional 8 paths terminate after 5 games Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 323 Recap Key Concepts Independence Multiplication Rule If we have a sequence of events which are independent note that this does not apply to the world series since depending on the outcome of previous games games 5 6 and 7 may not be played the multiplication rule applies Theorem Multiplication Rule If an operation consists of k steps and step i can be performed in m ways i 1 2 k then the entire operation can be performed in n1n2nkways If all 7 games of the world series were played no matter what the outcome of the previously played games k7 n1n2n3n4n5n6n72 27 128 possibilities Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 423 Set Order A permutation of a set of objects is an ordering of the objects For example the set abc has six permutations abc acb bac bca cab cba Question How many permutations does a set with n elements have The first element can be selected in 71 ways the second in n 1 ways the third in n 2 ways Permutationsn n n 1 1 n Theorem For any integer n 2 1 the number of permutations of a set with n elements is n nfactorial Counting and Probability Permutations Addition Rule InclusionExclusion 7 p 523 We are to seat six dinner guests around a table Figure Two seating arrangements are considered the same if they are just a rotation of each other Question How many seating arrangements are there taking rotational symmetry into consideration Solution We can take one guest and put himher in a fixed position then the other five can be seated in 5 120 different ways relative to the first guest Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 623 We are to seat six dinner guests around a table Figure Two seating arrangements are considered the same if they are a rotation of each other andor a reflection of each other Question How many seating arrangements are there taking rota tional and reflective symmetry into consideration Solution Since each seating arrangement has a mirror image we now effectively have 5 60 different seating arrange ments Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 723 C Given the set S abc there are six ways to select two letters from S and write them in order ab ac ba be ca Cb Each such ordering of 2 elements of S is called a 2permutation of S Definition rpermutation An r permutation of a set of n elements is an ordered selection of r elements taken from the set The number of rpermutations of a set of n elements is denoted Pn r I wonder if we could create a game using a set with 52 elements and consider the 5permutations 0 Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 823 Pn r r Theorem If n and r are integers and 1 g r g n then the number of rpermutations of a set of n elements is given by the formula Pnrnn 1n 2 nr1W Proof There are n 0 ways to make the first choice n 1 ways to make the second choice n r 1 ways to make the rth choice therefore the number of combinations are nn 1n r 1nn 1n r1 Now we notice n Tr n n 1 1 n 7quot nn 1 n r1 D Counting and Probability Permutations Addition Rule InclusionExclusion 7 p 923 Pn r Problem How many 4permutations are there of a set of 15 elements Solution 1 We can just plug in and evaluate 15 15 1307674 368000 32 760 15 4 11 39 916 800 P154 However this can become problematic if n is large my quite ancient calculator can only compute up to 69 1711 x 1098 Solution 2 Think about what the denominator does ie canceling the tail of the factorial in the numerator 15 15 Counting and Probability Permutations Addition Rule InclusionExclusion 7 p 1023 Pn 2 Pn 1 n2 Proposition For all integers n 2 2 Pm 2 Pm 1 n2 Proof Let n be an integer Z 2 and use the theorem on slide 9 ie Pn2 mi g nn 1 Pn1 mi ll n and therefore Pn2Pn1nn 1nn2 nnn2 V7122 D Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1123 The Addition Rule Counting Elements of Disjoint Sets Theorem If A1 A2 An is a partition of A then MA nA1 nA2 MA The formal proof exercise Epp6333 uses mathematical induction Intuitiver it is clear each element in A is a member of exactly one of the sets Ai so the element count on both the left and righthandside must be the same Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1223 Problem In order to use the Big Bank39s ATMs the user must have a 4 6 digit PIN each digit is an integer 0 9 How many such PINs are there Solution 4digit PINs 104 10 000 5digit PINs 105 100 000 6digit PINs 106 1 000 000 4 6digit PINs 1 110 000 Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1323 Theorem subset of A B C A then If A is a set with finitely many elements and B a nA B nA 713 A n elements Figure The Difference Rule Illustration B k elements L AB n k elements Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1423 Example Counting 46 Digit Ple withwithout repetition Problem In order to use the Big Bank39s ATMs the user must have a 4 6 digit PIN each digit is an integer 0 9 How many such Ple are there How many Ple have no repeating digits How many Ple have repeating digits Solution Ple Any Digits No Repetition With Repetition 4digit 104 10 000 P10 4 5040 4 960 5digit 105 100 000 P10 5 30 240 69 760 6digit 106 1000000 P10 6 151 200 848800 4 6digit 1110000 186 480 923 520 Thus requiring nonrepeating passwords limits the password space quite severely Counting and Probability Permutations Addition Rule InclusionExclusion 7 p 1523 Problem When you get your ATM card from the Big Bank you are assigned a random 4 6digit PIN What is the probability that the PIN will have repeated digits What is the probability that it will not Solution P ewm mm w wag 0ampm 83w7 p nany 1110000 39 0 nno repeated 186480 nany 391110000 Pno repeated 0168 168 We notice Prepeated I Pno repeated 1 This true in general for complementary events Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1623 Formula for the Probability of the Complement of an Event If S is a finite sample space and E is an event in S then PEC 1 PE Since 8 EUEC and E EC we have 718 MEG ltgt MEG 718 and HE nltsgt Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1723 Theorem if A and B are any finite sets then nA U B nA nB nA H B Figure If we count the elements in A and add the elements in B then the elements in the intersection A H B are counted twice The statement in the theorem subtracts one instance of the elements in the intersection making the count correct Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1823 C C Given the InclusionExclusion rule for two sets we can find rules for more sets Let A B and C be any sets nAUBUC AnBUC nA BUC nA nB n0 nB 0 nA 0 B U 0 nA nB n0 nB 0 nA 0 B U A 0 0 nA nB n0 nB 0 nA 0 B nA 0 nA 0 B 0 A 0 0 nA nB nC nB 0 C nA B nA CnA B C See exercise Epp6336 for the general inclusionexclusion rule for TL sets Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 1923 Problem 50 students replied to a survey of what computer program ming languages they knew A Students that know Java nA 30 B Students that know Fortran 713 18 C Students that know c nC 26 Further the survey reveals nA B 9 nA C 16 nB C 8 nAUBUC 47 Using the difference rule we find that the number of students that do not know any of the 3 languages nU nAUBUC50 473 Here U our universe is the set of all students who replied to the study Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 2023 nA 30 713 18 710 26 nA U B U C 47 nA B9nA C16nB C8 Using our derived inclusionexclusion formula for three set we find that the number of student that know all three languages are nAUBUC MA nB nC nB C nA B nA CnA B C 47 301826 9 16 8nA B C This gives us nA H B H C 6 We now have a complete picture Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 2123 nA 30 713 18 710 26 nA U B U C 47 nA B9nA C16nB C8nA B C6 B Fortran Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 2223 Homework 10 Due Wed 11222006 12noon GMCS587 Final Version Eppv30 Epp634 Epp636 Epp6311 Epp6318 Epp6325 Epp6326 Epp6328 Write down the inclusionexclusion principle for 4 sets hint Epp 6336 Eppv20 Epp634 Epp636 Epp6311 Epp6318 Epp6323 Epp6325 Write down the inclusionexclusion principle for 4 sets hint Epp 6333 Counting and Probability Permutations7 Addition Rule7 InclusionExclusion 7 p 2323

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

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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