Strings, Sets, and Binomial Coefficients: exercises

Practice (40)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

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?

   Avslöja svaret

   There are 52 choices for each of the first three positions, since both uppercase and lowercase letters are allowed. There are 10 choices for each of the next two positions, since they must be digits. There are 10 choices for the next position, which must be a symbol. The two uppercase letters have 26 choices each. The last two positions have 10 choices each, first as a digit and then as a symbol. Thus, his website has \(52^{3}\cdot 10^{2}\cdot 10\cdot 26^{2}\cdot 10\cdot 10 = 9,505,100,800,000\) possible passwords. If, on the other hand, he allowed any of the 72 characters in each of the 10 positions, he'd have \(72^{10}= 3,743,906,242,624,487,424\) passwords, which is several orders of magnitude more options!

4. How many ternary strings of length \(2n\) are there in which the zeroes appear only in odd-numbered positions?

   Avslöja svaret

   For the odd-numbered positions, of which there are \(n\), we have 3 choices. For the even-numbered positions, of which there are also \(n\), we have only 2 choices. Thus, the number of such ternary strings is \(3^{n}\cdot 2^{n}\).

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 (, 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?

   Avslöja svaret

   There are a couple of ways to approach this. You could process at least one K by thinking of it as meaning exactly one K or exactly two K's or exactly three K's and at least one digit is nonzero as exactly two digits are 0 or exactly one digit is 0 or no digits are 0. For K's, you'd have then \(C(3,1)25^{2} + C(3,2) 25^{1} + C(3,3)\) since you need to pick which position(s) are K and then fill in the other position(s) with one of the other 25 letters. For digits, you'd have \(C(3,1)9^{2} + C(3,2) 9^{1} + C(3,3)9^{3}\), and then you would multiply these to get the total number of license plates: \[\begin{aligned}\end{aligned}\].

   Alternatively, you could realize that the only strings of letters you don't want to allow are those with no K's, so you can subtract off the strings with no K's from the total number \(26^{3}-25^{3}\). Similarly for digits, you can just subtract the 000 case, which is unique, so there are \(10^{3}-1 = 999\) digit strings. Thus, you would have \((26^{3}-25^{3})\cdot 999\).

   Although these expressions might not look equal, you can check with a calculator that they are!

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.

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

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

   Avslöja svaret

   1. There are \(P(10,10)=10!\) ways for the 10 students in Group 1 to line up.

   2. We can view this as filling in 30 blanks where the first, fourth, seventh, etc. blank must come from group 1, the second, fifth, eighth, etc. must come from group 2, and the third, sixth, ninth, etc. must come from group 3. Hence, there are 10 choices for each of the first, second, and third blanks, 9 choices for each of the fourth, fifth, and sixth blanks, etc. This continues down until the 28th, 29th, and 30th blanks each have a single choice since there is only one remaining student in each group. Therefore, there are \((10!)^{3}\) ways for the students to line up.

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

   • \(1\leq i\leq 6\)\(l_i\)
   • \(1\leq i\leq 4\)\(d_i\)
   • \(l_2\)\(l_2\nin\{\text{A,E,I,O,U} \}\)
   • \(d_1\)\(d_2\)\(d_3\)\(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?

   1. The first and last characters of the string are letters.

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

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

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

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

   Avslöja svaret

   1. We have 26 choices for each of the first and last positions and 36 for the interior eight, so we have \(26^{2}\cdot 36^{8}\) strings.

   2. There are five vowels (choices for the first character), 21 consonants (choices for the second character), and 10 digits (choices for the last position). There are 36 choices for each of the remaining seven positions, so we have \(5\cdot 21\cdot 10\cdot 36^{7}\) strings.

   3. We have five choices for each of the third, sixth, and eighth positions. Since vowels do not appear in other positions, we have \(21+10 = 31\) options for each of the remaining seven positions. Thus, we have \(5^{3}\cdot 31^{7}\) strings.

   4. We first choose two positions for the vowels in \(C(10,2)\) ways. Since the vowels need not be distinct, we have five choices for each of those two positions. There are now \(21+10=31\) options for each of the remaining positions since we cannot use vowels. Thus, we have \(C(10,2)\cdot 5^{2}\cdot 31^{8}\) strings.

   5. We first choose for positions for the digits in \(C(10,4)\) ways. Since no digit can appear more than one time, we have \(P(10,4)=10\cdot 9\cdot 8\cdot 7\) ways to fill in the digits. For each of the remaining six positions, we have 26 choices. Thus, we have \(C(10,4) P(10,4) 26^{6}\) strings.

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.

   Avslöja svaret

   It makes sense to think about the choices by working from the most restrictive here. Since the last three positions are digits that cannot be repeated, we have \(P(10,3)\) ways to fill those positions. Of the remaining 17 positions, we must choose 3 of them to be vowels. There are \(\binom{17}{3}\) ways to make this choice. Once the positions for the vowels are chosen, we have five choices for each of those positions, for a total of \(5^{3}\) ways to fill in the vowels. We now have \(26+10 - 5 - 3= 28\) remaining symbols (the consonants and the unused digits) that can fill each of the remaining 14 positions. Therefore, the total number of record identifiers is \(P(10,3)\cdot \binom{17}{3}\cdot 5^{3} \cdot 28^{14}\).

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 \(V=\{a,e,i,o,u\}\) and these characters are all distinct.

    Avslöja svaret

    There are 10 choices for the initial digit and 9 choices for the distinct digit in the last position. Next we pick where to put the t, and we have \(C(13,4)\) ways to do this since we cannot put a t in the first or last position. We then pick three of the nine remaining positions for where to put letters from \(V\) in \(C(9,3)\) ways. Since the vowels used must be distinct, there are \(P(5,3) = 5\cdot 4\cdot 3\) ways to fill in those positions. We are now left with 20 letters and 10 digits (since we can reuse the digits from the first and last positions) to use in the remaining six positions. Therefore, the number of strings is \[\begin{aligned}\end{aligned}\].

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

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

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

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

    Avslöja svaret

    There are \(\binom{7}{4}\) ways to choose the men and \(\binom{11}{4}\) ways to choose the women. Since each selection of men can be combined with any of the selections of women, we must multiple and thus have \(\binom{7}{4}\cdot \binom{11}{4}\) possible korfball teams.

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.

    1. How many different outcomes are there for the top four places?

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

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

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

    Avslöja svaret

    1. Since the bowl is not symmetrical, the position of the scoops of ice cream matters, so there are \(P(20,3)=20\cdot 19\cdot 18\) ways to pick and place the ice cream. Since the sauces can be repeated (and where a sauce is placed matters), there are \(6^{3}\) ways to add sauce. The sprinkled toppings go over the entire banana split, so order is irrelevant. Thus, there are \(C(10,3)\) ways to choose the toppings. We must multiply to ensure all choices are made, so there are \(P(20,3)\cdot 6^{3}\cdot C(10,3)\) options for the banana split.

    2. Here all that changes from the answer to part a is our analysis of the sprinkled toppings. Now Xing can choose 0, 1, 2, or 3 sprinkled toppings, and there are \(C(10,0)\), \(C(10,1)\), \(C(10,2)\), \(C(10,3)\) ways to do these things, respectively. Since he must make a single choice of how to approach sprinkled toppings, the total way to choose sprinkled toppings is the sum of these values. We then replace \(C(10,3)\) in our original answer with this to get the answer to this part: \[\begin{aligned}\end{aligned}\].

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?

    Avslöja svaret

    We solve this by first counting where there is no upper bound restriction on Casper and then subtract the number of distributions in which he gets more than 5 pencils. Thus, we start by considering a situation where Casper could get 0 pencils, so we will need an artificial pencil for him. Se set aside three pencils for Barbara, so then she, Ahmed, and Dieter must each get at least one from the remaining. Thus, we have \(25 +1 -3 = 23\) pencils, which determine 22 gaps. We need 3 dividers, so the first part has \(C(22,3)\) distributions. Now, we consider how many ways there are for Casper to get more than 5 pencils. Here, we set aside \(5\) pencils for Casper (so he must get at least one more to have more than 5) and \(3\) pencils for Barbara. Thus, we have \(25-5-3 = 17\) pencils, which determine \(16\) gaps. As before, we need \(3\) dividers, so we have \(C(16,3)\) distributions in which Casper gets more than \(5\) pencils. Thus, the final solution is \[\begin{aligned}\end{aligned}\]

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

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

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

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

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

    5. \(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 \[\begin{aligned}\end{aligned}\] provided that \(x_1>0\), and \(x_2,x_3,x_4\geq 0\)? What if we add the restriction that \(x_4\lt 17\)?

    Avslöja svaret

    For the initially-presented problem, we can consider this as folder distribution with 132 folders. We need 3 artificial folders for \(x_{2},x_{3},x_{4}\). Thus, we have 135 folders, which determine 134 gaps. We need 3 dividers, so the answer is \(C(134,3)\). With the restriction that we need \(x_{4} \lt 17\), the most compact solution will be arrived at by taking our original solution and subtracting those where this inequality is false. That is, we subtract those that have \(x_{4}\geq 17\). Setting aside 17 folders for \(x_{4}\), we have 115 folders. We now could still allow \(x_{4}\) to get none of the remaining folders, so we need artificial folders for \(x_{2},x_{3},x_{4}\) as before. Thus, we distribute 118 folders, which determine 117 gaps. We need 3 dividers, so there are \(C(117,3)\) solutions we want to eliminate. Thus, the answer to the second question is \(C(134,3)-C(117,3)\).

18. How many integer solutions are there to the inequality \[\begin{aligned}\end{aligned}\] provided that \(x_1,x_2>0\), \(x_3\geq 0\), and \(x_4,x_5\geq 10\)?

    Avslöja svaret

    This is folder distribution with a keep pile that could be empty. We also need to do set-asides for \(x_{4},x_{5}\). To avoid needing artificial folders for these variables, we set aside 9 for each, meaning they must each get at least one from the remainder. Thus, we have \(782-9-9 = 764\) folders to distribute. However, we need an artificial folder to allow \(x_{3}\) to get none and another for the option of an empty keep pile. Thus, we count the ways to distribute \(766\) folders, which determine 765 gaps. Because of the keep pile, we need 5 dividers, so the solution is \(C(765,5)\).

19. Give a combinatorial argument to prove the identity \[\begin{aligned}\end{aligned}\]

    Avslöja svaret

    Hint:

    Think of choosing a team with a captain.

20. Let \(m\) and \(w\) be positive integers. Give a combinatorial argument to prove that for integers \(k\geq 0\), \[\begin{aligned}\end{aligned}\]

    Avslöja svaret

    Suppose we have \(m\) Minnesotans and \(w\) Wisconsinites and want to choose a committee of \(k\) people. Since there are \(m+w\) total people, the right-hand side counts the options straightforwardly. The left-hand side groups the committees based on the number \(j\) of Minnesotans on the committee. When there are \(j\) Minnesotans, there must be \(k-j\) Wisonsinites to get a total of \(k\) members. There are \(C(m,j)\) ways to choose the Minnesotans and \(C(w,k-j)\) ways to choose the Wisconsinites. Completely specifying a committee requires making both decisions, so we multiply these. We then sum over all the options for the number of Minnesotans on the committee and obtain the left-hand side.

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

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

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

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

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

    Avslöja svaret

    We count all the lattice paths from (0,0) to (14,73) and then subtract those through (6,37). Overall, there are \(14+73 = 87\) moves required and 14 of them must be H. Thus, the total number of lattice paths is \(C(87,14)\). When counting the lattice paths that go through (6,37), we need to count those from (0,0) to (6,37) and then count those from (6,37) to (14,73) and multiply these numbers to fully specify a lattice path. There are \(6+37 = 43\) moves, 6 of them H, in the first portion, so there are \(C(43,6)\) ways to do the first portion. There are \(14-6=8\) H's and \(73-37 = 36\) V's required for the second portion, for a total of 44 moves. Thus, there are \(C(44,8)\) ways to do the second portion. The final answer is therefore \(C(87,14)-C(43,6)C(44,8)\).

26. 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 \(1^\text{st}\) Street and \(1^\text{st}\) Avenue. He needs to return to his hideout at the intersection of \(7^\text{th}\) Street and \(5^\text{th}\) Avenue. However, one of his lookouts has reported that the town's one police officer is parked at the intersection of \(4^\text{th}\) Street and \(4^\text{th}\) 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.)

27. 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)?

    Avslöja svaret

    We can view this as a lattice path problem. Buzz's hive is at (0,0), Thundar's pen is at (6,7), Uga VIII is at (2,3), and the tigers are at (3,5). Thus, we need to count the lattice paths from (0,0) to (6,7) that avoid both (2,3) and (3,5). To do this, we need to subtract the lattice paths that go through (2,3) as well as those that go through (3,5). However, when we do this, we have subtracted the lattice paths that go through both (2,3) and (3,5) twice, so we must add those back. The components are:

    • All—13 moves, 6 H: \(C(13,6)\)

    • Through (2,3)—5 moves, 2 H in first portion and \(4+4 = 8\) moves, 4 H in second portion: \(C(5,2)C(8,4)\)

    • Through (3,5)—8 moves, 3 H in first portion and \(3+2 = 5\) moves, 3 H in second portion: \(C(8,3)C(5,3)\)

    • Through both (2,3) and (3,5)—5 moves, 2 H in first portion; 1+2 = 3 moves, 1 H in second portion; and \(3+2=5\) moves, 3 H in third portion: \(C(5,2)C(3,1)C(5,3)\)

    Therefore, the total is \[\begin{aligned}\end{aligned}\].

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

29. 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!)

    Avslöja svaret

    The multinomial theorem tells us that \[\begin{aligned}\end{aligned}\].

    Thus, we need \(12=3k_{1}+k_{2}\) and \(24 = 2k_{2}+k_{3}\) and all variables nonnegative. These equations imply that \(k_{3} = 6k_{1}\). Since the \(k_{i}\) must sum to \(18\), this means the only options for \(k_{1}\) are 0, 1, and 2. When \(k_{1} = 0\), we have \(k_{2} = 12\), \(k_{3} = 0\), and \(k_{4} = 6\). When \(k_{1} = 1\), we have \(k_{2} = 9\), \(k_{3} = 6\), and \(k_{4} = 2\). When \(k_{1} = 2\), we would need \(k_{3} = 12\) and \(k_{2} = 6\), but then the variables sum to more than \(18\). Thus, the coefficient on \(x^{12}y^{24}\) is \[\begin{aligned}\end{aligned}\].

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

    1. OVERNUMEROUSNESSES

    2. OPHTHALMOOTORHINOLARYNGOLOGY

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

31. 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\) are painted red?

32. What is \(0!\) defined to be?

33. Suppose we are making a (rather insecure) password of length \(8\). The first two characters will be uppercase letters, the third and fourth will be digits, and the last four characters can be any letter or digit. How many possible passwords are there?

34. Suppose we are making a password where the length can be either \(7\) or \(8\) characters. The first two characters will be uppercase letters, the third and fourth will be digits, and the remaining characters can be any letter or digit. How many possible passwords are there?

35. Suppose we are making a (rather insecure) password of length \(8\). The first four characters will be distinct uppercase letters. The next two characters will be digits. The last two characters will be distinct lowercase letters. How many possible passwords are there?

36. Suppose we had \(80\) candidates and needed to elect five co-chairs. If order mattered, there would be \(P(80,5)\) possible outcomes. Suppose we group them all based on which candidates were elected. Then each group would have how many outcomes in it?

37. We define \(\binom{n}{k}\) to be the number of ways to choose \(k\) elements from a set with \(n\) elements. Generalizing the ideas we have already discussed leads to which identity?

38. Which is larger, \(\binom{n}{k}\) or \(\binom{n}{n-k}\)?

39. A recurring theme in the reading from Section 2.4 was

40. How many dots if the grid is \(n\times n\)?

Prova själv

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mer information Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs