11.S: Counting (Summary)

Investigate!

Suppose you have a huge box of animal crackers containing plenty of each of 10 different animals. For the counting questions below, carefully examine their similarities and differences, and then give an answer. The answers are all one of the following:

\(P(10,6)\qquad\)

\({10 \choose 6}\qquad\)

\(10^6\qquad\)

\({15 \choose 9}.\)

1. How many animal parades containing 6 crackers can you line up?
2. How many animal parades of 6 crackers can you line up so that the animals appear in alphabetical order?
3. How many ways could you line up 6 different animals in alphabetical order?
4. How many ways could you line up 6 different animals if they can come in any order?
5. How many ways could you give 6 children one animal cracker each?
6. How many ways could you give 6 children one animal cracker each so that no two kids get the same animal?
7. How many ways could you give out 6 giraffes to 10 kids?
8. Write a question about giving animal crackers to kids that has the answer \({10\choose 6}\text{.}\)

With all the different counting techniques we have mastered in this last chapter, it might be difficult to know when to apply which technique. Indeed, it is very easy to get mixed up and use the wrong counting method for a given problem. You get better with practice. As you practice you start to notice some trends that can help you distinguish between types of counting problems. Here are some suggestions that you might find helpful when deciding how to tackle a counting problem and checking whether your solution is correct.

• Remember that you are counting the number of items in some list of outcomes. Write down part of this list. Write down an element in the middle of the list – how are you deciding whether your element really is in the list. Could you get this element more than once using your proposed answer?
• If generating an element on the list involves selecting something (for example, picking a letter or picking a position to put a letter, etc), can the things you select be repeated? Remember, permutations and combinations select objects from a set without repeats.
• Does order matter? Be careful here and be sure you know what your answer really means. We usually say that order matters when you get different outcomes when the same objects are selected in different orders. Combinations and “Stars & Bars” are used when order does not matter.
• There are four possibilities when it comes to order and repeats. If order matters and repeats are allowed, the answer will look like \(n^k\text{.}\) If order matters and repeats are not allowed, we have \(P(n,k)\text{.}\) If order doesn't matter and repeats are allowed, use stars and bars. If order doesn't matter and repeats are not allowed, use \({n\choose k}\text{.}\) But be careful: this only applies when you are selecting things, and you should make sure you know exactly what you are selecting before determining which case you are in.
• Think about how you would represent your counting problem in terms of sets or functions. We know how to count different sorts of sets and different types of functions.
• As we saw with combinatorial proofs, you can often solve a counting problem in more than one way. Do that, and compare your numerical answers. If they don't match, something is amiss.

While we have covered many counting techniques, we have really only scratched the surface of the large subject of enumerative combinatorics. There are mathematicians doing original research in this area even as you read this. Counting can be really hard.

In the next chapter, we will approach counting questions from a very different direction, and in doing so, answer infinitely many counting questions at the same time. We will create sequences of answers to related questions.

Chapter Review

1

You have 9 presents to give to your 4 kids. How many ways can this be done if:

1. The presents are identical, and each kid gets at least one present?
2. The presents are identical, and some kids might get no presents?
3. The presents are unique, and some kids might get no presents?
4. The presents are unique and each kid gets at least one present?

Answer

1. \({8 \choose 3}\) ways, after giving one present to each kid, you are left with 5 presents (stars) which need to be divide among the 4 kids (giving 3 bars).
2. \({12 \choose 3}\) ways. You have 9 stars and 3 bars.
3. \(4^9\text{.}\) You have 4 choices for whom to give each present. This is like making a function from the set of presents to the set of kids.
4. \(4^9 - \left[{4 \choose 1}3^9 - {4\choose 2}2^9 + {4 \choose 3}1^9 \right]\) ways. Now the function from the set of presents to the set of kids must be surjective.

2

For each of the following counting problems, say whether the answer is \({10\choose 4}\text{,}\) \(P(10,4)\text{,}\) or neither. If you answer is “neither,” say what the answer should be instead.

