Transcript Permutations and Combinations

Permutations and
Combinations
1.1 The Fundamental
Principle of
Multiplication
2015/7/21
Permutations and Combinations
1
P1
The Fundamental Principle of Multiplication
• If there are
• n1 ways of doing one
operation,
• n2 ways of doing a second
operation, n3 ways of doing a
third operation , and so forth,
2015/7/21
Permutations and Combinations
2
P1
• then the sequence of k
operations can be
performed in n1 n2 n3….. nk
ways.
• N= n1 n2 n3….. nk
2015/7/21
Permutations and Combinations
3
P1
Example 1
• A used car wholesaler has agents
who classify cars by size (full,
medium, and compact) and age (0 2 years, 2- 4 years, 4 - 6 years, and
over 6 years).
• Determine the number of possible
automobile classifications.
2015/7/21
Permutations and Combinations
4
P1
Solution
Full(F)
0-2
2-4
4-6
>6
0-2
2-4
4-6
>6
Medium(M)
Compact(C)
0-2
2-4
4-6
>6
The tree diagram enumerates all possible
classifications, the total number of which is 3x4= 12.
2015/7/21
Permutations and Combinations
5
P1
Example 2
• Mr. Chan has 2 pairs of trousers,
3 shirts and 2 ties.
• He chooses a pair of trousers, a
shirt and a tie to wear everyday.
• Find the maximum number of
days he does not need to repeat
his clothing.
2015/7/21
Permutations and Combinations
6
P2
Solution
• The maximum number of days he
does not need to repeat his clothing
is 2×3×2 = 12
2015/7/21
Permutations and Combinations
7
P2
Class Practice 1.1
(1)
If there are 3 routes from town
A to town B and 4 routes from
town B to town C,
how many different routes can
be taken in getting from A to C
via B?
2015/7/21
Permutations and Combinations
8
P2
(2)
The chief surgeon for an upcoming
transplant operation is preparing to
select the supporting surgical team.
Needed will be one resident surgeon,
one anesthesiologist, one surgical
nurse, one assisting nurse, and one
orderly.
2015/7/21
Permutations and Combinations
9
P2
• Given the date of the surgery, the
chief surgeon can select from 5
resident surgeons, 3
anesthesiologists, 6 surgical nurses,
10 assisting nurses and 4 orderlies.
• How many possible supporting
surgical teams can be selected?
2015/7/21
Permutations and Combinations
10
(3)
A cancer research project classifies persons in
four categories :
male or female;
heavy smoker, moderate smoker, or nonsmoker;
regular exercise program or no regular program;
overweight or not overweight.
Enumerate all possible classifications of persons.
2015/7/21
Permutations and Combinations
11
P3
1.2 Factorials
• The product of the first n
consecutive integers is denoted by n!
and is read as “factorial n”.
• That is n! = 1×2×3×4×…. ×(n-1) ×n
• For example,
•
4!=1x2x3x4=24,
•
7!=1×2×3×4×5×6×7=5040.
• Note 0! defined to be 1.
2015/7/21
Permutations and Combinations
12
P3
•The product of any number of consecutive
integers can be expressed as a quotient of two
factorials, for example,
• 6×7×8×9 = 9!/5! = 9! / (9 – 4)!
• 11×12×13×14×15= 15! / 10!
=15! / (15 – 5)!
In particular,
• n×(n – 1)×(n – 2)×...×(n – r + 1)
= n! / (n – r)!
2015/7/21
Permutations and Combinations
13
P3
Class Practice 1.2
1. Evaluate
(a) 5!
8!
(b) 7!
2. Express in factorial notation
(a) 1×2×3×4,
(b) 8×9×l0×11.
2015/7/21
Permutations and Combinations
14
P3
1.3 Permutations
• (A)
Permutations
• A permutation is an arrangement of
objects.
• abc and bca are two different
permutations.
• 1. Permutations with repetition
2015/7/21
Permutations and Combinations
15
P4
– The number of permutations of r
objects, taken from n unlike objects,
– can be found by considering the
number of ways of filling r blank
spaces in order with the n given
objects.
– If repetition is allowed, each blank
space can be filled by the objects in n
different ways.
2015/7/21
Permutations and Combinations
16
P4
1
2
3
4
r
n
n
n
n
n
• Therefore, the number of
permutations of r objects, taken
from n unlike objects,
• each of which may be repeated
any number of times
= n × n × n ×.... × n(r factors) =
2015/7/21
Permutations and Combinations
r
n
17
P4
2.
Permutations without repetition
• If repetition is not allowed, the
number of ways of filling each
blank space is one less than
the preceding one.
1
2
3
4
r
n
n-1
n-2
n-3
n-r+1
2015/7/21
Permutations and Combinations
18
P4
Therefore, the number of
permutations of r objects, taken
from n unlike objects, each of
which can only be used once in
each permutation
=n(n— 1)(n—2) .... (n—r + 1)
Various notations are used to represent
the number of permutations of a set of
n elements taken r at a time;
2015/7/21
Permutations and Combinations
19
P4
• some of them are
Since
n
r n r
P , P , P(n, r )
n!
(n  r )!
n(n  1)(n  2)....(n  r  1)(n  r )...3  2  1

