Transcript Click

Counting
CSCA67 Fall, 2012
Nov. 12, 2012
TA: Yadi Zhao
www.utsc.utoronto.ca/~09zhaoya
S
Permutation
An arrangement (or ordering) of a set of
objects is called a permutation. (We can
also arrange just part of the set of
objects.)
In a permutation, the order that we
arrange the objects is important
Example 1
Consider arranging 3 letters: A, B,
C. How many ways can this be
done?
Theorem 1
n distinct objects can be arranged
in n! ways
Example 2
In how many ways can 4 different
students be arranged in a row?
Theorem 2
The number of permutations of n distinct
objects taken r at a time, where repetitions
are not allowed, is given by
n!/(n-r)!
Example 3
In how many ways can a
supermarket manager display 5
brands of cereals in 3 spaces on a
shelf ?
Example 4
How many different number-plates for
cars can be made if each number-plate
contains four of the digits 0 to 9
followed by a letter A to Z, assuming
that
(a) no repetition of digits is allowed?
(b) repetition of digits is allowed?
Theorem 3
The number of different permutations
of n objects of which n1 are of one
kind, n2 are of a second kind, ... nk are
of a k-th kind is
n! / (n1! * n2! *…nk!)
Example 5
In how many ways can the six
letters of the word "mammal" be
arranged in a row?
Theorem 4
There are (n−1)! ways to arrange n
distinct objects in a circle.
Example 6
In how many ways can 5 people be
arranged in a circle?
Exercise 1
How many numbers greater than 1000
can be formed with the digits 3,4,6,8,9
if a digit cannot occur more than once
in a number?
Exercise 2
How many different ways can 3 red,
4 yellow and 2 blue bulbs be
arranged in a string of Christmas
tree lights with 9 sockets?
Combination
A combination of n objects taken r
at a time is a selection which does
not take into account the
arrangement of the objects. That is,
the order is not important.
Number of Combinations
The number of ways (or combinations)
in which r objects can be selected from
a set of n objects, where repetition is
not allowed, is denoted by:
n! / (r!*(n-r)! )
Example 1
How many different sets of 4
different letters can be selected
from the alphabet?
Example 2
Find the number of ways in which
3 components can be selected from
a batch of 20 different
components.
Example 3
In how many ways can a group of 4
boys be selected from 10 if
(a) the eldest boy is included in each
group?
(b) the eldest boy is excluded?
(c) What proportion of all possible
groups contain the eldest boy?
Example 4
A class consists of 15 students of
whom 5 are girls. How many
committees of 8 can be formed if each
consists of
(a) exactly 2 girls? (b) at least 2 girls?
Example 5
Out of 5 mathematicians and 7 engineers, a
committee consisting of 2 mathematicians
and 3 engineers is to be formed. In how
many ways can this be done if
(a) any mathematician and any engineer can be
included?
Example 5
Out of 5 mathematicians and 7 engineers, a
committee consisting of 2 mathematicians
and 3 engineers is to be formed. In how
many ways can this be done if
(b) one particular engineer must be in
the committee?
Example 5
Out of 5 mathematicians and 7 engineers, a
committee consisting of 2 mathematicians
and 3 engineers is to be formed. In how
many ways can this be done if
(c) two particular mathematicians
cannot be in the committee?