Chapter Six
Counting
WARNING: The web material for this chapter contains many
(invisible) tables. If some of the equations look cramped on your screen, try maximizing
the size of your window and hopefully the tables will straighten themselves out.
Section 6.1
Counting and Probability
The following solutions make use of information found on pages 273 - 279 of the
textbook.
Exercise 6.1.1: Definitions
Fill in the blanks to complete the following sentences.
- A process is said to be random if
when
it takes place, one outcome from some set of outcomes is sure to
occur but it is
impossible to predict with certainty which outcome will occur.
- A sample space is the set of all possible
outcomes of a random process or experiment.
- An event is a subset of a
sample space.
- If S is a finite sample space in which all outcomes are equally
likely and E is an event
in S, then the probability of E, denoted
P(E),
is
P(E) = (the number of outcomes in E) / (the total number of outcomes
in S).
- For any finite set A, n(A) denotes the number of
elements in the set A.
An alternate notation for n(A) is |A|.
- Let m and n be integers with
m £ n. Then there are
n - m + 1 integers from m to n
inclusive.
Exercise 6.1.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
1. In the game of Two Up, you bet on either heads or tails. Two coins are
tossed. You win if both coins show the side you bet on and you lose if both coins show the
opposite side you bet on. If the two coins show a combination of heads and tails, nothing
happens (your bet stays as it was) and the coins are tossed again.
a) If this was the complete set of rules for Two Up, work out the probability that
i) you win on the first toss.
ii) you win if you are betting on heads (after the coins are tossed as many times as
necessary to get either two heads or two tails).
Hint
Full solution
b) There is an additional rule in Two Up. If the coin toss turns up a combination of a
head and a tail five times in a row, the house takes all the bets (so all the players
lose). What is the probability that five coin tosses in a row show a mix of heads and
tails?
Hint
Full solution
2. a) How many integers from 1000 to 10000 inclusive are multiples of four?
b) What is the probability that a randomly chosen integer from 1000 to 10000 inclusive
is divisible by four?
Hint
Full solution
3. Suppose you have a list of the integers written consecutively from -52 to 57.
a) How many integers are in the list?
Full solution
b) Where would you have to split the list (into two sublists) in order to have a
sublist containing 61 consecutive integers?
Hint
Full solution
Section 6.2
Trees and the Multiplication Rule
The following solutions make use of information found on pages 281 - 292 of the
textbook.
Exercise 6.2.1: Definitions
Fill in the blanks to complete the following sentences.
- The Multiplication Rule
Let O be an operation consisting of k steps where:
there are n1 different ways to perform
the first step,
there are n2 different ways to perform
the second step (regardless of
how the first step was performed),
:
:
there are nk different ways to perform
the kth step (regardless of how
the preceding steps were performed).
Then there are n1 · n2
· ... · nk different ways to perform the
entire operation O.
A tree can be used to represent the set of all possible
outcomes of the operation O.
- A permutation of a set of objects is an
arrangement or
ordering of the objects in a row.
- Theorem: For any integer n with
n
1, the number of permutations of a set with
n elements is n!
- An r-permutation of a set of
n elements is an
ordered selection of r elements taken from the set of n
elements.
The number of r-permutations of a set of n elements is
denoted P(n,r).
- Theorem: For positive integers n and r, where
1 £
r £ n, the number of
r-permutations of a set of
n elements is given by the formula
P(n,r) = n (n-1) (n-2) ... (n-r+1)
or, equivalently, P(n,r) = n! / (n-r)!.
Exercise 6.2.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
1. How many bit strings (strings of 0s and 1s) of length n are there?
Hint
Full solution
2. How many bit strings (strings of 0s and 1s) of length four do not have two
consecutive 1s?
Hint
Full solution
3. Beginning with the letter A at the top of the pyramid and reading down, always
passing from a letter to an adjoining letter, in how many ways is it possible to read ABRACADABRA?
Hint
Full solution
4. a) Consider the following nested loop:
for i = 1 to 4
for j = 1 to
3
for
k = 1 to 5
Statements in body of inner loop
None lead out of the inner loop
next
k
next j
next i
How many times will the inner loop be iterated when the program runs?
b) Consider the following nested loop:
for i = 1 to n
for j = 1
to n
for
k = 1 to n
Statements in body of inner loop
None lead out of the inner loop
next
k
next j
next i
How many times will the inner loop be iterated when the program runs?
Hint
Full solution
5. How many four digit numbers, which are not divisible by five, can be created using
the digits 4, 5, 6 and 7, without repeating any digits.
Hint
Full solution
6. At the local Chinese take-away, the menu consists of 6 chicken dishes, 7 pork
dishes, 9 beef dishes and 5 vegetarian dishes. Your prospective in-laws are coming to
dinner tonight and you want to impress them by providing a variety of dishes. You decide
to buy 4 dishes from the take-away (one each of chicken, pork, beef and vegetarian). How
many possible meal combinations could you serve?
Hint
Full solution
7. In how many ways can a photographer at a wedding arrange six people in a row,
including the bride and groom, if:
a) the bride must be next to the groom?
b) the groom's mother is not next to the bride?
c) the bride's mother is to the left of the groom (not necessarily right beside him)?
Hint
Full solution
Section 6.3
Counting Elements of Disjoint Sets: The Addition Rule
The following solutions make use of information found on pages 295 - 303 of the
textbook.
Exercise 6.3.1: Definitions
Fill in the blanks to complete the following sentences.
- Let A1, A2,..., Ak be a
collection of sets which partition a finite set A. Then (from the
definition of a partition in Chapter 5)
A = A1 È
A2 È
... È
Ak and for i,j
Î {1,2,...,k} and i not equal to j
Ai Ç Aj
= Æ.
The Addition Rule states that:
n(A) = n(A1) + n(A2)
+ ... + n(Ak).
- Let S be a finite sample space, A be an event in S and
Ac be the complement of A in S. Then
1 - P(Ac) = P(A)
- The Inclusion/Exclusion Rule
If A, B and C are any finite sets, then
n(A È
B) = n(A) + n(B) -
n(A Ç B).
and n(A È B È C)
= n(A) + n(B) + n(C) - n(A Ç B) - n(A Ç C) - n(B Ç C) + n(A Ç B Ç C).
Exercise 6.3.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
1. Refer back to the Chinese take-away in Section 6.2, Question 6, and recall that
there were 6 chicken dishes, 7 pork dishes, 9 beef dishes and 5 vegetarian dishes. Tonight
you are on your own and you would like one dish from the take-away. However, after the
latest salmonella outbreak, you have decided not to eat chicken for a few weeks. How many
ways are there to choose your meal?
Full solution
2. Suppose that you go to the Chinese take-away for dinner with two friends and you
each randomly choose one dish (which could all be the same) and then share the three
dishes for your meal.
a) What is the probability that the three of you end up with a meal that does not
consist only of chicken dishes?
b) What is the probability that the three of you end up with a meal that has no
vegetarian dishes in it?
Hint
Full solution
3. A total of 1232 students have taken a course in Statistics, 879 have taken a course
in Calculus and 114 have taken a course in Logic. Furthermore, 103 have taken courses in
both Statistics and Calculus, 23 have taken courses in both Statistics and Logic and 14
have taken courses in both Calculus and Logic. If 2092 students have taken at least one
course in Statistics, Calculus or Logic, how many students have taken courses in all three
maths subjects?
Hint
Full solution
4. Solve the Chelsea Pensioners puzzle by Lewis Carroll: If 70 % have
lost an eye, 75 % an ear, 80 % an arm and 85 % a leg, what percentage at least must have
lost all four?
Hint
Full solution
Section 6.4
Combinations
The following solutions make use of information found on pages 306 - 320 of the
textbook.
Exercise 6.4.1: Definitions
Fill in the blanks to complete the following sentences.
- An ordered selection of r elements from a set of
n elements is an r-permutation of the set.
An unordered selection of r elements from a set of
n elements is an r-combination of the set.
- Let r and n be nonnegative integers with r
£ n. An r-combination
chosen from a set of n elements is a subset
consisting of r of the n elements.
The number of r-combinations that can be chosen from a set of
n elements is denoted by
( nr )
read "n choose r".
An r-combination is merely a collection of r different elements chosen
from a set of n elements.
Alternate notation to
( nr ) is C(n,r).
- Theorem:
Let n and r be nonnegative integers, with
r £ n.
The number of subsets of size r (or r-combinations) that can
be chosen from a set of n elements,
( nr ), is given by the formula
(nr) = P(n,r) / r!
or, equivalently, (nr) =
n! / (r! (n-r)!).
- Suppose a collection of n objects consists of:
n1 indistinguishable
objects of type 1;
n2
indistinguishable objects of type 2;
:
:
nk indistinguishable objects
of type k;
where n1 + n2 + ... + nk = n.
Then
the number of distinct permutations of the collection of n objects is
C(n, n1) × C(n-n1, n2) ×
C(n-n1-n2, n3) × ... ×
C(n-n1-n2-...-nk-1, nk)
Using the above Theorem it can be shown that
C(n, n1) × C(n-n1, n2) ×
C(n-n1-n2, n3) × ... ×
C(n-n1-n2-...-nk-1, nk) =
n! /
(n1! n2! ... nk!).
Exercise 6.4.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
1. Calculate (without a calculator) the value of
a) |
( |
9 |
) |
b) |
( |
200 |
) |
|
3 |
198 |
Hint
Full solution
2. There are five questions on your maths assignment but you only have time to complete
three of them. How many combinations of questions are there which you could complete?
Hint
Full solution
3. You are playing a word game in which you must make up a sentence using the three
words you draw out of a bag containing ten words.
a) How many possible ways are there to choose three words from the bag of ten words?
b) Suppose the game rules change so that you now have to make up a sentence in which
the three words appear in the order in which they were chosen.
How many possible combinations are there now?
c) What is the relationship between your answers to parts a) and b)?
Hint
Full solution
4. Recall that the Chinese take-away sells six chicken dishes, seven pork dishes, nine
beef dishes and five vegetarian dishes.
a) This week they have a promotional deal in which, if you buy the chicken with noodles
dish, you get a beef and black bean dish for free. How many ways are there to choose four
different main dishes (assuming that if you choose the chicken with noodles, you also take
the beef and black bean)?
Hint
Full solution
b) From previous experience, you realize that there are two pork dishes which do not go
well together. How can you choose four main dishes which contain at most one of the two
pork dishes?
Hint
Full solution
5. In the game of poker each player is dealt five cards from an
ordinary deck of cards, and each player is said to have a 5-card hand.
(You may like to refer to Example 6.4.9 on page 316 of your textbook.)
a) How many 5-card poker hands contain four cards of the same
denomination (four of a kind)?
Hint
Full solution
b) Find the error in the following calculation of the number of 5-card poker hands
which contain at least one jack. Once you have found the error,
calculate the true number
of 5-card poker hands which contain at least one jack.
Consider this in two steps:
Choose one jack from the four jacks.
Choose the other four cards in the hand.
Thus we have C(4, 1) C(51, 4) = 999600 such hands.
Hint
Full solution
6. How many distinct ways are there to arrange the letters of the word abracadabra?
Hint
Full solution
Section 6.5
r-Combinations with Repetition Allowed (Extension material)
The following solutions make use of information found in the reading and the textbook.
Exercise 6.5.1: Definitions
Fill in the blanks to complete the following sentences.
- The number of r-combinations that can be chosen from a set with n elements when
repetition is allowed is
|
( |
r + n - 1 |
). |
|
r |
Exercise 6.5.2: Examples
You should attempt all these exercises yourself, using the textbook and reading as an
aid. Once you have attempted each question, check your answers by following the
appropriate links. If you are stuck on a question, choose the link that gives you a hint
and then try the question again.
1. The Chinese take-away shop sells fortune cookies with fortunes relating to Health,
Wealth, Happiness and Love. Normally these fortune cookies are kept in four separate jars,
but to save space on the counter, they have all been put into one big jar. Assuming that
there are at least six fortune cookies of each type in the jar, how many different
combinations of the fortune types can you get if you choose six cookies from the jar?
Hint
Full solution
2. How many solutions does the equation x + y + z = 11 have, where x, y and
z are all non-negative integers?
Hint
Full solution
Section 6.6
Useful Formulas
The following solutions make use of information found on pages 330 - 335 of the
textbook.
Exercise 6.6.1: Definitions
Fill in the blanks to complete the following sentences.
- Let n and r be positive integers with
r £ n.
A combinatorial proof that
is based on the fact that the number of subsets of size r, from a set
of size n, is the same as the number of subsets of size
n-r from a set of size n.
An algebraic proof that C(n, r) = C(n, n - r)
is
C(n, r) = n! / (r! (n-r)!) and C(n, n - r) = n! / ((n-r)! r!).
- Pascal's Formula: Let n and r be positive integers and
suppose r £ n.Then
( |
n + 1 |
) |
= |
( |
n |
) |
+ |
( |
n |
). |
| r |
r - 1 |
r |
Exercise 6.6.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
| 1. Given that |
( |
n |
) |
= |
n (n - 1) , |
find an expression for |
( |
x + 3 |
). |
| n - 2 |
2 |
x + 1 |
Hint
Full solution
| 2. Use Pascal's formula to compute: |
a) |
( |
7 |
) |
+ |
( |
7 |
) |
b) |
( |
9 |
) |
+ |
( |
9 |
). |
| 5 |
6 |
6 |
5 |
Hint
Full solution
Section 6.7
The Binomial Theorem
The following solutions make use of information found on pages 336 - 342 of the
textbook.
Exercise 6.7.1: Definitions
Fill in the blanks to complete the following sentences.
- The sum of two terms is called a binomial. Examples of binomials
are a + b, 2x + 4y, m2 + 5n.
- The Binomial Theorem:
Given any real numbers a and b and any nonnegative integer n,
| (a + b)n |
= |
n |
( |
n |
) |
an-k bk |
|
| S |
| k |
| k=0 |
|
|
|
|
= |
| an |
+ |
( |
n |
) |
an-1 b1 |
+ |
( |
n |
) |
an-2 b2 |
+ |
... |
+ |
( |
n |
) |
a1 bn-1 |
+ |
bn. |
|
|
|
|
| 1 |
2 |
n-1 |
|
Exercise 6.7.2: Examples
You should attempt all these exercises yourself, using the textbook as an aid. Once you
have attempted each question, check your answers by following the appropriate links. If
you are stuck on a question, choose the link that gives you a hint and then try the
question again.
1. Expand the following using the Binomial Theorem.
a) (x + y)4
b) (2a - 3b)5
Hint
Full solution
2. Find the coefficient of m2 n8 in the expansion of
(m + n)10.
Hint
Full solution
3. Find the coefficient of x6 y3 in the expansion of
(5x - 3y)9.
Hint
Full solution
Back to workbook solution page