Create Presentation
Download Presentation

Download Presentation
## Some other set notation

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Some other set notation**We will use the notation to mean that e is an element of A. We will use the notation to mean that e is not an element of A.**We will use the notation**to mean that A is a subsetB. (B is a superset of A.) B A**Union and Intersection**more than two events**Union:**E2 E3 E1**Intersection:**E2 E3 E1**Suppose we are observing a random phenomena**Let S denote the sample space for the phenomena, the set of all possible outcomes. An event E is a subset of S. A probability measureP is defined on S by defining for each event E, P[E] with the following properties • P[E] ≥ 0, for each E. • P[S] = 1.**P[E1]**P[E2] P[E3] P[E4] P[E5] P[E6] …**Example: Finite uniform probability space**In many examples the sample space S = {o1, o2, o3, … oN} has a finite number, N, of oucomes. Also each of the outcomes is equally likely (because of symmetry). Then P[{oi}] = 1/N and for any event E**Note:**with this definition of P[E], i.e.**Thus this definition of P[E], i.e.**satisfies the axioms of a probability measure • P[E] ≥ 0, for each E. • P[S] = 1.**R**Another Example: We are shooting at an archery target with radius R. The bullseye has radius R/4. There are three other rings with width R/4. We shoot at the target until it is hit S = set of all points in the target = {(x,y)| x2 + y2≤ R2} E, any event is a sub region (subset) of S.**E**E, any event is a sub region (subset) of S.**Thus this definition of P[E], i.e.**satisfies the axioms of a probability measure • P[E] ≥ 0, for each E. • P[S] = 1.**Finite uniform probability space**Many examples fall into this category • Finite number of outcomes • All outcomes are equally likely To handle problems in case we have to be able to count. Count n(E) and n(S).**Rule 1**Suppose we carry out have a sets A1, A2, A3, … and that any pair are mutually exclusive (i.e. A1 A2 = f) Let ni = n (Ai) = the number of elements in Ai. Let A = A1A2A3 …. Then N = n( A ) = the number of elements in A = n1 + n2 + n3 + …**A1**A2 n1 n2 A3 A4 n3 n4**Rule 2**Suppose we carry out two operations in sequence Let n1 = the number of ways the first operation can be performed n2 = the number of ways the second operation can be performed once the first operation has been completed. Then N = n1n2 = the number of ways the two operations can be performed in sequence.**Examples**• We have a committee of 10 people. We choose from this committee, a chairman and a vice chairman. How may ways can this be done? Solution: Let n1 = the number of ways the chairman can be chosen = 10. Let n2 = the number of ways the vice-chairman can be chosen once the chair has been chosen = 9. Then N = n1n2 = (10)(9) = 90**In Black Jack you are dealt 2 cards. What is the probability**that you will be dealt a 21? Solution: The number of ways that two cards can be selected from a deck of 52 is N = (52)(51) = 2652. A “21” can occur if the first card is an ace and the second card is a face card or a ten {10, J, Q, K} or the first card is a face card or a ten and the second card is an ace. The number of such hands is (4)(16) +(16)(4) =128 Thus the probability of a “21” = 128/2652 = 32/663**Rule 3**Suppose we carry out k operations in sequence Let n1 = the number of ways the first operation can be performed ni = the number of ways the ith operation can be performed once the first (i - 1) operations have been completed. i = 2, 3, … , k Then N = n1n2 … nk= the number of ways the k operations can be performed in sequence.**ì**ï ï í ï ï î Diagram:**Examples**• Permutations: How many ways can you order n objects Solution: Ordering n objects is equivalent to performing n operations in sequence. • Choosing the first object in the sequence (n1 = n) 2. Choosing the 2nd object in the sequence (n2 = n -1). … k. Choosing the kth object in the sequence (nk= n – k + 1) … n. Choosing the nth object in the sequence (nn= 1) The total number of ways this can be done is: N = n(n – 1)…(n – k + 1)…(3)(2)(1) = n!**Example How many ways can you order the 4objects**{A, B, C, D} Solution: N = 4! = 4(3)(2)(1) = 24 Here are the orderings.**Examples - continued**• Permutations of size k (< n): How many ways can you choose k objects from n objects in a specific order Solution:This operation is equivalent to performing k operations in sequence. • Choosing the first object in the sequence (n1 = n) 2. Choosing the 2nd object in the sequence (n2 = n -1). … k. Choosing the kth object in the sequence (nk= n – k + 1) The total number of ways this can be done is: N = n(n – 1)…(n – k + 1) = n!/ (n – k)! This number is denoted by the symbol**Definition: 0! = 1**This definition is consistent with for k = n**Solution:**Example How many permutations of size 3 can be found in the group of 5objects {A, B, C, D, E}**Example We have a committee of n = 10 people and we want to**choose a chairperson, a vice-chairperson and a treasurer Solution: Essentually we want to select 3 persons from the committee of 10 in a specific order. (Permutations of size 3 from a group of 10).**Example We have a committee of n = 10 people and we want to**choose a chairperson, a vice-chairperson and a treasurer. Suppose that 6 of the members of the committee are male and 4 of the members are female. What is the probability that the three executives selected are all male? Solution: Again we want to select 3 persons from the committee of 10 in a specific order. (Permutations of size 3 from a group of 10).The total number of ways that this can be done is: This is the size, N = n(S), of the sample space S. Assume all outcomes in the sample space are equally likely. Let E be the event that all three executives are male**Hence**Thus if all candidates are equally likely to be selected to any position on the executive then the probability of selecting an all male executive is:**Examples - continued**• Combinations of size k ( ≤n): A combination of size k chosen from n objects is a subset of size k where the order of selection is irrelevant. How many ways can you choose a combination of size k objects from n objects (order of selection is irrelevant) Here are the combinations of size 3 selected from the 5 objects {A, B, C, D, E}**Important Notes**• In combinations ordering is irrelevant. Different orderings result in the same combination. • In permutations order is relevant. Different orderings result in the different permutations.**Solution: Let n1denote the number of combinations of size**k. One can construct a permutation of size k by: How many ways can you choose a combination of size k objects from n objects (order of selection is irrelevant) • Choosing a combination of size k (n1 = unknown) 2. Ordering the elements of the combination to form a permutation (n2 = k!)**The number:**is denoted by the symbol read “n choose k” It is the number of ways of choosing k objects from n objects (order of selection irrelevant). nCk is also called a binomial coefficient. It arises when we expand (x + y)n (the binomial theorem)**Proof: The term xkyn = kwill arise when we select x from k**of the factors of (x + y)n and select y from the remaining n – k factors. The no. of ways that this can be done is: Hence there will be terms equal to xkyn = k and**Pascal’s triangle – a procedure for calculating binomial**coefficients 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1**The two edges of Pascal’s triangle contain 1’s**• The interior entries are the sum of the two nearest entries in the row above • The entries in the nth row of Pascals triangle are the values of the binomial coefficients**Pascal’s triangle**1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1**Summary of counting results**Rule 1 n(A1A2A3 ….) = n(A1) + n(A2) + n(A3) + … if the sets A1, A2, A3, … are pairwise mutually exclusive(i.e. AiAj= f) Rule 2 N = n1n2 = the number of ways that two operations can be performed in sequence if n1 = the number of ways the first operation can be performed n2 = the number of ways the second operation can be performed once the first operation has been completed.**N = n1n2 … nk**= the number of ways the k operations can be performed in sequence if Rule 3 n1 = the number of ways the first operation can be performed ni = the number of ways the ith operation can be performed once the first (i - 1) operations have been completed. i = 2, 3, … , k**Basic counting formulae**• Orderings • Permutations The number of ways that you can choose k objects from n in a specific order • Combinations The number of ways that you can choose k objects from n (order of selection irrelevant)**Applications to some counting problems**• The trick is to use the basic counting formulae together with the Rules • We will illustrate this with examples • Counting problems are not easy. The more practice better the techniques**Application to Lotto 6/49**Here you choose 6 numbers from the integers 1, 2, 3, …, 47, 48, 49. Six winning numbers are chosen together with a bonus number. How many choices for the 6 winning numbers