(n  r )...3  2  1
 n(n  1)(n  2)....(n  r  1)
Prn ,n Pr , P(n, r )
We have
 Prn
n!
P 
(n  r )!
n
r
2015/7/21
Permutations and Combinations
20
P4
Example 3
• How many 4-digit numbers can be made
from the figures 1, 2, 3, 4, 5, 6, 7 when
• (a)repetitions are allowed;
• (b) repetition is not allowed?
• Solution
• (a)Number of 4-digit numbers
= 74 = 2401.
• (b)Number of 4 digit numbers
=7 ×6 ×5 ×4 = 840.
2015/7/21
Permutations and Combinations
21
P5
Example 4
• In how many ways can 10 men be
arranged
• (a) in a row,
• (b) in a circle?
• Solution
• (a)Number of ways is
10 = 3628800
P
10
2015/7/21
Permutations and Combinations
22
P5
• Suppose we arrange
the 4 letters A, B, C
and D in a circular
arrangement as
shown.
• Note that the
arrangements ABCD,
BCDA, CDAB and
DABC are not
distinguishable.
2015/7/21
A
D
Permutations and Combinations
B
C
23
P5
• For each circular arrangement
there are 4 distinguishable
arrangements on a line.
• If there are P circular
arrangements, these yield 4P
arrangements on a line, which
we know is 4!.
4!
P   (4  1)!  3!
Hence
4
2015/7/21
Permutations and Combinations
24
P5
Solution (b)
• The number of distinct circular
arrangements of n objects is (n —1)!
• Hence 10 men can be arranged in a
circle in 9! = 362 880 ways.
2015/7/21
Permutations and Combinations
25
P5
Class Practice 1.3
1. In how many ways can 10
people be seated in 10 chairs
2. In how many ways can 20
people be seated in 30 chairs
2015/7/21
Permutations and Combinations
26
P6
3. How many 3-digit numbers can
be made from the figures 1, 2, 3,
4, 5,6, 7, 8, 9 when
(a) repetitions are allowed,
(b) repetition is not allowed?
2015/7/21
Permutations and Combinations
27
P6
(B) Conditional Permutations
• When arranging elements in
order , certain restrictions
may apply.
• In such cases the restriction
should be dealt with first..
2015/7/21
Permutations and Combinations
28
P6
Example 5
How many even numerals
between 200 and 400 can be
formed by using 1, 2, 3, 4, 5 as
digits
(a) if any digit may be repeated;
(b) if no digit may be repeated?
2015/7/21
Permutations and Combinations
29
P6
• Solution (a)
• Number of ways of choosing the
hundreds’ digit = 2.
• Number of ways of choosing the tens’
digit = 5.
• Number of ways of choosing the unit
digit = 2.
• Number of even numerals between
200 and 400 is
2 × 5 × 2 = 20.
2015/7/21
Permutations and Combinations
30
P6
•Solution (b)
•If the hundreds’ digit is 2,
then the number of ways of choosing
an even unit digit = 1,
and the number of ways of choosing a
tens’ digit = 3.
•the number of numerals formed
1×1×3 = 3.
2015/7/21
Permutations and Combinations
31
P6
If the hundreds’ digit is 3, then the
number of ways of choosing an even.
unit digit = 2, and the number of ways
of choosing a tens’ digit = 3.
• number of numerals formed
= 1×2×3 = 6.
• the number of even numerals
between 200 and 400 = 3 + 6 = 9
2015/7/21
Permutations and Combinations
32
P6
Example 6
In how many ways can 7 different
books be arranged on a shelf
(a) if two particular books are
together;
2015/7/21
Permutations and Combinations
33
P6
• Solution (a)
• If two particular books are together,
they can be considered as one book for
arranging.
• The number of arrangement of 6 books
= 6! = 720.
• The two particular books can be
arranged in 2 ways among themselves.
• The number of arrangement of 7 books
with two particular books together
= 6! x 2 = 1440.
2015/7/21
Permutations and Combinations
34
P6
(b) if two particular books are
separated?
• Solution (b)
• Total number of arrangement of
7 books = 7! = 5040.
• the number of arrangement of 7
books with 2 particular books
separated = 5040 －1440 = 3600.
2015/7/21
Permutations and Combinations
35
P7
(C)
Permutation with
Indistinguishable Elements
• In some sets of elements there may
be certain members that are
indistinguishable from each other.
• The example below illustrates how to
find the number of permutations in
this kind of situation.
2015/7/21
Permutations and Combinations
36
P7
Example 7
In how many ways can the letters of the
word “ISOS CELES” be arranged to
form a new “word” ?
• Solution
• If each of the 9 letters of
“ISOSCELES” were different, there
would be P= 9! different possible
words.
2015/7/21
Permutations and Combinations
37
P7
• However, the 3 S’s are
indistinguishable from each other
and can be permuted in 3!
different ways.
• As a result, each of the 9!
arrangements of the letters of
“ISOSCELES” that would
otherwise spell a new word will be
repeated 3! times.
2015/7/21
Permutations and Combinations
38
P7
• To avoid counting repetitions
resulting from the 3 S’s, we must
divide 9! by 3!.
• Similarly, we must divide by 2! to
avoid counting repetitions resulting
from the 2 indistinguishable E’s.
• Hence the total number of words
that can be formed is
9! ÷3! ÷2! = 30240
2015/7/21
Permutations and Combinations
39
P7
• If a set of n elements has k1
indistinguishable elements of one
kind, k2 of another kind,
and so on for r kinds of elements,
then the number of permutations of
the set of n elements is
2015/7/21
n!
k1!k 2 !    kr !
Permutations and Combinations
40
P7
Example 8
• The streets of a town form a
rectangular grid, 5 blocks long and
4 blocks wide, as shown in the
diagram.
A man walks along the street from
P to Q always walking either due
East or due North.
• (a) Find the total number of
possible paths.
2015/7/21
Permutations and Combinations
41
P8
Q
North
R
P
East
• (b) Find the number of these
paths which pass through the
point R.
2015/7/21
Permutations and Combinations
42
P8
• Solution (a)
• Each path from P to Q involves a walk
of 5 blocks due East and 4 blocks due
North.
• Hence each path corresponds to an
arrangement of the nine letters
EEEEENNNN, taken together.
• The number of paths is equal to the
number of permutations of the nine
letters,
= 9! ÷5! ÷ 4! = 126 paths
2015/7/21
Permutations and Combinations
43
P8
• Similarly, the number of paths from P
to R
= 5! ÷4! ÷ 1! = 5
• and the number of paths from R to Q
= 4! ÷1! ÷ 3! = 4
• The total number of paths from P to Q
via R
= 5 × 4 = 20
2015/7/21
Permutations and Combinations
44
P8
Class Practice 1.4
(1) Five boys and two girls are to
be seated in a row. In how many
ways can this be done if
(a) a girl must sit at either end of
the row,
(b) the two girls must not sit next to
each other.
2015/7/21
Permutations and Combinations
45
P8
• (2)
• How many different
numbers can be indicated
by rearranging the 9
digits of 988877666?
2015/7/21
Permutations and Combinations
46
P8
• (3)
• In how many ways can 3 different
Mathematics, 2 different Physics
and 4 different Chemistry books
be arranged on a shelf if
(a) the Mathematics books are next to
each other,
(b) the books are kept in subject
groupings?
2015/7/21
Permutations and Combinations
47
P8
• (4)
• In how many ways can the
letters of the word
“AGREEMENT” be
arranged to from a new
“word”?
2015/7/21
Permutations and Combinations
48
P8
Exercise 1(a)
p9
1.(a)A woman has 5 skirts and 6 blouses.
Assuming that each blouse can be
worn with each skirt, how many
different skirt-blouse outfits does the
woman have?
(b) A full dinner at a restaurant
consists of one of 5 appetizers, one of
6 main courses, and one of 8 deserts.
How many different complete dinners
are there?
2015/7/21
Permutations and Combinations
49
P9
Exercise 1(a)
p9
• (2)
• In how many ways can 4
people be accommodated in
5 rooms if they
(a) are put in separate
rooms,
(b) don’t mind sharing?
2015/7/21
Permutations and Combinations
50
P9
Exercise 1(a)
p9
• (3)
• In how many ways can 4 different
prizes be awarded in a class of 15
boys if
(a) no boy may win more than 1
prize,
(b) any boy may win all the prizes?
2015/7/21
Permutations and Combinations
51
P9
Exercise 1(a)
• (4)
p9
• A man has time to visit one friend on
each evening of a given week.
• There are 12 friends whom he like to
visit.
• In how many ways can he plan his week
if
(a) he can visit a friend more than once,
(b) he will not visit a friend more than
once?
2015/7/21
Permutations and Combinations
52
P9
Exercise 1(a)
• (5)
p9
• Using all the digits 1,2,3,4,5,6
how many arrangements can
be made
(a) beginning with an even
digit,
(b) beginning and ending with
an even digit?
2015/7/21
Permutations and Combinations
53
P9
Exercise 1(a)
p9
• (6)
• If women must go first, in
how many ways can 5
women and 7 men enter a
lifeboat?
2015/7/21
Permutations and Combinations
54
P9
Exercise 1(a)
p9
• (7)
• Five boys and two girls sit in a
row. In how many ways is this
possible if the girls
• (a) must not sit together,
(b) must sit at the ends?
2015/7/21
Permutations and Combinations
55
P9
Exercise 1(a)
p9
• (8)
• Four visitors A, B, C and D arrive in a
town which has 6 hotels.
• In how many ways can they disperse
themselves among the 6 hotels
• (a) if four hotels are used to
accommodate them,
(b) if three hotels are used to
accommodate them in such a way
that A and B stay at the same hotel?
2015/7/21
Permutations and Combinations
56
P9
Exercise 1(a)
p10
• (9)
• How many numbers
between 4000 and 7000 can
be formed by using 3, 4, 5, 6
as digits, so that any digit
may be repeated ?
2015/7/21
Permutations and Combinations
57
P10
Exercise 1(a)
p10
• (10)
• In how many ways can 4
Mathematics books and 6 Physics
books be arranged on a shelf
• (a) with no restrictions,
(b) if all the Mathematics books are
to the left of the Physics books.
2015/7/21
Permutations and Combinations
58
P10
Exercise 1(a)
p10
• (11)
• In how many ways can 5
people be seated for a
photograph
if there are 2 seats in the
front row and 3 seats in the
back row?
2015/7/21
Permutations and Combinations
59
P10
Exercise 1(a)
p10
• (12)
• In how many ways can a
president, vice-president,
secretary, and treasurer be
selected from a class of 30
students, if no person may hold
two offices?
2015/7/21
Permutations and Combinations
60
P10
Exercise 1(a)
• (13)
p10
• If the first 2 symbols in a license tag
are letters of the alphabet and the
next 4 symbols are digits of our
numeral system, how many different
tags can be made
• (a) if no symbol may be repeated,
• (b) if any symbol may be repeated?
2015/7/21
Permutations and Combinations
61
P10
Exercise 1(a)
p10
• (14)
• A particular new car model is
available with 5 choices of
colour, 3 choices of
transmission, 4 types of
interior and 3 types of engine.
How many different cars of
this model are possible ?
2015/7/21
Permutations and Combinations
62
P10
Exercise 1(a)
p10
• (15)
• Employee ID numbers at a certain
factory consist of one capital letter
followed by a 3-digit number
containing no repeat digits.
(For example, A025 is an ID number.)
How many such ID numbers can be
formed ?
How many could be formed if repeat
digits were allowed?
2015/7/21
Permutations and Combinations
63
P10
Exercise 1(a)
p10
• (16)
• In the figure shown,
the vertices represent
cities and the edge
routes between cities.
In how many
different ways can a
man starting at A
visit each other city
once and return to A?
A
D
E
B
2015/7/21
Permutations and Combinations
C
64
P10
Exercise 1(a)
p11
• (17)
• There are 5 boys and 5 girls at a
dance.
In how many different ways
can they pair off for dancing,
if everyone is dancing with a
member of the opposite sex?
2015/7/21
Permutations and Combinations
65
P11
Exercise 1(a)
p11
• (18)
• How many different numbers
can be indicated by
rearranging
• (a) the 8 digits of 122 33344?
• (b) the 11 digits of
99988887765?
2015/7/21
Permutations and Combinations
66
P11
Exercise 1(a)
p11
• (19)
• A signaler has six flags, of which one
is blue, two are white and three are
red. He sends messages by hoisting
flags on a flagpole, the message being
conveyed by the order in which the
colours are arranged. Find how many
different message he can send
• (a)
by using exactly six flags,
• (b)
by using exactly five flags.
2015/7/21
Permutations and Combinations
67
P11
1.4 Combinations
• When a selection of objects is made
with no regard being paid to order,
it is referred to as a combination.
• Thus, ABC, ACB, BAG, BCA, CAB,
CBA are different permutation, but
they are the same combination of
letters.
2015/7/21
Permutations and Combinations
68
P12
• Suppose we wish to appoint a
committee of 3 from a class of 30
students.
• We know that P330 is the number of
different ordered sets of 3 students
each that may be selected from
among 30 students.
• However, the ordering of the
students on the committee has no
significance,
2015/7/21
Permutations and Combinations
69
P12
• so our problem is to determine the
number of three-element unordered
subsets that can be constructed from
a set of 30 elements.
• Any three-element set may be
ordered in 3! different ways, so P330
is 3! times too large.
• Hence, if we divide P330 by 3!,the
result will be the number of
unordered subsets of 30 elements
taken 3 at a time.
2015/7/21
Permutations and Combinations
70
P12
• This number of unordered
subsets is also called the number
of combinations of 30 elements
taken 3 at a time, denoted by C330
and
1
C
2015/7/21
30
3

