Chapter 2 Combinatorial Analysis 主講人 : 虞台文. Content Basic Procedure for Probability Calculation Counting – Ordered Samples with Replacement – Ordered.

Presentation on theme: "Chapter 2 Combinatorial Analysis 主講人 : 虞台文. Content Basic Procedure for Probability Calculation Counting – Ordered Samples with Replacement – Ordered."— Presentation transcript:

1 Chapter 2 Combinatorial Analysis 主講人 : 虞台文

2 Content Basic Procedure for Probability Calculation Counting – Ordered Samples with Replacement – Ordered Samples without Replacement  Permutations – Unordered Samples without Replacement  Combinations Binomial Coefficients Some Useful Mathematic Expansions Unordered Samples with Replacement Derangement Calculus

3 Chapter 2 Combinatorial Analysis Basic Procedure for Probability Calculation

4 1. Identify the sample space . 2. Assign probabilities to certain events in A, e.g., sample point event P(  ). 3. Identify the events of interest. 4. Compute the desired probabilities.

5 Chapter 2 Combinatorial Analysis Counting

6 Goal of Counting Counting the number of elements in a particular set, e.g., a sample space, an event, etc.

7 Cases Ordered Samples w/ Replacement Ordered Samples w/o Replacement – Permutations Unordered Samples w/o Replacement – Combinations Unordered Samples w/ Replacement

8 Chapter 2 Combinatorial Analysis Ordered Samples with Replacement

9 Ordered Samples eat ate tea elements in samples appearing in different orders are considered different.

10 Ordered Samples w/ Replacement meet teem mete 1. Elements in samples appearing in different orders are considered different. 2. In each sample, elements are allowed repeatedly selected.

11 Ordered Samples w/ Replacement Drawing k objects, their order is noted, among n distinct objects with replacement. The number of possible outcomes is n distinct objects  k  k

12 Example 1 How many possible 16-bit binary words we may have? 2 distinct objects  16

13 Example 2 Randomly Choosing k digits from decimal number, Find the probability that the number is a valid octal number. For any , P(  )=1/10 k.

14 Chapter 2 Combinatorial Analysis Ordered Samples without Replacement  Permutations

15 Permutations 清 心 也 可 以 可以清心也 以清心也可 清心也可以 心也可以清 也可以清心 可以清心也 以清心也可 清心也可以 心也可以清 也可以清心

16 Ordered Samples w/o Replacement  Permutations Drawing k objects, their order is noted, among n distinct objects without replacement. The number of possible outcomes is n distinct objects  k  k

17 Example 3 Five letters are to be selected without replacement from the alphabet (size 26) to form a word (possibly nonsense). Find the probabilities of the following events? 1. Begin with an s. 2. Contains no vowel. 3. Begins and ends with a consonant. 4. Contains only vowels. Five letters are to be selected without replacement from the alphabet (size 26) to form a word (possibly nonsense). Find the probabilities of the following events? 1. Begin with an s. 2. Contains no vowel. 3. Begins and ends with a consonant. 4. Contains only vowels.

18 Example 3 Five letters are to be selected without replacement from the alphabet (size 26) to form a word (possibly nonsense). Find the probabilities of the following events? 1. Begin with an s. 2. Contains no vowel. 3. Begins and ends with a consonant. 4. Contains only vowels. Five letters are to be selected without replacement from the alphabet (size 26) to form a word (possibly nonsense). Find the probabilities of the following events? 1. Begin with an s. 2. Contains no vowel. 3. Begins and ends with a consonant. 4. Contains only vowels. Define E 1 : word begins with an s. E 2 : word contains no vowel. E 3 : word begins and ends with a consonant. E 4 : word contains only vowels. P(E 1 ) =? P(E 2 ) =? P(E 3 ) =? P(E 4 ) =?

19 Example 3 Define E 1 : word begins with an s. E 2 : word contains no vowel. E 3 : word begins and ends with a consonant. E 4 : word contains only vowels. P(E 1 ) =? P(E 2 ) =? P(E 3 ) =? P(E 4 ) =? For any , P(  )=1/|  |.

20 Chapter 2 Combinatorial Analysis Unordered Samples without Replacement  Combinations

21 Combinations n distinct objects Choose k objects How many choices?

22 Combinations Drawing k objects, their order is unnoted, among n distinct objects w/o replacement, the number of possible outcomes is This notation is preferred

23 More on

24 Examples

25 Example 4 The mathematics department consists of 25 full professors, and 15 associate professors, and 35 assistant professors. A committee of 6 is selected at random from the faculty of the department. Find the probability that all the members of the committee are assistant professors. x Denoting the all-assistant event as E,

26 Example 5 A poker hand has five cards drawn from an ordinary deck of 52 cards. Find the probability that the poker hand has exactly 2 kings. x Denoting the 2-king event as E,