1. How many shortest lattice paths are there from \((0,0)\) to \((10,4)\text{?}\)
2. If you have 10 bow ties, and you want to select 4 of them for next week, how many choices do you have?
3. Suppose you have 10 bow ties and you will wear one on each of the next 4 days. How many choices do you have?
4. If you want to wear 4 of your 10 bow ties next week (Monday through Sunday), how many ways can this be accomplished?
5. Out of a group of 10 classmates, how many ways can you rank your top 4 friends?
6. If 10 students come to their professor's office but only 4 can fit at a time, how different combinations of 4 students can see the prof first?
7. How many 4 letter words can be made from the first 10 letters of the alphabet?
8. How many ways can you make the word “cake” from the first 10 letters of the alphabet?
9. How many ways are there to distribute 10 apples among 4 children?
10. If you have 10 kids (and live in a shoe) and 4 types of cereal, how many ways can your kids eat breakfast?
11. How many ways can you arrange exactly 4 ones in a string of 10 binary digits?
12. You want to select 4 single digit numbers as your lotto picks. How many choices do you have?
13. 10 kids want ice-cream. You have 4 varieties. How many ways are there to give the kids as much ice-cream as they want?
14. How many 1-1 functions are there from \(\{1,2,\ldots, 10\}\) to \(\{a,b,c,d\}\text{?}\)
15. How many surjective functions are there from \(\{1,2,\ldots, 10\}\) to \(\{a,b,c,d\}\text{?}\)
16. Each of your 10 bow ties match 4 pairs of suspenders. How many outfits can you make?
17. After the party, the 10 kids each choose one of 4 party-favors. How many outcomes?
18. How many 6-elements subsets are there of the set \(\{1,2,\ldots, 10\}\)
19. How many ways can you split up 11 kids into 5 teams?
20. How many solutions are there to \(x_1 + x_2 + \cdots + x_5 = 6\) where each \(x_i\) is non-negative?
21. Your band goes on tour. There are 10 cities within driving distance, but only enough time to play 4 of them. How many choices do you have for the cities on your tour?
22. In how many different ways can you play the 4 cities you choose?
23. Out of the 10 breakfast cereals available, you want to have 4 bowls. How many ways can you do this?
24. There are 10 types of cookies available. You want to make a 4 cookie stack. How many different stacks can you make?
25. From your home at (0,0) you want to go to either the donut shop at (5,4) or the one at (3,6). How many paths could you take?
26. How many 10-digit numbers do not contain a sub-string of 4 repeated digits?

Answer

1. Neither. \({14 \choose 4}\) paths.
2. \({10\choose 4}\) bow ties. \(P(10,4)\text{,}\) since order is important.
3. Neither. Assuming you will wear each of the 4 ties on just 4 of the 7 days, without repeats: \({10\choose 4}P(7,4)\text{.}\)
4. \(P(10,4)\text{.}\) \({10\choose 4}\text{.}\)
5. Neither. Since you could repeat letters: \(10^4\text{.}\) If no repeats are allowed, it would be \(P(10,4)\text{.}\)
6. Neither. Actually, “k” is the 11th letter of the alphabet, so the answer is 0. If “k” was among the first 10 letters, there would only be 1 way - write it down.
7. Neither. Either \({9\choose 3}\) (if every kid gets an apple) or \({13 \choose 3}\) (if appleless kids are allowed).
8. Neither. Note that this could not be \({10 \choose 4}\) since the 10 things and 4 things are from different groups. \(4^{10}\text{.}\)
9. \({10 \choose 4}\) - don't be fooled by the “arrange” in there - you are picking 4 out of 10 spots to put the 1's. \({10 \choose 4}\) (assuming order is irrelevant).
10. Neither. \(16^{10}\) (each kid chooses yes or no to 4 varieties).
11. Neither. 0.
12. Neither. \(4^{10} - [{4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}]\text{.}\)
13. Neither. \(10\cdot 4\text{.}\)
14. Neither. \(4^{10}\text{.}\)
15. \({10 \choose 4}\) (which is the same as \({10 \choose 6}\)).
16. Neither. If all the kids were identical, and you wanted no empty teams, it would be \({10 \choose 4}\text{.}\) Instead, this will be the same as the number of surjective functions from a set of size 11 to a set of size 5.
17. \({10 \choose 4}\text{.}\) \({10 \choose 4}\text{.}\)
18. Neither. \(4!\text{.}\)
19. Neither. It's \({10 \choose 4}\) if you won't repeat any choices. If repetition is allowed, then this becomes \(x_1 + x_2 + \cdots +x_{10} = 4\text{,}\) which has \({13 \choose 9}\) solutions in non-negative integers.
20. Neither. Since repetition of cookie type is allowed, the answer is \(10^4\text{.}\) Without repetition, you would have \(P(10,4)\text{.}\)
21. \({10 \choose 4}\) since that is equal to \({9 \choose 4} + {9 \choose 3}\text{.}\)
22. Neither. It will be a complicated (possibly PIE) counting problem.

