 # 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:

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. 1 1 2 2 3 3 r r 1 1 2 2 3 3 r r m n P(“k matches”) = ? E |  |=? |E|=?

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.

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

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

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

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

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

Exercise 1 1 2 2 3 3 r r 1 1 2 2 3 3 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 1 1 1 1 1 1 1 1 1 2 3 3 4 6 4

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) 11

Negative Binomial Coefficients 這公式真的對嗎 ? k k k (n+k1)(n+k1) 11 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 )=? jk4jk4 jk6jk6 j  k  10 jkjk

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

Example 9

Chapter 2 Combinatorial Analysis Derangement

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

Example 10

 n 人中正好 k 人拿對自己的帽子  n 人中無人拿對自己的帽子 12 21 12 23 3 1312 1/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

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

Similar presentations