How many different combinations of 3 ingredients that are chosen from 4 choices.

A pizza parlor offers 10 toppings.

1. How many 3-topping pizzas could they put on their menu? Assume double toppings are not allowed.

2. How many total pizzas are possible, with between zero and ten toppings (but not double toppings) allowed?

3. The pizza parlor will list the 10 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?

Solution

1. \({10 \choose 3} = 120\) pizzas. We must choose (in no particular order) 3 out of the 10 toppings.
2. \(2^{10} = 1024\) pizzas. Say yes or no to each topping.
3. \(P(10,5) = 30240\) ways. Assign each of the 5 spots in the left column to a unique pizza topping.

A combination lock consists of a dial with 40 numbers on it. To open the lock, you turn the dial to the right until you reach a first number, then to the left until you get to second number, then to the right again to the third number. The numbers must be distinct. How many different combinations are possible?

Solution

Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \(P(40,3) = 40\cdot 39 \cdot 38\) different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(40^3\)).

An anagram of a word is just a rearrangement of its letters. How many different anagrams of “uncopyrightable” are there? (This happens to be the longest common English word without any repeated letters.)

How many anagrams are there of the word “assesses” that start with the letter “a”?

Solution

After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \({7 \choose 2} = 21\) anagrams starting with “a”.

How many anagrams are there of “anagram”?

On a business retreat, your company of 20 businessmen and businesswomen go golfing.

1. You need to divide up into foursomes (groups of 4 people): a first foursome, a second foursome, and so on. How many ways can you do this?

2. After all your hard work, you realize that in fact, you want each foursome to include one of the five Board members. How many ways can you do this?

Solution

1. \({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\) ways. Pick 4 out of 20 people to be in the first foursome, then 4 of the remaining 16 for the second foursome, and so on (use the multiplicative principle to combine).
2. \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\) ways. First determine the tee time of the 5 board members, then select 3 of the 15 non board members to golf with the first board member, then 3 of the remaining 12 to golf with the second, and so on.

Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 17\text{.}\)

1. How many functions \(f: A \to B\) are there?

2. How many functions \(f: A \to B\) are injective?

Solution

1. \(17^{10}\) functions. There are 17 choices for the image of each element in the domain.
2. \(P(17, 10)\) injective functions. There are 17 choices for image of the first element of the domain, then only 16 choices for the second, and so on.