3

Recall, you own 3 regular ties and 5 bow ties. You realize that it would be okay to wear more than two ties to your clown college interview.

1. You must select some of your ties to wear. Everything is okay, from no ties up to all ties. How many choices do you have?
2. If you want to wear at least one regular tie and one bow tie, but are willing to wear up to all your ties, how many choices do you have for which ties to wear?
3. How many choices do you have if you wear exactly 2 of the 3 regular ties and 3 of the 5 bow ties?
4. Once you have selected 2 regular and 3 bow ties, in how many orders could you put the ties on, assuming you must have one of the three bow ties on top?

Answer

1. \(2^8 = 256\) choices. You have two choices for each tie: wear it or don't.
2. You have 7 choices for regular ties (the 8 choices less the “no regular tie” option) and 31 choices for bow ties (32 total minus the “no bow tie” option). Thus total you have \(7 \cdot 31 = 217\) choices.
3. \({3\choose 2}{5\choose 3} = 30\) choices.
4. Select one of the 3 bow ties to go on top. There are then 4 choices for the next tie, 3 for the tie after that, and so on. Thus \(3\cdot 4! = 72\) choices.

4

Give a counting question where the answer is \(8\cdot 3 \cdot 3 \cdot 5\text{.}\) Give another question where the answer is \(8 + 3 + 3 + 5\text{.}\)

Answer

You own 8 purple bow ties, 3 red bow ties, 3 blue bow ties and 5 green bow ties. How many ways can you select one of each color bow tie to take with you on a trip? \(8 \cdot 3 \cdot 3 \cdot 5\) ways. How many choices do you have for a single bow tie to wear tomorrow? \(8 + 3 + 3 + 5\) choices.

5

Consider five digit numbers \(\alpha = a_1a_2a_3a_4a_5\text{,}\) with each digit from the set \(\{1,2,3,4\}\text{.}\)

1. How many such numbers are there?
2. How many such numbers are there for which the sum of the digits is even?
3. How many such numbers contain more even digits than odd digits?

Answer

1. \(4^5\) numbers.
2. \(4^4\cdot 2\) numbers (choose any digits for the first four digits - then pick either an even or an odd last digit to make the sum even).
3. We need 3 or more even digits. 3 even digits: \({5 \choose 3}2^3 2^2\text{.}\) 4 even digits: \({5 \choose 4}2^4 2\text{.}\) 5 even digits: \({5 \choose 5}2^5\text{.}\) So all together: \({5 \choose 3}2^3 2^2 + {5 \choose 4}2^4 2 + {5 \choose 5}2^5\) numbers.

6

In a recent small survey of airline passengers, 25 said they had flown American in the last year, 30 had flown Jet Blue, and 20 had flown Continental. Of those, 10 reported they had flown on American and Jet Blue, 12 had flown on Jet Blue and Continental, and 7 had flown on American and Continental. 5 passengers had flown on all three airlines.

How many passengers were surveyed? (Assume the results above make up the entire survey.)

Answer

51 passengers.

7

Recall, by \(8\)-bit strings, we mean strings of binary digits, of length 8.

1. How many \(8\)-bit strings are there total?
2. How many \(8\)-bit strings have weight 5?
3. How many subsets of the set \(\{a,b,c,d,e,f,g,h\}\) contain exactly 5 elements?
4. Explain why your answers to parts (b) and (c) are the same. Why are these questions equivalent?

Answer

1. \(2^8\) strings.
2. \({8 \choose 5}\) strings.
3. \({8 \choose 5}\) strings.
4. There is a bijection between subsets and bit strings: a 1 means that element in is the subset, a 0 means that element is not in the subset. To get a subset of an 8 element set we have a 8-bit string. To make sure the subset contains exactly 5 elements, there must be 5 1's, so the weight must be 5.

8

What is the coefficient of \(x^{10}\) in the expansion of \((x+1)^{13} + x^2(x+1)^{17}\text{?}\)

Answer

\({13 \choose 10} + {17 \choose 8}\text{.}\)

9

How many 8-letter words contain exactly 5 vowels (a,e,i,o,u)? What if repeated letters were not allowed?

Answer

With repeated letters allowed: \({8 \choose 5}5^5 21^3\) words. Without repeats: \({8 \choose 5}5! P(21, 3)\) words.

10

For each of the following, find the number of shortest lattice paths from \((0,0)\) to \((8,8)\) which:

1. pass through the point \((2,3)\text{.}\)
2. avoid (do not pass through) the point \((7,5)\text{.}\)
3. either pass through \((2,3)\) or \((5,7)\) (or both).

Answer

1. \({5 \choose 2}{11 \choose 6}\) paths.
2. \({16 \choose 8} - {12 \choose 7}{4 \choose 1}\) paths.
3. \({5 \choose 2}{11 \choose 6} + {12 \choose 5}{4 \choose 3} - {5 \choose 2}{7 \choose 3}{4 \choose 3}\) paths.

11

You live in Grid-Town on the corner of 2nd and 3rd, and work in a building on the corner of 10th and 13th. How many routes are there which take you from home to work and then back home, but by a different route?

Answer

\({18 \choose 8}\left({18 \choose 8} - 1\right)\) routes.

12

How many 10-bit strings start with \(111\) or end with \(101\) or both?

Answer

\(2^7 + 2^7 - 2^4\) strings (using PIE).

13

How many 10-bit strings of weight 6 start with \(111\) or end with \(101\) or both?

Answer

\({7 \choose 3} + {7 \choose 4} - {4 \choose 1}\) strings.

14

How many 6 letter words made from the letters \(a,b,c,d,e,f\) without repeats do not contain the sub-word “bad” in (a) consecutive letters? or (b) not-necessarily consecutive letters (but in order)?

Answer

(a) \(6! - 4\cdot 3!\) words. (b) \(6! - {6 \choose 3}3!\) words.

15

Explain using lattice paths why \(\sum_{k=0}^n {n \choose k} = 2^n\text{.}\)

Answer

\(2^n\) is the number of lattice paths which have length \(n\text{,}\) since for each step you can go up or right. Such a path would end along the line \(x + y = n\text{.}\) So you will end at \((0,n)\text{,}\) or \((1,n-1)\) or \((2, n-2)\) or … or \((n,0)\text{.}\) Counting the paths to each of these points separately, give \({n \choose 0}\text{,}\) \({n \choose 1}\text{,}\) \({n \choose 2}\text{,}\) …, \({n \choose n}\) (each time choosing which of the \(n\) steps to be to the right). These two methods count the same quantity, so are equal.

16

Suppose you have 20 one-dollar bills to give out as prizes to your top 5 discrete math students. How many ways can you do this if:

1. Each of the 5 students gets at least 1 dollar?
2. Some students might get nothing?
3. Each student gets at least 1 dollar but no more than 7 dollars?

Hint

Stars and bars.

Answer

