Counting

Chapter 3 Counting

A more formal title for this chapter would be combinatorics. Many problems involving probability and statistics require knowing how many elements 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 3.1.

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 3.2.

There are six area codes used for Maryland telephone numbers: 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 number 555, or begin with the number 0. How many telephone numbers can be issued for the State of Maryland?

Problem 3.3.

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?

Problem 3.4.

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 3.5.

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 3.6.

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 3.7.

Multiplication Principle. If each of \(m\) and \(n\) is a positive integer, \(A\) is an \(m\)-element set, and \(B\) is an \(n\)-element set, then \(|A \times B| = mn\) or restated, \(|A \times B| = |A||B|\text{.}\) This is sometimes called the Fundamental Principle of Counting.

Theorem 3.8.

Generalized Multiplication Principle. Suppose that \(n\) is a positive integer and each of \(A_1, A_2, \dots ,A_n\) is a finite set. Then \(|A_1 \times A_2 \times A_3 \times \cdots \times A_n| = |A_1||A_2|\cdots|A_n|\text{.}\) This is sometimes called the Generalized or Fundamental Principle of Counting.

Example 3.9.

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?

Problem 3.10.

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 3.11.

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 3.12.

A program to produce greeting cards has 100 pictures to choose from and twenty-five sayings. How many different cards can the program produce?

Problem 3.13.

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?

Problem 3.14.

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 3.15.

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.

How many usernames are possible if they are not case-sensitive?
How many passwords are possible if they are not case-sensitive?
How many usernames are possible if they are case-sensitive?
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 3.16.

Let \(A\) be a set. By an unordered sample of size \(n\) chosen from \(A\) we mean an \(n\)-element subset of \(A\text{.}\) By an ordered sample of size \(n\) chosen from \(A\) we mean an \(n\)-element sequence of \((\)not necessarily distinct\()\) elements of \(A\text{.}\) 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 ordered samples of size 3 from the same population.

Using this language, we can restate Problem 3.3 as “How many unordered samples of size two can be chosen without replacement (or ``without repetition”) from the four-element “population” (Andrew, Bob, Carly, Diane)?'' In Problem 3.4, we sought an ordered sample of size two without replacement (repetition) from the same population. Finally, in Problem 3.5 we desired an ordered sample of size two “with replacement” (or “with repetition”).

Example 3.17.

Suppose you are working on a ten-digit keypad to open a door. You know the combination is exactly three digits long.

How many choices are there if you may use a number multiple times and the order matters?
How many choices are there if you may not use a number multiple times and the order matters?
How many choices are there if you may not use a number multiple times and the order does not matter?
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,\(\frac{1}{2}\)) is an ordered triple; and (7,\(\frac{1}{4}\text{,}\)\(\pi\text{,}\)z) is an ordered quadruple. If \(n\) is a positive integer and \(A\) is a set and \(a_i \in A\) for each integer \(i \in \{1,...,n\}\text{,}\) then (\(a_1\text{,}\) \(a_2\text{,}\) ..., \(a_n\)) is an ordered \(n\)-tuple.

Theorem 3.18.

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\text{.}\)

Theorem 3.19 is simply a restatement of Theorem 3.18 using fancy words!

Theorem 3.19.

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\text{.}\)

Ordered Samples without Repetition (permutations)

Theorem 3.20.

If n and k are positive integers with \(k \leq 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\text{,}\) is \((n-0)(n-1)(n-2) \cdots (n-(k-1)) = n (n - 1) (n - 2) \cdots (n - k + 1)\text{.}\)

If \(n\) is a non-negative integer then n factorial is denoted by \(n!\) and defined by

\begin{equation*} n! = \begin{cases} 1 \amp \text{if} \;\;\;\; n=0 \;\; \text{or} \;\; n=1 \\ n \cdot (n - 1) \cdots 2 \cdot 1 \amp \text{if} \;\;\;\; n > 1 \; \; \text{(the product of integers 1 to n)} \end{cases} \end{equation*}

Problem 3.21.

Show that

if \(n=10\) and \(k=3\text{,}\) then \(n(n - 1)(n - 2) \cdots (n - k + 1) = n!/(n - k)!\) and
if each of \(n\) and \(k\) is a positive integer and \(k \leq n\text{,}\) then \(n(n - 1)(n - 2) \cdots (n - k + 1) = n!/(n - k)!\text{.}\)

The next theorem is merely a restatement of Theorem 3.20 when \(k=n\text{.}\)

Theorem 3.22.

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!\text{.}\)

Definition 3.23.

If n is a positive integer and S is an n-element set, then a permutation of S is a bijection on S.

Example 3.24.

Let \(S = \{1, 2, 3\}\text{.}\) One permutation of \(S\) would be the bijection \(f : S \to S\) defined by \(f(1) = 2, f(2) = 3\text{,}\) and \(f(3)=1\text{.}\) Typically, we omit all the function notation and just write the range of \(f\) as \((2,3,1)\text{.}\) Recall that the order matters when we use \(()\) but not when we use \(\{\}\text{.}\)

Problem 3.25.

List all the permutations of \(S=\{1,2,3\}\text{.}\)

Problem 3.26.

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 3.27.

Let \(D=\{a,b,c\}\) and \(R=\{1,2,3,4,5\}\text{.}\) How many functions are there with domain all of \(D\) and with range a subset of \(R\text{?}\) How many are one-to-one? How many are onto \(R\text{?}\)

Problem 3.28.

