2.9: Exercises

1. The Hawaiian alphabet consists of 12 letters. How many six-character strings can be made using the Hawaiian alphabet?
2. How many \(2n\)-digit positive integers can be formed if the digits in odd positions (counting the rightmost digit as position 1) must be odd and the digits in even positions must be even and positive?
3. Matt is designing a website authentication system. He knows passwords are most secure if they contain letters, numbers, and symbols. However, he doesn't quite understand that this additional security is defeated if he specifies in which positions each character type appears. He decides that valid passwords for his system will begin with three letters (uppercase and lowercase both allowed), followed by two digits, followed by one of 10 symbols, followed by two uppercase letters, followed by a digit, followed by one of 10 symbols. How many different passwords are there for his website system? How does this compare to the total number of strings of length 10 made from the alphabet of all uppercase and lowercase English letters, decimal digits, and 10 symbols?
4. How many ternary strings of length \(2n\) are there in which the zeroes appear only in odd-numbered positions?
5. Suppose we are making license plates of the form \(l_1l_2l_3 - d_1d_2d_3\) where \(l_1,l_2,l_3\) are capital letters in the English alphabet and \(d_1,d_2,d_3\) are decimal digits (i.e., elements of the set \(\{0,1,2,3,4,5,6,7,8,9\})\) subject to the restriction that at least one digit is nonzero and at least one letter is \(K\). How many license plates can we make?
6. Mrs. Steffen's third grade class has 30 students in it. The students are divided into three groups (numbered 1, 2, and 3), each having 10 students.

a) The students in group 1 earned 10 extra minutes of recess by winning a class competition. Before going out for their extra recess time, they form a single file line. In how many ways can they line up?

b) When all 30 students come in from recess together, they again form a single file line. However, this time the students are arranged so that the first student is from group 1, the second from group 2, the third from group 3, and from there on, the students continue to alternate by group in this order. In how many ways can they line up to come in from recess?

7. How many strings of the form \(l_1l_2d_1d_2d_3l_3l_4d_4l_5l_6\) are there where

• for \(1 \leq i \leq 6\), \(l_i\) is an uppercase letter in the English alphabet
• for \(1 \leq i \leq 4\), \(d_i\) is a decimal digit
• \(l_2\) is not a vowel (i.e., \(l_2 \notin \{A,E,I,O,U\}\))
• the digits \(d_1,d_2\), and \(d_3\) are distinct (i.e., \(d_1 \neq d_2 \neq d_3 \neq d_1\))

8. In this exercise, we consider strings made from uppercase letters in the English alphabet and decimal digits. How many strings of length 10 can be constructed in each of the following scenarios?

a) The first and last characters of the string are letters.

b) The first character is a vowel, the second character is a consonant, and the last character is a digit.

c) Vowels (not necessarily distinct) appear in the third, sixth, and eighth positions and no other positions.

d) Vowels (not necessarily distinct) appear in exactly two positions.

e) Precisely four characters in the string are digits and no digit appears more than one time.

9. A database uses 20-character strings as record identifiers. The valid characters in these strings are upper-case letters in the English alphabet and decimal digits. (Recall there are 26 letters in the English alphabet and 10 decimal digits.) How many valid record identifiers are possible if a valid record identifier must meet all of the following criteria:

• Letter(s) from the set \(\{A,E,I,O,U\}\) occur in exactly three positions of the string.
• The last three characters in the string are distinct decimal digits that do not appear elsewhere in the string.
• The remaining characters of the string may be filled with any of the remaining letters or decimal digits.

10. Let \(X\) be the set of the 26 lowercase English letters and 10 decimal digits. How many \(X\)-strings of length 15 satisfy all of the following properties (at the same time)?

• The first and last symbols of the string are distinct digits (which may appear elsewhere in the string).
• Precisely four of the symbols in the string are the letter '\(t\)'.
• Precisely three characters in the string are elements of the set \(\{a,e,i,o,u\}\) and these characters are all distinct.

11. A donut shop sells 12 types of donuts. A manager wants to buy six donuts, one each for himself and his five employees.

a) Suppose that he does this by selecting a specific type of donut for each person. (He can select the same type of donut for more than one person.) In how many ways can he do this?