3!
30
3
P
30!

 4060
27!3!
Permutations and Combinations
71
P12
• In general, each unordered r-element
subset of a given n-element set (r n) is
called a combination.
• The number of combinations of n
elements taken r at a time is denoted by
Cnr or nCr or C(n, r) .
• A general equation relating
combinations to permutations is
1 n
n!
C  Pr 
r!
(n  r )!r!
n
r
2015/7/21
Permutations and Combinations
72
P12
• Note:
•
•
•
(1) Cnn = Cn0 = 1
(2) Cn1 = n
(3) Cnn = Cnn-r
• Class Practice 1.5
• 1. Evaluate
•
(a) C52 (b) C55 (c) C51
• 2. Evaluate
•
(a) C85 (b) C74+C75
• 3. Prove that Cnr = Cnn-r
2015/7/21
Permutations and Combinations
73
P12
Example 9
How many different 5-card hands can be
dealt from a deck of 52 playing cards?
• Solution
• Since we are not concerned with the
order in which each card is dealt,
our problem concerns the number of
combinations of 52 elements taken 5
at a time.
• The number of different hands is
C525＝ 2118760.
2015/7/21
Permutations and Combinations
74
P13
Example 10
6 points are given and no three of them are
collinear.
(a) How many triangles can be formed by
using 3 of the given points as vertices?
• Solution
• (a)Number of triangles
•
= number of ways
•
of selecting 3 points out of 6
•
= C63 = 20.
2015/7/21
Permutations and Combinations
75
P13
(b) How many pairs of triangles can be
formed by using the 6 points as vertices?
• Solution:
• Let the points be A, B, C, D, E, F.
• If A, B, C are selected to form a
triangles, then D, E, F must form
the other triangle.
• Similarly, if D, E, F are selected to
form a triangle, then A, B, C must
form the other triangle.
2015/7/21
Permutations and Combinations
76
P13
• Therefore, the selections A, B, C
and D, E, F give the same pair of
triangles and the same applies to
the other selections.
• Thus the number of ways of
forming a pair of triangles
= C63 ÷ 2 = 10
2015/7/21
Permutations and Combinations
77
Example 11
From among 25 boys who play basketball, in
how many different ways can a team of 5
players be selected if one of the players is to be
designated as captain?
• Solution
• A captain may be chosen from any of the 25
players.
• The remaining 4 players can be chosen in C254
different ways.
• By the fundamental counting principle, the total
number of different teams that can be formed is
25 × C244＝265650.
2015/7/21
Permutations and Combinations
78
P14
• Alternative Method
• Without designating a captain the
number of ways would be C255 .
• However, 5 different captains may be
chosen in each different set of
players.
• The total number of different teams
is
5 × C255 =265650
2015/7/21
Permutations and Combinations
79
P14
• 1.
•
•
• 2.
•
•
•
• 3.
•
•
Class Practice 1.6
Write down all 2-element
subsets that can be constructed
from the set { a,b,c,d,e}.
A secondary school principal
plans to appoint a committee of 4
from the 48 teachers. How many
different committees are possible?
How many different 13-card hands
can be dealt from a deck of 52
playing cards?
2015/7/21
Permutations and Combinations
80
P15
(B) Conditional Combinations
• If a selection is to be restricted in
some way, this restriction must be
dealt with first.
• The following examples illustrate
such conditional combination
problems.
2015/7/21
Permutations and Combinations
81
P15
Example 13
A committee of 3 men and 4 women
is to be selected from 6 men and 9
women.
If there is a married couple among
the 15 persons, in how many ways
can the committee be selected so
that it contains the married couple?
2015/7/21
Permutations and Combinations
82
P15
• Solution
• If the committee contains the married
couple, then only 2 men and 3 women
are to be selected from the remaining 5
men and 8 women.
• The number of ways of selecting 2 men
out of 5 = C52 = 10.
• The number of ways of selecting 3
women out of 8 =C83 = 56.
• the number of ways of selecting the
committee = lO × 56 = 560.
2015/7/21
Permutations and Combinations
83
P15
Example 14
Find the number of ways a team of 4 can
be chosen from 15 boys and 10 girls if
(a) it must contain 2 boys and 2 girls,
• Solution (a)
• Boys can be chosen in C152 = 105 ways
• Girls can be chosen in C102 = 45 ways.
• Total number of ways is 105 × 45 =
4725.
2015/7/21
Permutations and Combinations
84
P15
(b)
it must contain at least 1 boy and 1 girl.
• Solution :
• If the team must contain at least 1 boy and 1
girl it can be formed in the following ways:
• (I) 1 boy and 3 girls, with C151 × C103 = 1800
ways,
• (ii) 2 boys and 2 girls, with 4725 ways,
• (iii) 3 boys and 1 girl, with C153 × C101 = 4550
ways.
• the total number of teams is
1800 + 4725 + 4550 = 11075.
2015/7/21
Permutations and Combinations
85
P16
Example 15
A woman has 12 friends and wishes to invite 6
of them to a party. Find the number
of ways she may do this if
(a) there is no restriction on choice,
• Solution (a)
• An unrestricted choice of 6 out
of 12 gives C126＝ 924.
2015/7/21
Permutations and Combinations
86
P16
(b) two of the friends is a couple and will
not attend separately,
• Solution(b)
• If the couple attend, the remaining 4 may
then be chosen from the other 10 in C104
ways.
• If the couple does not attend, the woman
simply chooses 6 from the other 10 in C106
ways.
• total number of ways is C104 + C106 = 420.
2015/7/21
Permutations and Combinations
87
P16
(c) two of the friends are not speaking
and
will not attend together
• Solution
• Let the non-speaking friends be A, B.
• If one of A, B attends, the party can be
formed in C21 × C105 ways.
• If neither A nor B attends, the party
can be formed in C106 ways.
• Total number of ways is
•
C21 × C105 + C106 = 714.
2015/7/21
Permutations and Combinations
88
P16
Example 16
Find the number of ways in
which 30 students can be
divided into three groups, each
of 10 students, if the order of
the groups and the
arrangement of the students in
a group are immaterial.
2015/7/21
Permutations and Combinations
89
P16
• Solution
• Let the groups be denoted by A, B
and C. Since the arrangement of the
students in a group is immaterial,
• group A can be selected from the 30
students in C3010 ways .
• Group B can be selected from the
remaining 20 students in C2010 ways.
• There is only 1 way of forming group
C from the remaining 10 students.
2015/7/21
Permutations and Combinations
90
P16
• Since the order of the groups is
immaterial, we have to divide the
product C3010 × C2010 × C1010 by 3!,
• hence the total number of ways of
forming the three groups is
1
30
20
10
 C3  C10  C10