Let \(D=\{a,b,c,d,e\}\) and \(R=\{1,2,3\}\text{.}\) How many functions are there with domain all of \(D\) and range a subset of \(R\text{?}\) How many are one-to-one? How many are onto \(R\text{?}\)

Unordered Samples without Repetition (subsets)

Problem 3.29.

Let \(D=\{a,b,c,d,e\}\text{.}\) How many three element subsets are there of \(D\text{?}\)

Theorem 3.30.

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 denoted by \(\begin{pmatrix}n \cr k \end{pmatrix}\) where \(\dsp \begin{pmatrix}n \cr k \end{pmatrix} = \frac{n!}{(n-k)!k!} \text{.}\)

Problem 3.31.

Compute \(\dsp{\frac{n!}{(n-k)!k!}}\) for each of

\(n=10\text{,}\) \(k=3\text{,}\)
\(n=10\text{,}\) \(k=7\text{,}\)
\(n=5\text{,}\) \(k=5\text{,}\) and
\(n=5\text{,}\) \(k=0\text{.}\)

Problem 3.32.

Show that

if \(n=20\) and \(k=12\) and \(j=8\) then \(\dsp{\frac{n!}{(n-k)!k!} = \frac{n!}{(n-j)!j!}}\) and
if \(n\) is a positive integer and \(k\) is a nonnegative integer not larger than \(n\) and \(j=n-k\) then \(\dsp{ \frac{n!}{(n-k)!k!} = \frac{n!}{(n-j)!j!}}\text{.}\)

Problem 3.33.

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

Give each child exactly one CD?
Give away all the CD's so that each child gets at least one without giving any child more than two?
Give away all the CD's so that each child gets at least one?

Problem 3.34.

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\text{.}\) How many functions are there from \(A\) to \(B\text{?}\) How many are one-to-one? How many are onto \(B\text{?}\)

Problem 3.35.

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 3.36.

You and thirteen of your closest friends have decided to form a club.

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?
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 3.37.

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.

How many possible seating arrangements are there?
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 3.38.

An elementary-school teacher is directing an after-school parade 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.

How many different parades are possible if he wants to have the twirlers followed by the cymbal players, with the tumblers at the rear?
How many are possible if he simply keeps together the children who are doing the same thing?
How many would be possible in a free-for-all, where the kids are in any order?
How many are possible if the twirlers stay together but the others can be in any order?

Problem 3.39.

A coin is tossed six times and the results, heads or tails on each toss, are recorded in order.

How many outcomes are possible?
How many of these have exactly one head?
How many have at least one head?
How many have at least one head and at least one tail?

Definition 3.40.

Suppose that \(A\) is a set and \(f: A \to A\) is a function. If \(x\in A\) satisfies \(f(x)=x\text{,}\) then we say that \(x\) is a fixed point of \(A\) with respect to \(f\).

Problem 3.41.

Suppose that \(A = \{a, b, c, d\}\text{.}\)

How many functions are there on \(A\) for which \(a\) is a fixed point?
How many for which \(a\) and \(b\) are fixed points?
How many for which \(a\text{,}\) \(b\) and \(c\) are fixed points?
How many functions are there that fix every point of \(A\text{?}\)

Problem 3.42.

Suppose \(A = \{a, b, c, d \}\text{.}\) Let F1 be the set of functions \(f:A \to A\) for which \(a\) is a fixed point. Let F2 be the set of functions \(f:A \to A\) for which \(a\) and \(b\) are fixed points. Let F3 be the set of functions \(f:A \to A\) for which \(a\text{,}\) \(b\) and \(c\) are fixed points. Let F4 be the set of functions for which all four elements are fixed points. What are \(|F1 \cap F2|\text{,}\) \(|F3 \cap F2|\text{,}\) \(|F3 \cap F4|\) and \(|F1 \cap F2 \cap F3|\text{?}\)

Problem 3.43.

If six cards are chosen without replacement from a standard deck, how many hands are possible if

the six cards can be anything?
at least one card is an ace?
at least four are clubs?
exactly three of the cards are hearts?

Problem 3.44.

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.

Of the possible outcomes, in how many would at least one math-club member win?
How many outcomes involve no math club member winning?
How many outcomes involve exactly two math club members winning?
How many outcomes involve all three winners being club members?

Theorem 3.45.

Binomial Theorem. If each of \(x\) and \(y\) is a real number and \(n\) is a non-negative integer, then

\begin{equation*} (x+y)^n = \begin{pmatrix}n \cr 0 \end{pmatrix} x^n + \begin{pmatrix}n \cr 1 \end{pmatrix} x^{n-1}y + \begin{pmatrix}n \cr 2 \end{pmatrix} x^{n-2}y^2 + \dots + \begin{pmatrix}n \cr n-1 \end{pmatrix} x y^{n-1} + \begin{pmatrix}n \cr n \end{pmatrix} y^n\text{.} \end{equation*}

Problem 3.46.

Prove Theorem 3.45. This theorem may be proved either using tools from this chapter (a counting argument) or using tools from the forthcoming chapter on induction.

Problem 3.47.

Expand \((x + y)^3\) by hand and using the Binomial Theorem.
Expand \((x - y)^5\) using the Binomial Theorem.
Use the Binomial Theorem to expand \((x - 1)^{10}\text{.}\) When \(x = 2\text{,}\) what happens?

Problem 3.48.

What is the coefficient of \(x^7\) in the expansion of \((1 + x)^{23}\text{?}\)