434 CHAPTER^7 Counting and Combinatorics
- A palindrome is a string that reads the same forward and as it reads backward. An
example (if blanks and punctuation are ignored) is: A man, a plan, a canal, Panama.
How many n-letter palindromes can be formed using the alphabet {0, 11? - In the United States and Canada, a telephone number is a 10-digit number of the form
NXX-NXX-XXXX where N c {2, 3,..., 9} and X c {0, 1, 2,..., 91. How many tele-
phone numbers are possible? The first three digits of a telephone number are called an
area code. How many different area codes must a city with 23,000,000 phones have?
A previous scheme for forming telephone numbers required a format of NYX-NXX-
XXXX where N and X are defined as above and Y is either a 0 or a 1. How many more
phone numbers are possible under the new format than under the old format?- How many ways can a computer system be configured if there are k input devices,
m processors, and n output devices. A configuration consists of an input device, a
processor, and an output device connected for use together. If k = 3, m = 6, and n = 4,
draw three possible system configurations if every processor must be connected to at
least one input device and two output devices. - The Omnibus Society has four officers: chair, secretary, treasurer, and editor. The by-
laws for holding office state that one person shall be eligible to hold two, but not more
than two, offices concurrently. If the Society has 1000 members, in how many ways
can the officers be selected? - A flag is to consist of six vertical stripes in yellow, green, blue, orange, brown, and
red. It is not necessary to use all the colors. The same color may be used more than
once. How many possible flags are there with no two adjacent stripes the same color? - A convex polygon is a polygon such that any line segment joining two points inside the
polygon lies entirely inside the polygon. If no 3 of the 15 diagonals of a convex, six-
sided polygon intersect at a point common to all three, into how many line segments
are the diagonals divided by their intersection points? Can you conjecture and prove a
general result for an n-sided convex polygon? - How many sequences of length n can be formed using the alphabet {0, 1 }? Using the
alphabet {0, 1, 2}? Using the alphabet [1, 2 ... , k} for k E N? How many possible
words are there in the English language of length 13 at most? If a dictionary contains
500,000 words of length less than or equal to 13, what percentage of all words of
length less than or equal to 13 does it contain? - How many ways can three integers be selected from 3n consecutive integers so that the
sum is a multiple of 3? Here, n is a positive integer. What if the three chosen integers
must be distinct? - A three out of five series is a competition between two teams consisting of at most
five games and ending as soon as one of the two competing teams wins three games.
How many different three out of five series are possible? Two series are "different" if
the sequence of winners and losers in one series is not the same as in the other series.
Draw a tree to represent the possibilities. - A four out of seven series is a competition between two teams consisting of at most
seven games and ending as soon as one of the two competing teams wins four games.
How many different four out of seven series are possible? Two series are "different" if
the sequence of winners and losers in one series is not the same as in the other series.
Draw a tree to represent the possibilities. - How many injective functions are there from S to T if S1 = n and ITI = m where
n <m?