b) How many ways could he select the donuts if he wants to ensure that he chooses a different type of donut for each person?

c) Suppose instead that he wishes to select one donut of each of six different types and place them in the breakroom. In how many ways can he do this? (The order of the donuts in the box is irrelevant.)

12. The sport of korfball is played by teams of eight players. Each team has four men and four women on it. Halliday High School has seven men and 11 women interested in playing korfball. In how many ways can they form a korfball team from their 18 interested students?

13. Twenty students compete in a programming competition in which the top four students are recognized with trophies for first, second, third, and fourth places.

a) How many different outcomes are there for the top four places?

b) At the last minute, the judges decide that they will award honorable mention certificates to four individuals who did not receive trophies. In how many ways can the honorable mention recipients be selected (after the top four places have been determined)? How many total outcomes (trophies plus certificates) are there then?

14. An ice cream shop has a special on banana splits, and Xing is taking advantage of it. He's astounded at all the options he has in constructing his banana split:

• He must choose three different flavors of ice cream to place in the asymmetric bowl the banana split is served in. The shop has 20 flavors of ice cream available.
• Each scoop of ice cream must be topped by a sauce, chosen from six different options. Xing is free to put the same type of sauce on more than one scoop of ice cream.
• There are 10 sprinkled toppings available, and he must choose three of them to have sprinkled over the entire banana split.

a) How many different ways are there for Xing to construct a banana split at this ice cream shop?

b) Suppose that instead of requiring that Xing choose exactly three sprinkled toppings, he is allowed to choose between zero and three sprinkled toppings. In this scenario, how many different ways are there for him to construct a banana split?

15. Suppose that a teacher wishes to distribute 25 identical pencils to Ahmed, Barbara, Casper, and Dieter such that Ahmed and Dieter receive at least one pencil each, Casper receives no more than five pencils, and Barbara receives at least four pencils. In how many ways can such a distribution be made?

16. How many integer-valued solutions are there to each of the following equations and inequalities?

a) \(x_1+x_2+x_3+x_4+x_5=63\), all \(x_i > 0\)

b) \(x_1+x_2+x_3+x_4+x_5=63\), all \(x_i \geq 0\)

c) \(x_1+x_2+x_3+x_4+x_5 \leq 63\), all \(x_i \geq 0\)

d) \(x_1+x_2+x_3+x_4+x_5=63\), all \(x_i \geq 0, x_2 \geq 10\)

e) \(x_1+x_2+x_3+x_4+x_5=63\), all \(x_i \geq 0, x_2 \leq 9\)

17. How many integer solutions are there to the equation

\(x_1+x_2+x_3+x_4 = 132\)

provided that \(x_1 > 0\), and \(x_2,x_3,x_4 \geq 0\)? What if we add the restriction that \(x_4 < 17\)?

18. How many integer solutions are there to the inequality

\(x_1+x_2+x_3+x_4+x_5 \leq 782\)

provided that \(x_1,x_2 > 0\), \(x_3 \geq 0\), and \(x_4,x_5 \geq 10\)?

19. A teacher has 450 identical pieces of candy. He wants to distribute them to his class of 65 students, although he is willing to take some leftover candy home. (He does not insist on taking any candy home, however.) The student who won a contest in the last class is to receive at least 10 pieces of candy as a reward. Of the remaining students, 34 of them insist on receiving at least one piece of candy, while the remaining 30 students are willing to receive no candy.

a) In how many ways can he distribute the candy?

b) In how many ways can he distribute the candy if, in addition to the conditions above, one of his students is diabetic and can receive at most 7 pieces of candy? (This student is one of the 34 who insist on receiving at least one piece of candy.)

20. Give a combinatorial argument to prove the identity

\(k\dbinom{n}{k} = n\dbinom{n-1}{k-1}\).

Hint

Think of choosing a team with a captain.

21. Let \(m\) and \(w\) be positive integers. Give a combinatorial argument to prove that for integers \(k \geq 0\),

\(\displaystyle \sum_{j=0}^k \dbinom{m}{j} \dbinom{w}{k-j} = \dbinom{m+w}{k}\).

22. How many lattice paths are there from (0,0) to (10,12)?