1. \({19 \choose 4}\) ways.
2. \({24 \choose 4}\) ways.
3. \({19 \choose 4} - \left[{5 \choose 1}{12 \choose 4} - {5 \choose 2}{5 \choose 4} \right]\) ways.

17

How many functions \(f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}\) are there satisfying:

1. \(f(1) = a\) or \(f(2) = b\) (or both)?
2. \(f(1) \ne a\) or \(f(2) \ne b\) (or both)?
3. \(f(1) \ne a\) and \(f(2) \ne b\text{,}\) and \(f\) is injective?
4. \(f\) is surjective, but \(f(1) \ne a\text{,}\) \(f(2) \ne b\text{,}\) \(f(3) \ne c\text{,}\) \(f(4) \ne d\) and \(f(5) \ne e\text{?}\)

Answer

1. \(5^4 + 5^4 - 5^3\) functions.
2. \(4\cdot 5^4 + 5 \cdot 4 \cdot 5^3 - 4 \cdot 4 \cdot 5^3\) functions.
3. \(5! - \left[ 4! + 4! - 3! \right]\) functions. Note we use factorials instead of powers because we are looking for injective functions.
4. Note that being surjective here is the same as being injective, so we can start with all \(5!\) injective functions and subtract those which have one or more “fixed point”. We get \(5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5} 0!\right]\) functions.

18

How many functions map \(\{1,2,3,4,5,6\}\) onto \(\{a,b,c,d\}\) (i.e., how many surjections are there)?

Answer

\(4^6 - \left[{4 \choose 1}3^6 - {4 \choose 2}2^6 + {4 \choose 3} 1^6 \right]\text{.}\)

19

To thank your math professor for doing such an amazing job all semester, you decide to bake Oscar cookies. You know how to make 10 different types of cookies.

1. If you want to give your professor 4 different types of cookies, how many different combinations of cookie type can you select? Explain your answer.
2. To keep things interesting, you decide to make a different number of each type of cookie. If again you want to select 4 cookie types, how many ways can you select the cookie types and decide for which there will be the most, second most, etc. Explain your answer.
3. You change your mind again. This time you decide you will make a total of 12 cookies. Each cookie could be any one of the 10 types of cookies you know how to bake (and it's okay if you leave some types out). How many choices do you have? Explain.
4. You realize that the previous plan did not account for presentation. This time, you once again want to make 12 cookies, each one could be any one of the 10 types of cookies. However, now you plan to shape the cookies into the numerals 1, 2, …, 12 (and probably arrange them to make a giant clock, but you haven't decided on that yet). How many choices do you have for which types of cookies to bake into which numerals? Explain.
5. The only flaw with the last plan is that your professor might not get to sample all 10 different varieties of cookies. How many choices do you have for which types of cookies to make into which numerals, given that each type of cookie should be present at least once? Explain.

Answer

1. \({10 \choose 4}\) combinations. You need to choose 4 of the 10 cookie types. Order doesn't matter.
2. \(P(10, 4) = 10 \cdot 9 \cdot 8 \cdot 7\) ways. You are choosing and arranging 4 out of 10 cookies. Order matters now.
3. \({21 \choose 9}\) choices. You must switch between cookie type 9 times as you make your 12 cookies. The cookies are the stars, the switches between cookie types are the bars.
4. \(10^{12}\) choices. You have 10 choices for the “1” cookie, 10 choices for the “2” cookie, and so on.
5. \(10^{12} - \left[{10 \choose 1}9^{12} - {10 \choose 2}8^{12} + \cdots - {10 \choose 10}0^{12} \right]\) choices. We must use PIE to remove all the ways in which one or more cookie type is not selected.

20

For which of the parts of the previous problem (Exercise 1.7.19) does it make sense to interpret the counting question as counting some number of functions? Say what the domain and codomain should be, and whether you are counting all functions, injections, surjections, or something else.

Answer

1. You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We could say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn't matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types).
2. We want to consider injective functions from the set \(\{\)most, second most, second least, least\(\}\) to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example).
3. This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.).
4. The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here.
5. Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part.