27 Example 6 Two boxes both have r balls numbered 1, 2, …, r. Two random samples of size m and n are drawn without replacement from the 1 st and 2 nd boxes, respectively. Find the probability that these two samples have exactly k balls with common numbers. 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n P(“k matches”) = ? E |  |=? |E|=?

28 Example 6 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n # possible outcomes from the 1 st box. # possible k -matches. # possible outcomes from the 2nd box for each k -match.

29 Example 6 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n

30 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n 樂透和本例有何關係 ?

31 Example 6 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n 本式觀念上係由第一口箱子出發所推得

32 Example 6 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n 觀念上，若改由第二口箱子出發結果將如何 ?

33 Example 6 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n

34 Exercise 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n

35 Chapter 2 Combinatorial Analysis Binomial Coefficients

36

37

38 n terms

39 Binomial Coefficients n boxes

40 Binomial Coefficients Facts:

41 Properties of Binomial Coefficients

42

43

44 Exercise

45 Properties of Binomial Coefficients 第一類取法 :   第二類取法 :

46 Properties of Binomial Coefficients Pascal Triangular

47 Properties of Binomial Coefficients Pascal Triangular 1 1 1 1 1 1 1 1 1 2 3 3 4 6 4

48 Properties of Binomial Coefficients 吸星大法

49 Example 7-1

50 Example 7-2 k  x+1 Fact: ?

51 Example 7-2 k  k+1 簡化版

52 Example 7-3 k  k+2 簡化版 ?

53 Negative Binomial Coefficients

54 How to memorize? k k k (n)(n) 11

55 Negative Binomial Coefficients 這公式真的對嗎 ? k k k (n+k1)(n+k1) 11 1

56 Negative Binomial Coefficients

57 Chapter 2 Combinatorial Analysis Some Useful Mathematic Expansions

58

59

60

61

62

63

64

65 z 值沒有任何限制

66 Some Useful Mathematic Expansions

67 Chapter 2 Combinatorial Analysis Unordered Samples with Replacement

68 Discussion 投返 非投返 有序 無序 ?

69 Unordered Samples with Replacement n 不同物件任取 k 個 可重複選取 n 不同物件，每一 中物件均無窮多個 從其中任取 k 個

70 Unordered Samples with Replacement 此多項式乘開後 z k 之係數有何意義 ?

71 Unordered Samples with Replacement

72 投返 非投返 有序 無序

73 Example 8 Suppose there are 3 boxes which can supply infinite red balls, green balls, and blue balls, respectively. How many possible outcomes if ten balls are chosen from them? n = 3 k = 10

74 Example 9 There are 3 boxes, the 1st box contains 5 red balls, the 2nd box contains 3 green balls, and the 3rd box contains infinite many blue balls. How many possible outcomes if k balls are chosen from them. k=1 有幾種取法 k=2 有幾種取法 k=3 有幾種取法 k=4 有幾種取法 觀察 :

75 Example 9 此多項式乘開後 z k 之係數卽為解

76 Example 9 此多項式乘開後 z k 之係數卽為解

77 Example 9 此多項式乘開後 z k 之係數卽為解 Coef(z k )=?

78 Example 9 Coef(z k )=? jk4jk4 jk6jk6 j  k  10 jkjk

79 Example 9 Coef(z k )=? jk4jk4 jk6jk6 j  k  10 jkjk

80 Example 9

81

82 Chapter 2 Combinatorial Analysis Derangement

83 最後 ! ! ! 每一個人都拿 到別人的帽子 錯排

84 Example 10 n 人中正好 k 人拿 對自己的帽子 n 人中無人拿 對自己的帽子

85 Example 10

86  n 人中正好 k 人拿對自己的帽子  n 人中無人拿對自己的帽子 12 21 12 23 3 1312 1/2!2/3!

87 Example 10  n 人中正好 k 人拿對自己的帽子  n 人中無人拿對自己的帽子 令 A i 表第 i 個人拿了自己帽子

88 Example 10 A i 表第 i 個人拿了自己帽子

89 Example 10 A i 表第 i 個人拿了自己帽子 12n 1...

90 Example 10 A i 表第 i 個人拿了自己帽子 12n 12...

91 Example 10 A i 表第 i 個人拿了自己帽子

92 Example 10 A i 表第 i 個人拿了自己帽子

93 Example 10 A i 表第 i 個人拿了自己帽子

94 Example 10 A i 表第 i 個人拿了自己帽子

95 Example 10 A i 表第個人拿了自己帽子

96 Example 10

97 ... k matches n  k mis matches 

98 Example 10

99 Remark

100 Chapter 2 Combinatorial Analysis Calculus

101 Some Important Derivatives Derivatives for multiplications — Derivatives for divisions — Chain rule —

102 L’Hopital rule

103 Examples

104 Integration by Part

105

106 The Gamma Function

107 Example 12

108

109

110 0  (   1)

111 Example 12

112

113

114

115

116 

117