Transcript File

Agenda
• Lecture Content:
 Discrete Probability
 Binomial and Combinatorial Identity
• Review UTS
Pokok Bahasan (Minggu 8-11)
Minggu ke
Topik
8
-
Peluang diskret
Koefisien binomial
Identitas kombinatorik
9
-
Algoritma rekursif
Relasi rekurensi
Penyelesaian relasi rekurensi
Fungsi pembangkit
10
-
Graf dan terminologi graf
Path dan cycle
Euler cycle dan Hamiltonian cycle
11
-
Representasi graf
Graf isomorfis
Graf planar
Permasalahan lintasan terpendek
Pokok Bahasan (Minggu 12-14)
Minggu ke
Topik
12
-
Terminologi dan karakterisasi pohon
Spanning Trees
Binary Trees
13
-
Tree traversals
Decision trees
Pohon isomorfis
Game trees
14
-
Kombinatorial sirkuit
Aljabar Boolean
Ujian Akhir Semester (UAS)
Discrete Probability
Finite Probability
If S is a finite sample space of equally likely
outcomes, and E is an event, that is, a subset of S,
then the probability of E is
P(E) = |E| / |S|
Example 1
- An urn contains four blue balls and five red
balls. What is the probability that a ball chosen
from the urn is blue?
- Answer: 4/9
- What is the probability that when two dice are
rolled, the sum of the numbers on the two dice
is 7?
- Possible outcome: 36
- Successful outcome: 6  (1,6), (2,5), (3,4),
(4,3), (5,2), (6,1)
- Answer: 6/36
Example 2
- In a lottery, players win a large prize when they
pick four digits that match, in the correct order,
four digits selected by a random mechanical
process. What is the probability that a player
wins the large prize?
- To choose 4 digits = 104 = 10.000 ways
- To choose all 4 digits correctly: 1
- Answer: 1/10.000 = 0.0001
Example 3
- What is the probability that a person picks the
correct six numbers out of 40?
- The total number of ways to choose six
numbers out of 40 is:
C(40,6) = 40! / (34! * 6!) = 3.838.380
Answer: 1 / 3.838.380 ≈ 0,00000026
Example 4
- What is the probability that 11, 4, 17, 39, 23 are
drawn in that order from a bin containing 50
balls labeled with the number 1,2,…50, if :
- The ball selected is not returned to the bin
before the next ball is selected
Answer: 1 / (50 * 49 * 48 * 47 * 46)
1 / 254.251.200
- The ball is selected is returned to the bin
before the next ball is selected
Answer: 1 / (50 * 50 * 50 * 50 * 50)
1 / 312.500.000
Example 4
How many different license plates are available if
each plate contains a sequence of three letters
followed by three digits?
26 choices for each of the three letters and 10
choices for each of the three digits.
Total: 26 . 26 . 26 . 10 . 10 . 10 = 17,576,000
possible license plates
Assigning Probability
- Let S be the sample space of an experiment
and P(s) is the probability to each outcome s,
then:
(i) 0 ≤ P(s) ≤ 1 for each s  S
(ii) ∑sS P(s) = 1
- P: probability distribution
Example
-What probabilities should we assign to the
outcomes H (heads) and T (tails) when a fair coin
is flipped?
P(H) = P(T) = ½
-What probabilities should be assigned to these
outcomes when the coin is biased so that heads
comes up twice as often as tails?
P(H) = 2 * P(T)
P(H) + P(T) = 1
2 * P(T) + P(T) = 1
P(T) = 1/3; P(H) = 2/3
Uniform Distribution
- Suppose that S is a set with n elements. The
uniform distribution assigns the probability 1/n
to each element of S.
- The probability of the event E is the sum of the
probabilities of the outcomes in E. That is:
P(E) = ∑sE P(s)
Example
- Suppose that a dice is biased so that 3 appears
twice as often as each other number but that the
other five outcomes are equally likely. What is
the probability that an odd number appears when
we roll this die?
- E = {1, 3, 5}
- p(1) = p(2) = p(4) = p(5) = p(6) = 1/7
- p(3) = 2/7
- p(E) = p(1) + p(3) + p(5) = 4/7
Complement of Events
Let E be an event in a sample space S,
the probability of the event E (The
complementary event of E) is given by:
p(E) = 1 – p(E)
Example
- A sequence of 10 bits is randomly generated.
What is the probability that at least one of
these bits is 0?
- E : be the event that at least one of the 10 bits
is 0.
- E : be the event that all the bits are 1s.
- p(E) = |E| / |S| = 1/210 = 1/1024
- p(E) = 1 – p(E) = 1 – 1/1024 = 1023/1024
Combination of events E1 and E2
- Let E1 and E2 be events in the sample space
S. Then
p(E1E2) = p(E1) + p(E2) – p(E1E2)
| E1  E2 | | E1 |  | E2 |  | E1  E2 |
p( E1  E2 ) 

