Chapter 2 Combinatorial Analysis 主講人 : 虞台文
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
Chapter 2 Combinatorial Analysis Basic Procedure for Probability Calculation
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.
Chapter 2 Combinatorial Analysis Counting
Goal of Counting Counting the number of elements in a particular set, e.g., a sample space, an event, etc.
Cases Ordered Samples w/ Replacement Ordered Samples w/o Replacement – Permutations Unordered Samples w/o Replacement – Combinations Unordered Samples w/ Replacement
Chapter 2 Combinatorial Analysis Ordered Samples with Replacement
Ordered Samples eat ate tea elements in samples appearing in different orders are considered different.
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.
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
Example 1 How many possible 16-bit binary words we may have? 2 distinct objects 16
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.
Chapter 2 Combinatorial Analysis Ordered Samples without Replacement Permutations
Permutations 清 心 也 可 以 可以清心也 以清心也可 清心也可以 心也可以清 也可以清心 可以清心也 以清心也可 清心也可以 心也可以清 也可以清心
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
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.
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 ) =?
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/| |.
Chapter 2 Combinatorial Analysis Unordered Samples without Replacement Combinations
Combinations n distinct objects Choose k objects How many choices?
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
More on
Examples
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,
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,
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 r r r r m n P(“k matches”) = ? E | |=? |E|=?
Example r r r r m n # possible outcomes from the 1 st box. # possible k -matches. # possible outcomes from the 2nd box for each k -match.
Example r r r r m n
r r r r m n 樂透和本例有何關係 ?
Example r r r r m n 本式觀念上係由第一口箱子出發所推得
Example r r r r m n 觀念上，若改由第二口箱子出發結果將如何 ?
Example r r r r m n
Exercise r r r r m n
Chapter 2 Combinatorial Analysis Binomial Coefficients
n terms
Binomial Coefficients n boxes
Binomial Coefficients Facts:
Properties of Binomial Coefficients
Exercise
Properties of Binomial Coefficients 第一類取法 : 第二類取法 :
Properties of Binomial Coefficients Pascal Triangular
Properties of Binomial Coefficients Pascal Triangular
Properties of Binomial Coefficients 吸星大法
Example 7-1
Example 7-2 k x+1 Fact: ?
Example 7-2 k k+1 簡化版
Example 7-3 k k+2 簡化版 ?
Negative Binomial Coefficients
How to memorize? k k k (n)(n) 11
Negative Binomial Coefficients 這公式真的對嗎 ? k k k (n+k1)(n+k1) 11 1
Negative Binomial Coefficients
Chapter 2 Combinatorial Analysis Some Useful Mathematic Expansions
z 值沒有任何限制
Some Useful Mathematic Expansions
Chapter 2 Combinatorial Analysis Unordered Samples with Replacement
Discussion 投返 非投返 有序 無序 ?
Unordered Samples with Replacement n 不同物件任取 k 個 可重複選取 n 不同物件，每一 中物件均無窮多個 從其中任取 k 個
Unordered Samples with Replacement 此多項式乘開後 z k 之係數有何意義 ?
Unordered Samples with Replacement
投返 非投返 有序 無序
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
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 有幾種取法 觀察 :
Example 9 此多項式乘開後 z k 之係數卽為解
Example 9 此多項式乘開後 z k 之係數卽為解
Example 9 此多項式乘開後 z k 之係數卽為解 Coef(z k )=?
Example 9 Coef(z k )=? jk4jk4 jk6jk6 j k 10 jkjk
Example 9 Coef(z k )=? jk4jk4 jk6jk6 j k 10 jkjk
Example 9
Chapter 2 Combinatorial Analysis Derangement
最後 ! ! ! 每一個人都拿 到別人的帽子 錯排
Example 10 n 人中正好 k 人拿 對自己的帽子 n 人中無人拿 對自己的帽子
Example 10
n 人中正好 k 人拿對自己的帽子 n 人中無人拿對自己的帽子 /2!2/3!
Example 10 n 人中正好 k 人拿對自己的帽子 n 人中無人拿對自己的帽子 令 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第 i 個人拿了自己帽子 12n 1...
Example 10 A i 表第 i 個人拿了自己帽子 12n 12...
Example 10 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第 i 個人拿了自己帽子
Example 10 A i 表第個人拿了自己帽子
Example 10
... k matches n k mis matches
Example 10
Remark
Chapter 2 Combinatorial Analysis Calculus
Some Important Derivatives Derivatives for multiplications — Derivatives for divisions — Chain rule —
L’Hopital rule
Examples
Integration by Part
The Gamma Function
Example 12
0 ( 1)
Example 12