23. How many lattice paths are there from (3,5) to (10,12)?

24. How many lattice paths are there from (0,0) to (10,12) that pass through (3,5)?

25. How many lattice paths from (0,0) to (17,12) are there that pass through (7,6) and (12,9)?

26. How many lattice paths from (0,0) to (14,73) are there that do not pass through (6,37)?

27. A small-town bank robber is driving his getaway car from the bank he just robbed to his hideout. The bank is at the intersection of 1st Street and 1st Avenue. He needs to return to his hideout at the intersection of 7th Street and 5th Avenue. However, one of his lookouts has reported that the town's one police officer is parked at the intersection of 4th Street and 4th Avenue. Assuming that the bank robber does not want to get arrested and drives only on streets and avenues, in how many ways can he safely return to his hideout? (Streets and avenues are uniformly spaced and numbered consecutively in this small town.)

28. The setting for this problem is the fictional town of Mascotville, which is laid out as a grid. Mascots are allowed to travel only on the streets, and not “as the yellow jacket flies.” Buzz, the Georgia Tech mascot, wants to go visit his friend Thundar, the North Dakota State University mascot, who lives 6 blocks east and 7 blocks north of Buzz's hive. However, Uga VIII has recently moved into the doghouse 2 blocks east and 3 blocks north of Buzz's hive and already has a restraining order against Buzz. There's also a pair of tigers (mother and cub) from Clemson who live 1 block east and 2 blocks north of Uga VIII, and they're known for setting traps for Buzz. Buzz wants to travel from his hive to Thundar's pen every day without encountering Uga VIII or The Tiger and The Tiger Cub. However, he wants to avoid the boredom caused by using a route he's used in the past. What is the largest number of consecutive days on which Buzz can make the trip to visit Thundar without reusing a route (you may assume the routes taken by Buzz only go east and north)?

29. Determine the coefficient on \(x^{15}y^{120}z^{25}\) in \((2x+3y^2+z)^{100}\).

30. Determine the coefficient on \(x^{12}y^{24}\) in \((x^3+2xy^2+y+3)^{18}\). (Be careful, as \(x\) and \(y\) now appear in multiple terms!)

31. For each word below, determine the number of rearrangements of the word in which all letters must be used.

a) OVERNUMEROUSNESSES

b) OPHTHALMOOTORHINOLARYNGOLOGY

c) HONORIFICABILITUDINITATIBUS (the longest word in the English language consisting strictly of alternating consonants and vowels)

32. How many ways are there to paint a set of 27 elements such that 7 are painted white, 6 are painted old gold, 2 are painted blue, 7 are painted yellow, 5 are painted green, and 0 of are painted red?

33. There are many useful sets that are enumerated by the Catalan numbers. (Volume two of R.P. Stanley's Enumerative Combinatorics contains a famous (or perhaps infamous) exercise in 66 parts asking readers to find bijections that will show that the number of various combinatorial structures is \(C(n)\), and his web page boasts an additional list of at least 100 parts.) Give bijective arguments to show that each class of objects below is enumerated by \(C(n)\). (All three were selected from the list in Stanley's book.)

a) The number of ways to fully-parenthesize a product of \(n+1\) factors as if the “multiplication” operation in question were not necessarily associative. For example, there is one way to parenthesize a product of two factors \((a_1a_2)\), there are two ways to parenthesize a product of three factors \(((a_1(a_2a_3))\) and \(((a_1a_2)a_3))\), and there are five ways to parenthesize a product of four factors:

\((a_1(a_2(a_3a_4))),(a_1((a_2a_3)a_4)),((a_1a_2)(a_3a_4)),((a_1(a_2a_3))a_4),(((a_1a_2)a_3)a_4)\).

b) Sequences of \(n\) 1's and \(n −1\)'s in which the sum of the first \(i\) terms is nonnegative for all \(i\).

c) Sequences \(1 \leq a_1 \leq \cdot \cdot \cdot \leq a_n\) of integers with \(a_i \leq i\). For example, for \(n=3\), the sequences are

111 112 113 122 123

Hint

For part 2.9.33.c, think about drawing lattice paths on paper with grid lines and (basically) the number of boxes below a lattice path in a particular column.