|S|
|S|
Example 1
- What is the probability that a positive integer
selected at random from the set of positive
integers not exceeding 100 is divisible by
either 2 or 5?
- E1 : the event that the integer selected is
divisible by 2
- E2 : be the event that it is divisible by 5.
- E1  E2 : the event that it is divisible by either
2 or 5
- E1  E2 : the event that it is divisible by both
2 and 5 (divisible by 10)
Example 1
- |E1| = {2, 4, 6, …, 100} = 50
- |E2| = {5, 10, …, 100} = 20
- |E1  E2| = {10, 20, …, 100} = 10
p(E1E2) = p(E1) + p(E2) – p(E1E2)
= 50/100 + 20/100 – 10/100
= 3/5
Mutually Exclusive of events E1 and E2
- Let E1 and E2 be events in the sample space
S. Then
p(E1E2) = p(E1) + p(E2)
| E1  E2 | | E1 |  | E2 |
p( E1  E2 ) 

|S|
|S|
Conditional Probability: Illustration
- Suppose that we flip a coin three times, and all 8
possibilities are equally likely. Suppose we know that
the event F, that the first flip comes up tails, occurs.
Given this information, what is the probability of the
event E, that an odd number of tails appears?
- Because the first flip comes up tails, there are only
four possible outcomes: TTT, TTH, THT, and THH,
where H and T represent heads and tails, respectively.
An odd number of tails appears only for the outcomes
TTT and THH.
- p(E) = 2/4 = 1/2 , given F occurs.
 the conditional probability of E given F
Conditional Probability
- Let E and F be events with p(F) > 0. the
conditional probability of E given F, denoted
by p(E | F), is defined as:
p(E | F) = p(E ∩ F) / p(F)
Example 1
- A bit string of length 4 is generated at random
so that each of the 16 bit strings of length four
is equally likely. What is the probability that it
contains at least two consecutive 0s, given
that its first bit is a 0?
- E: a bit string of length 4 contains at least two
consecutive 0s.
- F: the first bit of a bit string of length 4 is a 0.
- p(E|F) =p(E  F)/p(F)
Example 1
(E  F) = {0000, 0001, 0010, 0011, 0100}
p(E  F) = 5/16
p(F) = 8/16
p(E | F) = 5/8
Example 2
- What is the conditional probability that a
family with two children has two boys, given
they have at least one boy?
- Possibilities: BB, BG, GB, GG
- E: a family with 2 children has two boys, {BB)
- F: a family with 2 children has at least one boy
{BB, BG, GB}
- E  F = {BB}
- p(F) = 3/4 ; p(E  F) = ¼
- p(E|F) = p(E  F) / p(F) = 1/3
Independent Events
- Two events are independent if the occurrence
of one of the events gives no information
about the probability that the other event
occurs.
- The events E and F are independent if and
only if
p(E  F) = p(E) * p(F)
Example
- Suppose E is the event that a randomly generated bit
string of length four begins with a 1 and F is the event
that a randomly generated bit string of length four
contains an even number of 1s. Are E and F
independent, if the 16 bit strings of length four are
equally likely?
- E: begin with a one: 1000, 1001, 1010, 1011, 1100, 1101,
1110, 1111
- F: contains even numbers of ones: 0000, 0011, 0101,
0110, 1001, 1010, 1100, 1111
- p(E) = p(F) = 8/16 = ½
- E  F = {1111, 1100, 1010, 1001}
- p(E  F) = 4/16 = ¼ = p(E) * p(F)
 E and F are independent
Example
- E: a family with 2 children has two boys
- F: a family with 2 children has at least one boy
- Independent?
-
Possibilities: BB, BG, GB, GG
E: {BB)
F: {BB, BG, GB}
E  F = {BB}
p(E) = ¼; p(F) = 3/4 ; p(E  F) = ¼
p(E) * p(F) = ¼ * ¾ = 3/16
p(E  F)  P(E) * p(F)
 E and F are not independent
Binomial Coefficients
&
Combinatorial Identities
Expansion (a+b)n using Combination
(a+b)3 = (a+b)(a+b)(a+b)
= aaa+ aab+ aba+ abb+ baa+ bab+ bba+ bbb
= a3+ a2b+ a2b+ ab2+ a2b+ ab2+ ab2+ b3
= a3+ 3a2b+ 3ab2+ b3
(a+b)n =
C(n,0)anb0
+ C(n,1)an-1b1
+ C(n,2)an-2b2
+ ···
+ C(n,n-1)a1bn-1
+ C(n,n)a0bn
Binomial Theorem
Pascal’s Triangle & Combinatorial Identity
 Pascal’s triangle
The border consists of 1’s, and any interior value is the
sum of the two numbers above it.  see next slide
Theorem (Pascal’s Triangle)
C(n+ 1,k) = C(n,k–1) + C(n,k) for 1 ≤ k ≤ n.
 Combinatorial identity
An identity that results from some counting process
 Combinatorial argument
The argument that leads to the formulation of a
combinatorial identity
Pascal’s Traingle
Combinatorial Identities
Ref: Rosen, Discrete mathematics and its
applications