UCLA STAT 100A Introduction to Probability TheoryPowerPoint PresentationTheory of Counting = Combinatorial AnalysisSlide 4Permutation & CombinationSlide 6Slide 7Slide 8ExamplesSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Binomial theorem & multinomial theoremMultinomial theoremSlide 21Number of integer solutions to linear equ’sExampleSlide 24Sterling Formula for asymptotic behavior of n!Probability and Venn diagramsSlide 27Slide 28Slide 29Slide 30Slide 31Stat 100A, UCLA, Ivo DinovSlide 1UCLA STAT 100A Introduction to Probability TheoryInstructor: Ivo Dinov, Asst. Prof. In Statistics and NeurologyTeaching Assistant: Romeo Maciuca, UCLA Statistics University of California, Los Angeles, Fall 2002http://www.stat.ucla.edu/~dinov/Stat 100A, UCLA, Ivo DinovSlide 2UCLA STAT 10 Introduction to Statistical Reasoning Course Description, Class homepage, online supplements, VOH’s etc.http://www.stat.ucla.edu/~dinov/courses_students.htmlStat 100A, UCLA, Ivo DinovSlide 3Principle of Counting: If 2 experiments are performed and the first one has N1 possible outcomes, the second (independent) experiment has N2 possible outcomes then the number of outcomes of the combined (dual) experiment is N1 x N2.E.g., Suppose we have 5 math majors in the class, each carrying 2 textbooks with them. If I select a math major student and 1 textbook at random, how many possibilities are there? 5x2=10Theory of Counting = Combinatorial AnalysisStat 100A, UCLA, Ivo DinovSlide 4Generalized Principle of Counting: If M (independent) experiments are performed and the first one has Nm possible outcomes, 1<=m<=M, then the TOTAL number of outcomes of the combined experiment is N1xN2x … x NM.E.g., How many binary functions [f(i)=0 or f(i)=1], defined on a grid 1, 2, 3, …, n, are there? How many numbers can be stored in 8 bits = 1 byte? 2 x 2 x … x 2= 2nTheory of Counting = Combinatorial AnalysisStat 100A, UCLA, Ivo DinovSlide 5Permutation: Number of ordered arrangements of r objects chosen from n distinctive objectse.g. P63 = 6·5·4 =120.Permutation & CombinationrrrnnnnPPP ·)1()2)(1(  rnnnnPrnStat 100A, UCLA, Ivo DinovSlide 6Combination: Number of non-ordered arrangements of r objects chosen from n distinctive objects:Or use notation of e.g. 3!=6 , 5!=120 , 0!=1 Permutation & Combination!)!(!!/rrnnrPCrnrn rnnrC 35!3!4!773Stat 100A, UCLA, Ivo DinovSlide 7Combinatorial Identity:Analytic proof: (expand both hand sides)Combinatorial argument: Given n object focus on one of them (obj. 1). There are groups of size r that contain obj. 1 (since each group contains r-1 other elements out of n-1). Also, there are groups of size r, that do not contain obj1. But the total of all r-size groups of n-objects is !Permutation & Combination     111nrnrnr11rnrn 1rnStat 100A, UCLA, Ivo DinovSlide 8Combinatorial Identity:Analytic proof: (expand both hand sides)Combinatorial argument: Given n objects the number of combinations of choosing any r of them is equivalent to choosing the remaining n-r of them (order-of-objs-not-important!)Permutation & Combination   nrnnr Stat 100A, UCLA, Ivo DinovSlide 9Examples1. Suppose car plates are 7-digit, like AB1234. If all the letters can be used in the first 2 places, and all numbers can be used in the last 4, how many different plates can be made? How many plates are there with no repeating digits?Solution: a) 26·26·10·10·10·10 b) P262 · P103 = 26·25·10·9·8·7Stat 100A, UCLA, Ivo DinovSlide 10Examples2. How many different letter arrangement can be made from the 11 letters of MISSISSIPPI?               1154941122264104111 ... Solution: There are: 1 M, 4 I, 4 S, 2 P letters.Method 1: consider different permutations: 11!/(1!4!4!2!)=34650Method 2: consider combinations:Stat 100A, UCLA, Ivo DinovSlide 11Examples3. There are N telephones, and any 2 phones are connected by 1 line. Then how many lines are needed all together?Solution: C2N = N (N - 1) / 2If, N=5, complete graph with 5 nodes hasC25=10 edges.Stat 100A, UCLA, Ivo DinovSlide 124. N distinct balls with M of them white. Randomly choose n of the N balls. What is the probability that the sample contains exactly m white balls (suppose every ball is equally likely to be selected)?Examples  MNmnMm    NnMNmnMm/Solution: a) For the event to occur, m out of M whiteballs are chosen, and n-m out of N-M non-whiteballs are chosen. And we get b) Then the probability isStat 100A, UCLA, Ivo DinovSlide 13Examples5. N boys ( ) and M girls ( ), M<=N+1, stand in 1 line. How many arrangements are there so that no 2 girls stand next to each other? 1NMSolution: N!· ·M!There are M! ways of ordering the girls amongthemselves. NOTE – if girls are indistinguishablethen there’s no need for this factor!There are N! ways of orderingthe boys among themselvesThere are N+1 slots for the girls to fill between the boysAnd there are M girls to position in these slots, hencethe coefficient in the middle.How about they are arranged in a circle?Answer: N! M!E.g., N=3, M=2 NMStat 100A, UCLA, Ivo DinovSlide 14Examples 1NMSolution:5a. How would this change if there are N functional ( ) and M defective chips ( ), M<=N+1, in an assembly line?There are N+1 slots for the girls to fill between the boysAnd there are M girls to position in these slots, hencethe coefficient in the middle.Stat 100A, UCLA, Ivo DinovSlide 15Examples 1NMSolution:5a. How would this change if there are N functional ( ) and M defective chips ( ), M<=N+1, in an assembly line?There are N+1 slots for the girls to fill between the boysAnd there are M girls to position in these slots, hencethe coefficient in the middle.Stat 100A, UCLA, Ivo DinovSlide 16Binomial theorem & multinomial theoremDeriving from this, we can get such useful formula (a=b=1)Also from (1+x)m+n=(1+x) m(1+x)n we obtain: On the left is the coeff of 1kx(m+n-k). On the right is the same coeff in the product of (…+ coeff * x(m-i) +…) * (…+coeff * x(n-k+i) +…). knknknknbaba )(0      nnnnnn112...10    nikkiminmk 0Binomial theoremStat 100A, UCLA, Ivo DinovSlide