Proba Combinatorics

Probability
Conditional probability
Marginal Probability
What’s a Probability ?
In mathematical terms, a first approach to the probability notion consists of considering a

probability on a finite set 𝜴 is an application from 𝜴 in 𝟎, 𝟏 , such that
%𝒑 𝝎 =𝟏
𝝎∈𝛀
Probabilistic Independence between two events
Two events 𝑨 and 𝑩 are independent i.o.i. ⇔ 𝑷 𝑨 ∩ 𝑩 = 𝑷 𝑨 𝑷 𝑩
Given a set of events 𝑨𝒊 mutually 𝐢𝐧𝐝𝐞𝐩𝐞𝐧𝐝𝐞𝐧𝐭 if and only if

𝒏 𝒏
𝑷 𝑨𝟏 ∩ ⋯ ∩ 𝑨𝒏 = 𝑷 . 𝑨𝒊 = / 𝑷(𝑨𝒊 )
𝒊+𝟏 𝒊+𝟏
Conditional probability
llustration of conditional probabilities with an Euler or Venn

diagram. We have the a priori probability
𝑷 𝑨 = 𝟎. 𝟑𝟎 + 𝟎. 𝟏𝟎 + 𝟎. 𝟏𝟐 = 𝟎. 𝟓𝟐
And conditional probabilities are as follows:
• 𝑃 𝐴Ι𝐵$ = ? 1
0.12
• 𝑃 𝐴Ι𝐵% = ? 0.12 + 0.04 = 0.75
• 𝑃 𝐴Ι𝐵& = ? 0
Chain rule (total probabilities)
𝑰𝒇 𝑩𝒊 𝒊∈𝑰 𝑖𝑠 𝑎𝑛 𝑒𝑥ℎ𝑎𝑢𝑠𝑡𝑖𝑣𝑒 𝑠𝑒𝑡 𝑜𝑓 𝑒𝑣𝑒𝑛𝑡𝑠, (i.e. ∀𝒊 ≠ 𝒋, 𝑩𝒊 ⋂𝑩𝒋 = ∅ 𝒂𝒏𝒅 ⋃𝒊∈𝑰 𝑩𝒊 = 𝜴) ,

𝒂𝒏𝒅 𝒊𝒇 ∀𝒊 ∈ 𝑰 , 𝑷 𝑩𝒊 ≠ 𝟎, then
𝑷 𝑨 = ∑𝒊∈𝑰 𝑷 𝑨𝚰𝑩𝒊 𝑷 (𝑩𝒊 ) = ∑𝒊∈𝑰 𝑷 𝑨 ∩ 𝑩𝒊

Bayes theorem
𝑷 𝑩\𝑨 𝑷(𝑨) A priori distribution

A posteriori Distribution 𝑷 𝑨\𝑩 =
𝑷(𝑩) Marginal distribution
The calculation of 𝑷(𝑩) depends on its field of application. In numerical

science, it is named "proof" to denote the marginal likelihood function,
and applied in medicine, it denotes a likelihood ratio.
Combinatorial analysis
Enumerative
combinatorics
Combinatorics
▪ Count the number of ways to put things

together into various combinations.
e.g. If a password is 6-8 letters and/or digits,
how many passwords can there be?
▪ Two main rules:
▪ Sum rule
▪ Product rule
Sum Rule
▪ Let us consider two tasks:

▪ m is the number of ways to do task 1
▪ n is the number of ways to do task 2
▪ Tasks are independent of each other, i.e.,
▪ Performing task 1 does not accomplish task 2 and vice
versa.
▪ Sum rule: the number of ways that “either task 1 or
task 2 can be done, but not both”, is m+n.
▪ Generalizes to multiple tasks ...
Example
▪ A student can choose a computer project from one of

three lists. The three lists contain 23, 15, and 19
possible projects respectively. How many possible
projects are there to choose from?
10
Set Theoretic Version
▪ If A is the set of ways to do task 1, and B

the set of ways to do task 2, and if A and
B are disjoint, then:
“the ways to do either task 1 or 2 are

AÈB, and |AÈB|=|A|+|B|”
Product Rule
▪ Let us consider two tasks:

▪ m is the number of ways to do task 1
▪ n is the number of ways to do task 2
▪ Tasks are independent of each other, i.e.,
▪ Performing task 1does not accomplish task 2 and
vice versa.
▪ Product rule: the number of ways that “both tasks
1 and 2 can be done” is m x n.
▪ Generalizes to multiple tasks ...
Example
▪ The chairs of an auditorium are to be labeled

with a letter and a positive integer not to exceed
100. What is the largest number of chairs that
can be labeled differently?
Set Theoretic Version
▪If A is the set of ways to do task 1, and

B the set of ways to do task 2, and if A
and B are disjoint, then:
▪The ways to do both task 1 and 2 can
be represented as A´B, and
|A´B|=|A|·|B|
Example
▪ How many different license plates

are available if each plate contains a
sequence of three letters followed by
three digits?
Example Using Both Rules
▪ Each user on a computer system has a

password, which is six to eight characters
long where each character is an
uppercase letter or a digit. Each password
must contain at least one digit. How many
possible passwords are there?
IP Address Example
(Internet Protocol vers. 4)
▪ Main computer addresses are in one of 3 types:

▪ Class A: address contains a 7-bit “netid” ≠ 17, and a 24-bit “hostid”
▪ Class B: address has a 14-bit netid and a 16-bit hostid.
▪ Class C: address has 21-bit netid and an 8-bit hostid.
▪ Hostids that are all 0s or all 1s are not allowed.
▪ How many valid computer addresses are there?

