Transcript Document

Counting and Probability

The outcome of a random process is sure to occur,
but impossible to predict.




Examples: fair coin tossing, rolling a pair of dice, card drawing
from a well shuffled card deck, etc.
Sample space is the set of all possible outcomes of
a random process.
An event is a subset of a sample space.
The probability of an event is the ratio between the
number of outcomes that satisfy the event to the
total number of possible outcomes.
Possibility Trees

Teams A and B are to play each other
repeatedly until one wins two games in a row
or a total three games.


What is the probability that five games will be
needed to determine the winner?
Suppose there are 4 I/O units and 3 CPUs. In
how many ways can I/Os and CPUs be
paired with each other when there are no
restrictions?
Multiplication Rule

Multiplication rule: if an operation consists of k steps
each of which can be performed in ni ways (i = 1, 2,
…, k), then the entire operation can be performed in
ni ways.





Number of PINs with repetitions
Number of elements in a Cartesian product
Number of PINs without repetition
Number of Input/Output tables for a circuit with n input
signals
Number of iterations in nested loops
Multiplication Rule

Three officers – a president, a treasurer and
a secretary are to be chosen from four
people: Alice, Bob, Cindy and Dan. Alice
cannot be a president, Either Cindy or Dan
must be a secretary. How many ways can the
officers be chosen?
Permutations





A permutation of a set of objects is an
ordering of these objects.
The number of permutations of a set of n
objects is n! .
An r-permutation of a set of n elements is an
ordered selection of r elements taken from a
set of n elements: P(n, r)
P(n, r) = n! / (n – r)!
Show that P(n, 2) + P(n, 1) = n2
Exercises



How many odd integers are there from 10 through
99 that have distinct digits? (40)
How many numbers from 1 through 99999 contain
exactly one of each of the digits 2, 3, 4, and 5?
(720)
Let n = p1k1p2k2…pmkm.


How many divisors does n have?
What is the smallest integer with exactly 12 divisors? (60)
Addition Rule

If a finite set A is a union of k mutually disjoint
sets A1, A2, …, Ak, then N(A) =  N(Ai)



Number of words of length no more than 3
Number of 3-digit integers divisible by 5
The Difference Rule
If A is a finite set and B is its subset, then
N(A – B) = N(A) – N(B).

Example 6.3.3: How many 4-symbol PINs contain
repeated symbols? (Each symbol is chosen from the 26
letters of the alphabet and the ten digits)
Inclusion/Exclusion Rule

n(AUB) = n(A) + n(B) – n(A∩B).



Derive the above rule for 3 sets.
How many integers from 1 through 1000
are multiples of 3 or multiples of 5?
How many integers from 1 through 1000
are neither multiples of 3 nor multiples of 5?
Exercises

Suppose that out of 50 students, 30 know Pascal,
18 know Fortran, 26 know Cobol, 9 know both
Pascal and Fortran, 16 know both Pascal and
Cobol, 8 know Fortran and Cobol and 47 know at
least one programming language.



How many students know none of the three languages? (3)
How many students know all three languages? (6)
How many students know exactly 2 languages? (15)
Exercises


A calculator has an eight-digit display and a decimal
point which can be before, after or in between digits.
The calculator can also display a minus sign for
negative numbers. How many different numbers can
the calculator display? (Q. of Hw6)
A combination lock requires three selections of
numbers from 1 to 39. How many combinations are
possible if the same number cannot be used for
adjacent selections? (39*38*38)
Exercises



How many integers from 1 to 100000 contain the
digit 6 exactly once / at least once?
What is the probability that a random number from 1
to 100000 will contain two or more occurrences of
digit 6?
6 new employees, 2 of whom are married are
assigned 6 desks, which are lined up in a row. What
is the probability that the married couple will have
non-adjacent desks?
Exercises

Consider strings of length n over the set {a, b, c, d}:




How many such strings contain at least one pair of
consecutive characters that are the same?
If a string of length 10 is chosen at random, what is the
probability that it contains at least on pair of consecutive
characters that are the same?
How many permutations of abcde are there in which
the first character is a, b, or c and the last character
is c, d, or e?
How many integers from 1 through 999999 contain
each of the digits 1, 2, and 3 at least once?
Combinations



An r-combination of a set of n elements is a
subset of r of the n elements, denoted C(n, r)
n
or  r  .
 
Permutation is an ordered selection;
combination is an unordered selection.
Quantitative relationship between permutations
and combinations:


P(n, r) = C(n, r) * r!
See slides later for permutations of a set with
repeated elements.
Team Selection Problems

12 people, 5 men and 7 women, work on a project:


How many 5-person teams can be chosen? C(12,5)
If two people insist on working together (or not working at
all), how many 5-person teams can be chosen?
C(10,3)+C(10,5)


If two people insist on not working together, how many 5person teams can be chosen? C(10,5)+C(10,4)*2
How many 5-person teams consist of 3 men and 2 women?
C(5,3)*C(7,2)

How many 5-person teams contain at least 1 man?
C(12,5)-C(7,5)

How many 5-person teams contain at most 1 man?
C(7,5)+C(5,1)*C(7,4)
Similar Exercises

An instructor gives an exam with 14 questions.
Students are allowed to choose any 10 of them to
answer:
Suppose 6 questions require proof and 8 do not:
 How many groups of 10 questions contain 4 that require a
proof and 6 that do not?
 How many groups of 10 questions contain at least one that
require a proof?
 How many groups of 10 questions contain at most 3 that
require a proof?
A student council consists of 3 freshmen, 4 sophomores, 3
juniors and 5 seniors. How many committees of eight members
contain at least one member from each class?


Permutations with Repetition

Suppose a collection consists of n objects of which
n1 are of type 1 and are indistinguishable from each other
n2 are of type 2 and are indistinguishable from each other
…
nk are of type k and are indistinguishable from each other,
and suppose n1+n2+ …+nk =n. Then the number of
n!
distinct permutations of the n objects is
n !n ! n !
Example: How many distinguishable orderings of the
letters in the word MISSISSIPPI are there?
1

2
k
Combinations with Repetition

An r-combination with repetition allowed is an unordered
selection of elements where some elements can be
repeated.

The number of r-combinations with repetition allowed
from a set of n elements is
 C(r + n –1, r)

Example: How many triples of integers from 1 through n
can be formed in which the elements of the triple are in
increasing order but not necessarily distinct?
Integral Equations


How many non-negative integer solutions are
there to the equation x1 + x2 + x3 + x4 = 10?
How many positive integer solutions are there
for the above equation?
Algebra of Combinations and
Pascal’s Triangle

The number of r-combinations from a set of n
elements equals the number of (n – r)combinations from the same set. Namely,



C(n,r)=C(n, n-r)
Show that C(n, 0)2 + C(n, 1)2 + … + C(n, n)2 =
C(2n, n).
Pascal’s Formula:
Let n and r be positive integers and r ≤ n. Then
 C(n + 1, r) = C(n, r – 1) + C(n, r)
Binomial Theorem

(a + b)n = C(n, k)an-kbk



Show that C(n, k) = 2n
Show that (-1)kC(n, k) = 0.
Express C(n, k)3k in the closed form.