Session-3-permutaiton-combination-probability-排列組合和概率

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1. PERMUTATION Suppose n objects are to be ordered from 1st to nth, each order is called a permutation. Apply the multiplication principle to count the number of permutations of n objects, i.e. n(n-1)(n-2)(n-3).(3)(2)(1), or n!, called n factorial. e.g. Suppose that 10 students are goin

2、g on a bus trip, and each of the students will be assigned to one of the 10 available seats. What is the number of possible different seating arrangements of the students on the bus?Notice: n objects should be distinguishable and they are always ordered in a line.If the objects are not ordered in a

3、line but in other shapes, such as a circle or a square, how to calculate the number of permutations?e.g. Five students are going to sit around a table, how many arrangement can there be? (If the relative position of two students is the same, then we view it as one arrangement.)formula: (n-1)!If ther

4、e are some objects are exactly the same, the number of permutations should be calculated in another way. e.g. How many different five-letter words can be formed when all letters in the word ENTER are used each time. formula: n!/(number of repeated objects)!Suppose that k objects will be selected fro

5、m a set of n objects, where k<=n, and the k objects will be placed in order from 1st to kth. The number of permutation is n(n-1)(n-2).(n-k+1). e.g. How many different five-digit positive integers can be formed using the digits 1, 2, 3, 4, 5, 6, and 7 if none of the digits can occur more than once

6、 in the integer?2. Combination Given the five letters A, B, C, D, and E, determine the number of ways of selecting 3 of the 5 letters, but unlike before, you do not want to count different orders for the 3 letters. i.e. Note that n choose k is always equal to n choose n-ke.g. You should choose 3-per

7、son committee from a group of 9 students. How many ways are there to do this? The difference between permutation and combination is whether order is considered. If different order makes different arrangement, it is permutation, and if different order makes no difference, it is combination. Most prob

8、lems require us to combine these two. e.g. Suppose you want to choose 5 members from a group of 8 to watering 5 different gardens. How many ways to do this?3. Permutation & combination Multiplication Principle: If we need N steps to do a job and in the first step we have M1 different ways, secon

9、d M2, third M3., then we apply multiplication principle to count the total ways of doing this job, i.e. N=M1*M2*M3.*MnAddition Principle:If we have N different ways to do a job and in the first way we have M1 different ways, second M2, third M3., then we apply addition principle to count the total w

10、ays of doing this job, i.e. N=M1+M2+M3.+MnNotice: In multiplication principle steps are interdependent, while in addition principle each way can independently make the job done. General method to solve permutation & combination problems:1. Understand what needs to be done2. Decide whether to tak

11、e steps or divide into different ways, or both. When taking steps, how many steps are there; when dividing into different ways, how many ways in total.4. Make sure of the requirements in each step or way, permutation or combination, and calculate the number of arrangements in each step or each way.

12、5. Count the total ways using multiplication principle or addition principle.3.1 Give priorities to special elements and placese.g. How many different 5-digit odd numbers can be formed when choosing from 0, 1, 2, 3, 4, 5 and each number can be used only once? (key: 288) 3.2 Bundling Strategy e.g. Th

13、ere are 7 students to stand in a straight line. If student A and B should always stand side by side, so should student D and G, how many ways to line those 7 students? (key: 480)Remember to make permutation between bundling elements3.3 Slot strategy e.g. There is going to be 2 dances, 2 cross talks,

14、 and 1 solo in a party. If the 2 dances cannot be performed in a row, how many different program lists can we make for this party? (key: 72)Permutation first and then plug in the special elements3.4 More than one line problemse.g. Suppose you are going to arrange 8 students into two rows with four s

15、tudents in each row. Student A and B must be in the first row and Student C must in the second row. How many ways to arrange? (key:5760)Turn it into one straight line problem 3.5 Mixture problemse.g. Suppose we need to put 5 different balls into 4 different boxes and each box should contain at least

16、 one ball. How many ways to make this done? (key: 240)First choose and then order3.6 Plank strategye.g. An elementary school has 10 athlete quota to be assigned to 7 classes. If every class should have at least one quota, how many ways are there to assign? (key: 84)Pay attention to the differences b

17、etween 3.5 and 3.6 4. Probability Probability is a way of describing uncertainty in numerical terms. Probability experiment (random experiment)The set of all possible outcomes of a random experiment is called the sample space, and any particular set of outcomes is called an event. P(E)=the number of

18、 outcomes in the event/the number of possible outcomes in the experiment General facts about probability:l If an event E is certain to occur, then P(E)=1l If an even E is certain not to occur, then P(E)=0l If an even E is possible but not certain to occur, then 0<P(E)<1l The probability that a

19、n event E will not occur is equal to 1-P(E)l If E is an event, then the probability of E is the sum of the probabilities of outcomes in E.l The sum of the probabilities of all possible outcomes of an experiment is 1.If E and F are two events of an experiment, we consider two other events related to

20、E and F. l The event that both E and F occur, that is, all outcomes in the set l The event that E or F, or both, occur, that is , all outcomes in the set l P(E or F)=P(E)+P(F)-P(both E and F) l P(E or F)=P(E)+p(F) if E and F are mutually exclusivel P(E and F)=P(E)P(F) if E and F are independentl the

21、 probability of one event occurring k times during n independent experiments P(E)=e.g. A fair 6-sided die is rolled nine times and what's the probability that two of the nine are odd number?If a fair 6-sided die is rolled once, let E be the event of rolling a 3 and let F be the event of rolling

22、an odd number. What is the probability of both E and F occurring? A 12-sided die, with faces numbered 1 to 12, is to be rolled once, and each of the 12 possible outcomes is equally likely to occur. What is the probability of rolling a number that is either a multiple of 5 or an odd number?Consider a

23、n experiment with events A, B, and C for which P(A)=0.23, P(B)=0.40, and P(C)=0.85. Suppose that events A and B are mutually exclusive and events B and C are independent. What are the probabilities P(A or B) and P(B or C)? Suppose that there is a 6-sided die that is weighted in such a way that each

24、time the die is rolled, the probabilities of rolling any of the numbers from 1 to 5 are all equal, but the probability of rolling a 6 is twice the probability of rolling a 1. When you roll the die once, the 6 outcomes are not equally likely. What are the probabilities of the 6 outcomes?Suppose that

25、you roll the weighted 6-sided die from above example twice. What is the probability that the first roll will be an odd number and the second roll will be an even number?A box contains 5 orange disks, 4 red disks, and 1 blue disk. You are to select two disks at random and without replacement from the

26、 box. What is the probability that the first disk you select will be red and the second disk you select will be orange?There are going to be 5 different songs and 3 different dances in a particular party. How many ways to arrange the programs as follows?(1) three dances should be shown in a row(2) t

27、hree dances should be separated How many ways to divide 6 different books into three piles?How many ways to assign 6 different books to 3 persons and each has exactly two books?How many different 5-digit even numbers can be formed from 0, 2, 3, 6, and 9? (Each number should be used only once.)A. 120

28、B. 72C. 60D, 48E. 106 Xavier, Yvonne, and Zelda each try independently to solve a problem. If their individual probabilities for success are 1/4, 1/2 and 5/8, respectively, what is the probability that Xavier and Yvonne, but not Zelda, will solve the problem?(A)11/8(B)7/8(C)9/64(D)5/64(E)3/64Among a group of 2,500 people