Inclusion-Exclusion Principle
(relates to the “sum rule”)
▪ Suppose that k£m of the ways of doing

task 1 also simultaneously accomplishes
task 2. (And thus are also ways of doing
task 2.)
▪ Then the number of ways to accomplish
“Do either task 1 or task 2” is m+n-k.
▪ Set theory: If A and B are not disjoint,
then |AÈB|=|A|+|B|-|AÇB|.
Example
▪ Hypothetical rules for passwords:

▪ Passwords must be 2 characters long.
▪ Each password must be a letter a-z, a
digit 0-9, or one of the 10 punctuation
characters !@#$%^&*().
▪ Each password must contain at least 1
digit or punctuation character.
Sol. Cont’d
▪ A legal password has a digit or punctuation character

in position 1 or position 2.
▪ These cases overlap, so the principle applies.
▪ (# of passwords w. OK symbol in
position #1) = (10+10)·(10+10+26)
▪ (# w. OK sym. in pos. #2): also 20·46
▪ (# w. OK sym both places): 20·20
▪ Answer: 920+920−400 = 1,440
Permutations
▪ A permutation of a set S of objects is an ordered

arrangement of the elements of S where each
element appears only once:
e.g., 1 2 3, 2 1 3, 312
▪ An ordered arrangement of r distinct elements
of S is called an r-permutation.
▪ The number of r-permutations of a set S with
n=|S| elements is
P(n,r) = n(n−1)…(n−r+1) = n!/(n−r)!
Example
▪ How many ways are there to select a third-

prize winner from 100 different people
who have entered a contest?
More Examples
▪ How many permutations of the letters

ABCDEFG contain the string ABC?
Combinations
▪ The number of ways of choosing r elements

from S (order does not matter).
S={1,2,3}
e.g., 1 2 , 1 3, 23
▪ The number of r-combinations C(n,r) of a set
with n=|S| elements is
ænö n!
C (n, r ) = ç ÷ =
è r ø r !(n - r )!
Combinations vs Permutations
▪ Essentially unordered permutations …
P(n, r ) = C (n, r ) P(r , r )
æ n ö P(n, r ) n! /(n - r )! n!
C (n, r ) = çç ÷÷ = = =
è r ø P(r , r ) r! r!(n - r )!
▪ Note that C(n,r) = C(n, n−r)

Combination Example
▪ How many distinct 7-card hands can be drawn from a

standard 52-card deck?
▪ The order of cards in a hand doesn’t matter.
▪ Answer C(52,7) = P(52,7)/P(7,7)
= 52·51·50·49·48·47·46 / 7·6·5·4·3·2·1
17 10 7 8
52·17·10·7·47·46 = 133,784,560

Proba Combinatorics

Uploaded by

Copyright:

Available Formats

Proba Combinatorics

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Proba Combinatorics

Uploaded by

Copyright:

Available Formats

Probability

In mathematical terms, a first approach to the probability notion consists of considering a

Two events 𝑨 and 𝑩 are independent i.o.i. ⇔ 𝑷 𝑨 ∩ 𝑩 = 𝑷 𝑨 𝑷 𝑩

Given a set of events 𝑨𝒊 mutually 𝐢𝐧𝐝𝐞𝐩𝐞𝐧𝐝𝐞𝐧𝐭 if and only if

llustration of conditional probabilities with an Euler or Venn

𝑰𝒇 𝑩𝒊 𝒊∈𝑰 𝑖𝑠 𝑎𝑛 𝑒𝑥ℎ𝑎𝑢𝑠𝑡𝑖𝑣𝑒 𝑠𝑒𝑡 𝑜𝑓 𝑒𝑣𝑒𝑛𝑡𝑠, (i.e. ∀𝒊 ≠ 𝒋, 𝑩𝒊 ⋂𝑩𝒋 = ∅ 𝒂𝒏𝒅 ⋃𝒊∈𝑰 𝑩𝒊 = 𝜴) ,

𝑷 𝑨 = ∑𝒊∈𝑰 𝑷 𝑨𝚰𝑩𝒊 𝑷 (𝑩𝒊 ) = ∑𝒊∈𝑰 𝑷 𝑨 ∩ 𝑩𝒊

𝑷 𝑩\𝑨 𝑷(𝑨) A priori distribution

The calculation of 𝑷(𝑩) depends on its field of application. In numerical

▪ Count the number of ways to put things

▪ Let us consider two tasks:

▪ A student can choose a computer project from one of

▪ If A is the set of ways to do task 1, and B

“the ways to do either task 1 or 2 are

▪ Let us consider two tasks:

▪ The chairs of an auditorium are to be labeled

▪If A is the set of ways to do task 1, and

▪ How many different license plates

▪ Each user on a computer system has a

▪ Main computer addresses are in one of 3 types:

▪ Hostids that are all 0s or all 1s are not allowed.

▪ How many valid computer addresses are there?

▪ Suppose that k£m of the ways of doing

▪ Hypothetical rules for passwords:

▪ A legal password has a digit or punctuation character

▪ A permutation of a set S of objects is an ordered

▪ How many ways are there to select a third-

▪ How many permutations of the letters

▪ The number of ways of choosing r elements

▪ Essentially unordered permutations …

P(n, r ) = C (n, r ) P(r , r )

▪ Note that C(n,r) = C(n, n−r)

▪ How many distinct 7-card hands can be drawn from a

You might also like