3!
2015/7/21
Permutations and Combinations
91
P17
Example 17
What is the greatest possible
number of points of intersection of
6 lines and 5 circles?
2015/7/21
Permutations and Combinations
92
P17
•(i) Consider the 6 lines, the greatest possible
•
number of points of intersection is C62 = 15.
•(ii) Consider the 5 circles, the greatest possible
• number of points of intersection is 2× C52 = 20.
•(iii) Each line can intersect a circle at 0, 1 or 2
points. Hence the greatest possible number of
points of intersection resulting from the
intersection of a line and a circle is
2 × 6 × 5 = 60.
• Combining (i)(ii)(iii), the greatest possible
number of points of intersection is 15+20+60
= 95.
2015/7/21
Permutations and Combinations
93
P17
Class Practice 1.7
P17
• (1)
• In how many ways can a team of
three boys and three girls be
chosen from six boys and seven
girls ?
2015/7/21
Permutations and Combinations
94
P17
Class Practice 1.7
P17
• (2)
• In how many ways can a selection of
4 letters be taken from the letters in
the word “COMPUTE” if
• (a) the letter P is not to be chosen,
• (b) the letter P and E cannot be
chosen in the same selection ?
2015/7/21
Permutations and Combinations
95
P17
Class Practice 1.7
P17
• (3)
• A committee of 5 is to be chosen
from a group of 10 people.
• In how many ways can the
committee be formed, if two
particular people agree to serve
only if they are both chosen?
2015/7/21
Permutations and Combinations
96
P17
Class Practice 1.7
P18
• (4)
• A sorority house has 3 bedrooms
and 10 students.
• One bedroom has 5 beds, the
second has 3 beds, and the third has
2 beds.
• In how many different ways can the
students be assigned rooms?
2015/7/21
Permutations and Combinations
97
P18
Class Practice 1.7
P18
• (5)
• In how many ways can 12 students
be divided into three groups of 4,
• if the order of the groups and the
arrangement of the students in a
group are immaterial ?
2015/7/21
Permutations and Combinations
98
P18
Class Practice 1.7
P18
• (6)
• Eight policemen are to be posted to
guard three separate buildings.
• In how many ways may they all be
posted
if no building is to be guarded by
less than two policemen?
2015/7/21
Permutations and Combinations
99
P18
Class Practice 1.7
P18
•(7) Code numbers, each containing three digits,
•
are to be formed from the nine digits 1, 2,
•
3,…,9. In any number no particular digit
•
may occur more than once.
•(a) How many different code numbers may be
•
formed, and in how many of these will 9 be
•
one of the three digits selected?
(b) In how many numbers will the three digits
occur in their natural order (i.e. the digits being in
ascending order of magnitude reading from left to
right, e.g. 238) ?
2015/7/21
Permutations and Combinations
100
P18
Ex 1b
P19
• 1.(a) A firm has 12 computer
programmers. Three of these people are
to be promoted to system analysts.
In how many ways can the 3 people to
be promoted be selected?
• (b) A new product team will contain three
of eight engineers, two of five marketing
specialists, and one of three financial
experts.
How many different teams are possible?
2015/7/21
Permutations and Combinations
101
P19
Ex 1b
P19
• (2)
• Of the first 10 questions on a test, a
student must answer 7.
• On the second 5 questions, he must
answer 3.
• In how many ways can this be done?
2015/7/21
Permutations and Combinations
102
P19
Ex 1b
P19
• (3)
• Find the number of points of
intersection of 15 straight
lines ,
no two of which are parallel
and no three of which are
concurrent.
2015/7/21
Permutations and Combinations
103
P19
Ex 1b
P19
• (4)
• How many line segments are
determined by the 5 vertices
of a pentagon ?
• Of these, how many are
diagonals ?
2015/7/21
Permutations and Combinations
104
P19
Ex 1b
P19
• (5)
• There are 8 points on a
circle.
• How many triangles can be
inscribed with these points
as vertices?
2015/7/21
Permutations and Combinations
105
P19
Ex 1b
P19
• (6)
• Given 10 points in a plane, no 3
of which are collinear and no 4 of
which are concyclic,
• find the number of circles which
may be drawn to pass through 3
of the given points.
2015/7/21
Permutations and Combinations
106
P19
Ex 1b
P19
• 7.(a) Find the number of different
permutations of the letters of the word
“PROBABILITY”
• (b) Find the number of different selections of
5 letters which can be made from the
letters of the word “PROBABILITY”.
• (c) Find the number of ways in which
•
(i) a selection,
•
(ii) an arrangement can be made of 4
letters taken from the letters of the
word “ARRANGE”.
2015/7/21
Permutations and Combinations
107
P19
Ex 1b
P19
• (8)
• A football team consisting of a
goalkeeper and 10 other players is
to be selected from 18 players.
• Just 2 of the 18 players are
goalkeepers.
• Find the number of ways in which
the team may be selected.
2015/7/21
Permutations and Combinations
108
P19
Ex 1b
P19
• (9)
• (a) In how many ways can 9 men
be divided into three groups
of 2, 3 and 4 respectively?
• (b) In how many ways can 9 men
be divided into three groups of
three if no regard is paid to the
order of the group?
2015/7/21
Permutations and Combinations
109
P19
Ex 1b
P20
• (10)
• A committee of 4 is selected from
a group of 8 boys and 6 girls.
• If the committee must have at
least one girl, in how many ways
can the committee be selected ?
2015/7/21
Permutations and Combinations
110
P20
Ex 1b
• (11)
P20
• Of 20 computer chips, 4 will be selected for
testing. How many different samples could be
selected ?
• Suppose 5 of the 20 chips are defective and
15 of the chip are good.
• (a) How many of the samples contain only
good chips?
• (b) How many of the samples contain 2 good
chips and 2 defective chips?
• (c) How many of the samples contain one or
more defective chips?
2015/7/21
Permutations and Combinations
111
P20
Ex 1b
P20
• (12)
• Two lines are parallel. On the
first line there are 5 dots, and on
the second there are 4.
• How many possible triangles can
be formed by joining 3 of these
dots?
2015/7/21
Permutations and Combinations
112
P20
Ex 1b
P20
• (13)
• (a) In how many ways can 10
basketball players be divided into
two teams of 5 players each?
• (b) In how many ways can 10
basketball players be divided into
two teams of 5 players so that the
2 best players are on opposite
teams?
2015/7/21
Permutations and Combinations
113
P20
Ex 1b
P20
• (14)
• From 8 persons, including Mr. and
Mrs. Chan, a committee of four is to
be chosen.
• Mrs. Chan will not join the committee
without her husband, but Mr. Chan
will join the committee without his
wife.
• In how many ways can the committee
be formed?
2015/7/21
Permutations and Combinations
114
P20
Ex 1b
P20
• (15)
• A party of nine person is to
travel in two cars, one of which
will hold not more than seven
persons, and the other not more
than four.
• In how many ways can the party
travel ?
2015/7/21
Permutations and Combinations
115
P20
Ex 1b
P20
• (16)
• In how many ways can three
different numbers be selected
from the thirty numbers 1, 2,….,
30 such that their sum is
• (a) divisible by 2,
• (b) divisible by 3 ?
2015/7/21
Permutations and Combinations
116
P20
Ex 1b
• (17)
P20
• Two straight lines intersect at 0. If A1,
A2, ...., An , are taken on one line, and B1,
B2, ...., Bn on the other.
• Prove that the number of triangles that
can be drawn with three of the points for
vertices is
• (a) n2 (n — 1) if the point 0 cannot be
used,
(b) n3 if 0 may be used.
2015/7/21
Permutations and Combinations
117
P20
Ex 1b
P21
• (18)
• A committee of 3 is to be chosen from
4 married couples.
• Find how many ways can the
committee be chosen if
• (a) the committee must consist of one
•
woman and two men,
• (b) all are eligible except that a
•
husband and wife cannot both
•
serve on the committee.
2015/7/21
Permutations and Combinations
118
P21
Ex 1b
P21
• (19)
• A table-tennis club is to select a team
of three pairs, each pair consisting of
a man and a woman, for a match in
mixed double.
• The team is to be chosen from 7 men
and 5 women.
• In how many different ways can the
three pairs be chosen ?
2015/7/21
Permutations and Combinations
119
P21
Ex 1b
P21
• (20)
• There are 10 articles, 2 of which
are alike and the rest all different.
• In how many ways can a selection
of 5 articles be made ?
2015/7/21
Permutations and Combinations
120
P21