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:
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.
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.
How many shortest lattice paths are there from \((0,0)\) to \((10,4)\text{?}\)
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?
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?
Consider numbers of the form \(\alpha = a_1a_2a_3\dots a_n\text{,}\) with \(n\) digits, each digit from the set \({\left\{1,2,3,4,5,6,7,8\right\}}\text{.}\) For example, if \(n = 4\text{,}\) the number \(\alpha = a_1a_2a_3a_4\) will have 4 digits from the set \({\left\{1,2,3,4,5,6,7,8\right\}}\text{.}\)
In a recent small survey of airline passengers, 30 said they had flown American in the last year, 20 had flown Jet Blue, and 24 had flown Continental. Of those, 11 reported they had flown on American and Jet Blue, 14 had flown on Jet Blue and Continental, and 12 had flown on American and Continental. 9 passengers had flown on all three airlines.
How many 9-letter words contain exactly 3 vowels? (For example, an 8-letter word with 5 vowels is “aaioobtt”; don’t consider “y” a vowel for this exercise.)
You live in Grid-Town on the corner of 2nd and 4th, and work in a building on the corner of 16th and 17th. How many routes are there which take you from home to work and then back home, but by a different route?
We are making 11-letter words from the set of letters \(a,b,c,d,e,f \dots\text{,}\) in such a way that we have exactly the first 11 letters available so that we use all letters.
How many 11-letter words can we make from the letters without repeats that do not contain the sub-word “bad” in consecutive letters?
To thank your math professor for doing such an amazing job all semester, you decide to bake your professor cookies. You know how to make 12 different types of cookies.
If you want to give your professor 7 different types of cookies, how many different combinations of cookie type can you select? Explain your answer.
To keep things interesting, you decide to make a different number of each type of cookie. If again you want to select 7 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.
You change your mind again. This time you decide you will make a total of 20 cookies. Each cookie could be any one of the 12 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.
You realize that the previous plan did not account for presentation. This time, you once again want to make 20 cookies, each one could be any one of the 12 types of cookies. However, now you plan to shape the cookies into the numerals 1, 2, ..., 20. How many choices do you have for which types of cookies to bake into which numerals? Explain.
The only flaw with the last plan is that your professor might not get to sample all 12 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.
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.
