09_Combinatorics
pdf
keyboard_arrow_up
School
Westmoor High *
*We aren’t endorsed by this school
Course
220
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
8
Uploaded by Keysor
Chapter 3
Counting
A more formal title for this chapter would be
combinatorics
. Many prob-
lems involving probability and statistics require knowing how many ele-
ments are in a particular set. Consider poker hands. What is the probability
that a hand of five cards has two aces? To answer this, we would divide the
number of five-card hands having two aces by the total number of five-card
hands. We could list all possible five-card hands and then count the number
of these hands that have two aces. Doing this would give us real insight into
the problem, so listing is a very good way to solve counting problems. Many
times after you start listing elements, you’ll find ways to count the elements
without listing all of them. If we could count the number of five-card hands
having two aces without listing
all
of them, that would be more efficient.
In this chapter, to solve a problem will mean to convince the class that you
have counted all the items correctly.
Perhaps you’ll list all the items, or
perhaps you’ll list a smaller example to demonstrate the counting technique
you used.
Problem 48.
The standard license plate for a non-commercial vehicle titled
in the State of Maryland consists of six characters. The first character must
be one of the nine digits 1, 2, ..., 9. Each of the next three characters must
be a letter of the alphabet other than i, o, q, or u.
Each of the last two
characters must be one of the ten digits 0, 1, 2, ..., 9. How many standard
license plates for non-commercial vehicles can be issued by the State of
Maryland?
Problem 49.
There are six area codes used for Maryland telephone num-
bers: 227, 240, 301, 410, 443, 667. Following each area code are a three-
digit “prefix” and a four-digit “exchange.” The prefix may not be the num-
ber 555, or begin with the number 0. How many telephone numbers can be
issued for the State of Maryland?
Problem 50.
Andrew, Bob, Carly, and Diane are the only entrants in a
prize giveaway.
Both prizes are the same model of PlayStation.
In how
many ways can two winners be chosen from them?
7
12
Counting
13
Problem 51.
Andrew, Bob, Carly, and Diane are the only entrants in a prize
giveaway. The first prize is an Audi TT, and the second is a Ford Focus. No
one person is allowed to win both prizes. In how many ways can the prizes
be awarded?
Problem 52.
Andrew, Bob, Carly, and Diane are the only entrants in a prize
giveaway. The first prize is an Audi TT, and the second is a Ford Focus. It
is allowable for the same person to win both prizes. In how many ways can
the prizes be awarded?
Definition 16.
A set M is
finite
if there is a nonnegative integer n so that M
has n elements and does not have n
+
1
elements. If the set M has n elements
but does not have n
+
1
elements, then we write
|
M
|
=
n and say that M is
an n
-element set
. A set is
infinite
if it is not finite.
The next two theorems simply give names to the tools you probably used
to solve the last few problems.
Theorem 1.
Multiplication Principle.
If each of m and n is a positive in-
teger, A is an m-element set, and B is an n-element set, then
|
A
×
B
|
=
mn
or restated,
|
A
×
B
|
=
|
A
||
B
|
.
This is sometimes called the Fundamental
Principle of Counting.
Theorem 2.
Generalized Multiplication Principle.
Suppose that n is a pos-
itive integer and each of A
1
,
A
2
,...,
A
n
is a finite set. Then
|
A
1
×
A
2
×
A
3
×
··· ×
A
n
|
=
|
A
1
||
A
2
|···|
A
n
|
.
This is sometimes called the Generalized or
Fundamental Principle of Counting.
Example 7.
Suppose a mathematician has four different pairs of pants,
three different shirts, and five different hats.
How many outfits can s/he
make assuming an outfit consists of exactly one pair of pants, exactly one
shirt and exactly one hat?
8
Problem 53.
There are thirteen cards of each of the four suits in a fifty-two
card deck. How many possible four-card hands are there containing a card
from each of the four suits?
Problem 54.
Sherwoodn’t Cars sells five models of car in three colors. How
many different cars could you see in Sherwoodn’t’s lot, ignoring accessories
and options?
Problem 55.
A program to produce greeting cards has 100 pictures to
choose from and twenty-five sayings.
How many different cards can the
program produce?
9
Problem 56.
Suppose there are four 400-level mathematics courses: MATH
406, 402, 465, and 482, offered in a particular semester, and you want to
take two of them. How many options do you have?
David M. Clark
W. Ted Mahavier
www.jiblm.org
Counting
14
Problem 57.
Consider the algorithm below.
Let i = 1
While i < 7 do
Let j=2
While j < 6 do
Print ’’Here is an ordered pair’’, (i,j)
j = j + 1
End j While Loop
i = i + 1
End i While Loop
How many ordered pairs would this program print?
Problem 58.
Suppose that a web site has you choose a username and a
password. The username must consist of ten alphanumeric characters. The
password must consist of seven alphanumeric characters, the last of which
must be numeric and the first of which must be alphabetical.
1. How many usernames are possible if they are not case-sensitive?
2. How many passwords are possible if they are not case-sensitive?
3. How many usernames are possible if they are case-sensitive?
4. How many passwords are possible if they are case-sensitive?
In counting the number of ways we can select several objects from a
particular finite set, two questions arise: Does order matter? Is repetition
(replacement) allowed?
Definition 17.
Let A be a set. By an
unordered sample
of size n chosen
from A we mean an n-element subset of A. By an
ordered sample
of size n
chosen from A we mean an n-element sequence of
(
not necessarily distinct
)
elements of A. In this context, the set A is called the
population
from which
the samples are drawn.
For example,
{
1
,
2
,
3
}
and
{
2
,
3
,
1
}
are the same unordered sample of size
3 from the population of positive integers since order doesn’t matter in the
specification of a subset. In contrast,
(
1
,
1
,
3
)
and
(
1
,
3
,
1
)
are different or-
dered samples of size 3 from the same population.
Using this language, we can restate Problem
50
as “How many unordered
samples of size two can be chosen without replacement (or “without repe-
tition”) from the four-element “population” (Andrew, Bob, Carly, Diane)?”
In Problem
51
, we sought an ordered sample of size two without replace-
ment (repetition) from the same population. Finally, in Problem
52
we de-
sired an ordered sample of size two “with replacement” (or “with repeti-
tion”).
David M. Clark
W. Ted Mahavier
www.jiblm.org
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Counting
15
Example 8.
Suppose you are working on a ten-digit keypad to open a door.
You know the combination is exactly three digits long.
10
1. How many choices are there if you may use a number multiple times
and the order matters?
2. How many choices are there if you may not use a number multiple
times and the order matters?
3. How many choices are there if you may not use a number multiple
times and the order does not matter?
4. How many choices are there if you may use a number multiple times
and the order does not matter?
Ordered Samples with Repetition Allowed (n-tuples)
The expression (3,-5) is an example of an ordered pair; (-1,0,
1
2
) is an or-
dered triple; and (7,
1
4
,
π
,z) is an ordered quadruple. If
n
is a positive integer
and
A
is a set and
a
i
∈
A
for each integer
i
∈ {
1
,...,
n
}
, then (
a
1
,
a
2
, ...,
a
n
)
is an ordered
n
-tuple.
Theorem 3.
If each of n and k is a positive integer and A is an n-element
set, then the number of ordered k-tuples that can be selected from A is n
k
.
Theorem
4
is simply a restatement of Theorem
3
using fancy words!
Theorem 4.
If each of n and k is a positive integer and P is an n-element
set (population), then the number of ordered samples of size k that can be
drawn with replacement (repetition) from P is n
k
.
Ordered Samples without Repetition (permutations)
Theorem 5.
If n and k are positive integers with k
≤
n and P is an n-element
set (population), then the number of ordered samples of size k that can be
drawn without replacement from P, is
(
n
-
0
)(
n
-
1
)(
n
-
2
)
···
(
n
-
(
k
-
1
)) =
n
(
n
-
1
)(
n
-
2
)
···
(
n
-
k
+
1
)
.
Definition 18.
If n is a non-negative integer then
n factorial
is denoted by
n
!
and defined by
n
!
=
1
if
n
=
0
or n
=
1
n
·
(
n
-
1
)
···
2
·
1
if
n
>
1
(
the product of integers
1
to n
)
Problem 59.
Let each of n and k represent positive integers with k
≤
n and
show that n
(
n
-
1
)(
n
-
2
)
···
(
n
-
k
+
1
) =
n
!
/
(
n
-
k
)
!
.
The next theorem is merely a restatement of Theorem
5
when
k
=
n
.
Theorem 6.
If P is an n-element population, then the number of ordered
samples of size n that can be drawn without replacement from P is n
!
.
David M. Clark
W. Ted Mahavier
www.jiblm.org
Counting
16
Definition 19.
If n is a positive integer and S is an n-element set, then a
permutation of S
is a bijection on S.
Example 9.
Let S
=
{
1
,
2
,
3
}
. One permutation of S would be the bijection
f
:
S
→
S defined by f
(
1
) =
2
,
f
(
2
) =
3
,
and f
(
3
) =
1
. Typically, we omit
all the function notation and just write the range of f as
(
2
,
3
,
1
)
. Recall
that the order matters when we use
()
but not when we use
{}
.
Problem 60.
List all the permutations of S
=
{
1
,
2
,
3
}
.
Problem 61.
How many seven-letter strings can be formed using the letters
from the word TUESDAY, where no letter may be used twice? How many
five-letter strings?
Problem 62.
Let D
=
{
a
,
b
,
c
}
and R
=
{
1
,
2
,
3
,
4
,
5
}
. How many functions
are there with domain all of D and with range a subset of R? How many are
one-to-one? How many are onto R?
Problem 63.
Let D
=
{
a
,
b
,
c
,
d
,
e
}
and R
=
{
1
,
2
,
3
}
. How many functions
are there with domain all of D and range a subset of R? How many are
one-to-one? How many are onto R?
Unordered Samples without Repetition (subsets)
Problem 64.
Let D
=
{
a
,
b
,
c
,
d
,
e
}
. How many three element subsets are
there of D?
Theorem 7.
If n is a positive integer and k is a nonnegative integer not
larger than n, then the number of k-element subsets of an n-element set is
n
!
(
n
-
k
)
!
k
!
.
Problem 65.
Compute
n
!
(
n
-
k
)
!
k
!
for each of
1. n
=
10
, k
=
3
,
2. n
=
10
, k
=
7
,
3. n
=
5
, k
=
5
, and
4. n
=
5
, k
=
0
.
Problem 66.
Show that
1. if n
=
20
and k
=
12
and j
=
8
then
n
!
(
n
-
k
)
!
k
!
=
n
!
(
n
-
j
)
!
j
!
and
2. if n is a positive integer and k is a nonnegative integer not larger than
n and j
=
n
-
k then
n
!
(
n
-
k
)
!
k
!
=
n
!
(
n
-
j
)
!
j
!
.
David M. Clark
W. Ted Mahavier
www.jiblm.org
Counting
17
Problem 67.
Dr. Shannon has a total of six nieces and nephews. She has
just won a set of eight
different
CD’s. In how many different ways can she
1. Give each child exactly one CD?
2. Give away all the CD’s so that each child gets at least one without
giving any child more than two?
3. Give away all the CD’s so that each child gets at least one?
Problem 68.
Suppose that each of m and n is a positive integer and each
of A and B is a set such that
|
A
|
=
n and
|
B
|
=
m. How many functions are
there from A to B? How many are one-to-one? How many are onto B?
Problem 69.
Six cards are to be drawn from a standard deck and laid on
a table in the order in which they were drawn. How many outcomes are
possible in this experiment?
Problem 70.
You and thirteen of your closest friends have decided to form
a club.
1. If you decide to elect four officers, a president, a vice president, a
secretary, and a treasurer, then how many possible slates of officers
are there?
2. If you decide that the job of secretary is too much for one person and
elect a president, a vice president, a treasurer, and two secretaries,
then how many slates are there?
Problem 71.
To avoid the diplomatic quagmire of deciding who will sit at
the head of the table and who at the foot, a group planning peace talks with
the single heads of state of four nations decides to seat all four at a round
table, where all spots are equally prestigious and powerful.
1. How many possible seating arrangements are there?
2. How many arrangements are there if you only care who sits next to
whom but not on which side of the person each neighbor sits?
Problem 72.
An elementary-school teacher is directing an after-school pa-
rade with twelve of his students. Three of them will be twirling batons, five
will be playing cymbals, and four will be doing somersaults. They will be
parading in single file.
1. How many different parades are possible if he wants to have the twirlers
followed by the cymbal players, with the tumblers at the rear?
2. How many are possible if he simply keeps together the children who
are doing the same thing?
David M. Clark
W. Ted Mahavier
www.jiblm.org
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Counting
18
3. How many would be possible in a free-for-all, where the kids are in
any order?
4. How many are possible if the twirlers stay together but the others can
be in any order?
Problem 73.
A coin is tossed six times and the results, heads or tails on
each toss, are recorded in order.
1. How many outcomes are possible?
2. How many of these have exactly one head?
3. How many have at least one head?
4. How many have at least one head and at least one tail?
Definition 20.
Suppose that A is a set and f
:
A
→
A is a function. If x
∈
A
satisfies f
(
x
) =
x, then we say that x is a
fixed point of
A
with respect to
f.
Problem 74.
Suppose that A
=
{
a
,
b
,
c
,
d
}
.
1. How many functions are there on A for which a is a fixed point?
2. How many for which a and b are fixed points?
3. How many for which a, b and c are fixed points?
4. How many functions are there that fix every point of A?
Problem 75.
Suppose A
=
{
a
,
b
,
c
,
d
}
. Let F1 be the set of functions f
:
A
→
A for which a is a fixed point. Let F2 be the set of functions f
:
A
→
A for
which a and b are fixed points. Let F3 be the set of functions f
:
A
→
A for
which a, b and c are fixed points. Let F4 be the set of functions for which
all four elements are fixed points. What are
|
F
1
∩
F
2
|
,
|
F
3
∩
F
2
|
,
|
F
3
∩
F
4
|
and
|
F
1
∩
F
2
∩
F
3
|
?
Problem 76.
If six cards are chosen without replacement from a standard
deck, how many hands are possible if
1. the six cards can be anything?
2. at least one card is an ace?
3. at least four are clubs?
4. exactly three of the cards are hearts?
Problem 77.
The five-member math club decided to hold a raffle, with each
member being responsible for selling ten tickets. Each club member bought
one ticket and sold nine to non-members. The stubs were then to be thrown
into a fish bowl and three winning tickets were to be chosen at random.
David M. Clark
W. Ted Mahavier
www.jiblm.org
Counting
19
1. Of the possible outcomes, in how many would at least one math-club
member win?
2. How many outcomes involve no math club member winning?
3. How many outcomes involve exactly two math club members winning?
4. How many outcomes involve all three winners being club members?
Theorem 8.
Binomial Theorem.
If each of x and y is a real number and n
is a non-negative integer, then
(
x
+
y
)
n
=
n
0
x
n
+
n
1
x
n
-
1
y
+
n
2
x
n
-
2
y
2
+
···
+
n
n
-
1
xy
n
-
1
+
n
n
y
n
.
Problem 78.
Prove Theorem
8
. This theorem may be proved either using
tools from this chapter (a counting argument) or using tools from the forth-
coming chapter on induction.
Problem 79.
1. Expand
(
x
+
y
)
3
by hand and using the Binomial Theo-
rem.
2. Expand
(
x
-
y
)
5
using the Binomial Theorem.
3. Use the Binomial Theorem to expand
(
x
-
1
)
10
.
When x
=
2
,
what
happens?
Problem 80.
What is the coefficient of x
7
in the expansion of
(
1
+
x
)
23
?
3.1
Project: Unordered Samples and Probability, Inclu-
sion and Exclusion
Unordered Samples and Probability
Problem 81.
Suppose that A, B, and C are sets such that B
⊆
A, C
⊆
A,
B
∩
C
=
/0
,
|
A
|
=
60
,
|
B
|
=
25
, and
|
C
|
=
20
.
1. How many four-element subsets does A have?
2. How many five-element subsets of A contain no elements of B? How
many contain no elements of C? How many contain no elements of B
and no elements of C?
3. How many six-element subsets of A contain an element of B? How
many contain an element of B or an element of C?
4. How many seven-element subsets of A contain at least three elements
of B?
Definition 21.
Suppose that A and B are sets and B
⊆
A. If we randomly
choose an element of A, then the
probability
that the element we pick is in B
is
|
B
|
/
|
A
|
.
David M. Clark
W. Ted Mahavier
www.jiblm.org