  ## Exercises - Counting

1. If you have 2 pairs of shoes, 3 pants, and 5 t-shirts, how many different outfits can you make?

Fundamental Counting Principle.

There are $2 \times 3 \times 5 = 30$ such outfits.

2. How many ways can you answer a 5-question True/False test?

Fundamental Counting Principle.

There are two choices for each question, so $2 \times 2 \times 2 \times 2 \times 2 = 32$ ways are possible.

3. A true/false test has 10 items. How many different answer keys are possible?

Fundamental Counting Theorem, $2^{10} = 1024$.
4. A multiple choice test has 20 items. Each item has 3 choices. How many distinctly different answer keys are possible?

$3^{20} = 3,486,784,401$.
5. How many 5-digit numbers are divisible by 5? (Note: the presence of "leading zeros" does not count towards the number of digits. So for example, 01234 is a 4-digit number. Also, you may use a digit more than once.)

Fundamental Counting Principle.

There are $9$ choices for the first digit (which can't be zero), $2$ choices for the last digit (which must be $0$ or $5$) and $10$ choices for each of the remaining digits (since they can be anything). So, there are $9 \times 10 \times 10 \times 10 \times 2$ possible such numbers.

6. How many 4-digit odd numbers are there, if repeated digits are allowed? What if there are no repeated digits?

Fundamental Counting Principle.

Repeated digits allowed: There are $9$ possibilities for the first digit (since it can't be zero), $10$ possibilities for the second and third digits (since they can be anything), and $5$ possibilities for the last digit (since it must be odd). Thus there are $9 \times 10 \times 10 \times 5 = 4500$ such numbers.

Repeated digits not allowed: Pick the last digit first, then the first, then the other two to limit the number of cases that must be considered. There are $5$ choices for the last digit (since it must be odd), $8$ choices for the first digit (since it must not be zero or the last [non-zero] digit), $8$ choices for the second digit (since it must not equal the first or last digit), and $7$ choices for the third digit (since it must not equal the first, second, or last digits). Thus, there are $8 \times 8 \times 7 \times 5 = 2240$ such numbers.

7. How many different 5-digit odd numbers are possible if a digit may not be repeated?

Fundamental Counting Theorem. The number must end in an odd digit, there are 5 of these $\{1, 3, 5, 7, 9\}$. The first digit cannot be a repeat of the last digit and cannot be $0$, giving $8$ possibilities for the first digit (the $4$ odd digits not used as the last digit and the $4$ non-zero even digits). After determining how many are available for the first and last digit, there are $8$ remaining digits ($0$ can now be used) for the second digit, $7$ for the third digit, and $6$ for the fourth digit. $8 \times 8 \times 7 \times 6 \times 5 = 13,440$.

8. How many different 5-digit odd numbers are possible if digits may be repeated?

Fundamental Counting Theorem, $9 \times 10 \times 10 \times 10 \times 5 = 45,000$.

9. How many 4-digit even numbers are there if the digits may not be repeated?

Fundamental Counting Theorem. The last number must be an even digit. There are five of these $\{0, 2, 4, 6, 8\}$. The first number cannot be 0 or one of the other four at the end of the number. For the middle two digits, there are 8 and 7 possibiilities respectively. If zero ends the number: $9 \times 8 \times 7 \times 1$. If one of the four possibilities $\{2, 4, 6, 8\}$ ends the number, then the first digit cannot be the same as the last or be zero: $8 \times 8 \times 7 \times 4$. Add these together: $504 + 1792 = 2296$.

10. (a) How many four-digit odd numbers are less than 5000? (Digits may be repeated.); (b) How many three-digit even numbers, larger than 399, are there if the digits may be repeated?

Fundamental Counting Theorem. (a) $4 \times 10 \times 10 \times 5 = 2000$; (b) The first digit must be selected frome the set $\{4, 5, 6, 7, 8, 9\}$, there are six possibilities. The last digit must be an even digit, selected from the set $\{0, 2, 4, 6, 8\}$. The middle digit can be any of the 10 available digits. $6 \times 10 \times 5 = 300$.
11. How many ways can you arrange 5 people in a row for a photograph?

$5! = 120$
12. How many ways can you arrange 4 different pictures in a row on a wall?

Fundamental Counting Principle. $4 \times 3 \times 2 \times 1 = 24$ (i.e., $4!$).
13. King Art is sitting at his round table (at the head, of course). His seven knights are sitting around him. How many ways can his knights be arranged?

Relative to King Art, there are $7! = 5040$ ways.

R: factorial(7)

Excel: FACT(7)

14. How many ways can you arrange 4 chemistry books, 3 math books, and 2 physics books on a shelf? What if you want to keep books of the same subject together? (Assume books on the same subject look identical.)

$$\frac{9!}{4! \cdot 3! \cdot 2!} \textrm{ ways if one doesn't need same subject books together}$$
R
> counts = c(4,3,2)
> factorial(sum(counts))/prod(factorial(counts))

Excel
=FACT(9)/(FACT(4)*FACT(3)*FACT(2))

$$3! = 6 \textrm{ ways if same subject books are together}$$
15. How many ways can you arrange 4 pictures in a row on a wall if you have 7 pictures to choose from?

Use Fundamental Counting Principle or permutations: $7 \times 6 \times 5 \times 4 = {}_7 P_4 = 840$ ways

R
> factorial(4)*choose(7,4)

Excel
=PERMUT(7,4)

16. A question on a history quiz requires that 6 events be arranged in the proper chronological order. How many arrangements are possible?

Permutation, 720
R: factorial(6)

Excel: FACT(6)

17. How many ways can we award 1st, 2nd, and 3rd place in an 8-person race?

Fundamental Counting Principle. $8 \times 7 \times 6 = 336$ ways
18. How many ways can you arrange the letters in the word MISSISSIPPI?

Permutations of indistinguishable objects. There are $4$ I's, $4$ S's, $2$ P's, in $11$ letters, so there are $$\frac{11!}{4! \cdot 4! \cdot 2!} = 34650 \textrm{ ways}$$

R
> counts = c(4,4,2,1)
> factorial(sum(counts))/prod(factorial(counts))

Excel
FACT(11)/(FACT(4)*FACT(4)*FACT(2))

19. How many different arrangements are possible in the word BOOKKEEPER?

151,200, permutation of indistinguishable objects

R
> counts = c(1,2,2,3,1,1)
> factorial(sum(counts))/prod(factorial(counts))

EXCEL
=FACT(10)/(FACT(2)*FACT(2)*FACT(3))

20. How many ways can you arrange the letters of the word STATISTICS?

Permutations of indistinguishable objects. There are $3$ S's, $3$ T's, $2$ I's, in $10$ letters, so there are $$\frac{10!}{3! \cdot 3! \cdot 2!} = 50400 \textrm{ ways}$$

R
> counts = c(3,3,1,2,1)
> factorial(sum(counts))/prod(factorial(counts))

EXCEL
=FACT(10)/(FACT(3)*FACT(3)*FACT(2))

21. How many different arrangements are there of the letters in the following words:

1. LETTERED
2. LEVELED
3. COVINGTON

1. $\displaystyle{\frac{8!}{3! \cdot 2!} = 3360}$

2. $\displaystyle{\frac{7!}{2! \cdot 3!} = 420}$

3. $\displaystyle{\frac{9!}{2! \cdot 2!} = 90720}$

22. How many different orderings of letters can be made from the following: AAABBBBCCCCCDDDDD ?

Permutation of indistinguishable objects, 171531360.
R
> counts = c(3,4,5,5)
> factorial(sum(counts))/prod(factorial(counts))

Excel
=FACT(17)/(FACT(3)*FACT(4)*FACT(5)*FACT(5))

23. How many ways can you arrange 4 pennies and 4 nickels in a row?

Permutations of indistinguishable objects. There are $4$ pennies, $4$ nickels, in a row of $8$ coins, so there are $$\frac{8!}{4! \cdot 4!} = 70\textrm{ ways}$$

You can also solve this with combinations. Count how many ways we can choose 4 of 8 positions to be the pennies.

R
> choose(8,4)

Excel
=COMBIN(8,4)

24. A club has 20 members. How many ways can we choose a 4-person committee?

Combinations. There are ${}_{20} C_4 = 4845$ ways.

R
> choose(20,4)

Excel
=COMBIN(20,4)

25. How many different subcommittees of 4 can be formed from a club of 24 members?

Combination: 10,626

R
> choose(24,4)

Excel
=COMBIN(24,4)

26. A club has 20 members. How many ways can we choose a president, a vice-president, a secretary, and 4 senators?

Choose the president ($20$ choices), then the vice-president ($19$ choices), then the secretary ($18$ choices), then the $4$ senators (${}_{17} C_4$ choices). So there are

$$20 \cdot 19 \cdot 18 \cdot {}_{17} C_4 = 16,279,200 \textrm{ ways}$$
R
> 20*19*18*choose(17,4)

Excel
=20*19*18*COMBIN(17,4)

27. A 4-member micro team must be selected from a group of 10 soccer players. How many different micro teams are possible?

Combination: 210

R
> choose(10,4)

Excel
=COMBIN(10,4)

28. How many different groupings of 6 females are possible from an applicant pool of 20?

Combination: 38,760

R
> choose(20,6)

Excel
=COMBIN(20,6)

29. A club has 12 freshmen and 8 sophomores.

1. How many ways can we choose a 4-person committee of 2 freshmen and 2 sophomores?
2. How many ways can we choose a 4-person committee with at least 2 freshmen?

1. $\displaystyle{({}_{12}C_2)({}_8C_2) = 1848}$

2. $\displaystyle{({}_{12}C_2)({}_8C_2) + ({}_{12}C_3)({}_8C_1) + ({}_{12}C_4)({}_8C_0) = 4103}$

30. A bagel store offers 4 kinds of bagels, plain, poppyseed, sesame, and onion. One way to buy a dozen bagels might be to get 2 plain, 3 poppyseed, 5 sesame, and 2 onion bagels. Another might be to get all plain bagels. Still another would be to get 4 poppyseed and 8 onion bagels. In how many ways can one buy a dozen bagels? (Note the order in which the bagels are purchased is not important -- it only matters how many bagels of each kind are in your order.)

The answer is $\displaystyle{{}_{15}C_{3} = 455 \textrm{ ways}}$, although this may not be obvious. To see a clever way to solve this problem, watch this video!

31. A jar contains a number of red, blue, and white balls. Assuming balls of the same color are indistinguishable and order matters, how many different sequences can occur if someone draws...

1. 3 balls and gets one of each color?
2. 5 balls and gets 3 red and 2 blue?
3. 5 balls and gets exactly 3 red balls?
4. 2 balls, both of the same color?

1. $3 \cdot 2 \cdot 1 = 6$

2. ${}_5C_3 = 10$

3. $({}_5C_3) \cdot 2^2 = 40$

4. $1 + 1 + 1 = 3$

32. How many ways can one arrange $n$ different people in a line? Recall, the formula for the number of permutations of $n$ things taken $k$ at a time is $${}_n P_k = \frac{n!}{(n-k)!}$$ If you were to use this formula to answer the previous question, what would $k$ be? What does this suggest $0!$ should be defined to be?

By the fundamental counting principle, there are $n$ choices for the first person, $(n-1)$ for the second, $(n-2)$ for the third, and so on.. until there is only one choice for the last person. Thus there are $n(n-1)(n-2) \cdots 1 = n!$ ways to arrange $n$ people in a line.

To solve the same problem using the permutation formula, note that we would take $k = n$ as we are arranging all $n$ people.

This means that $$n! = {}_n P_n = \frac{n!}{(n-n)!} = \frac{n!}{0!}$$ suggesting that we should define $0! = 1$ to ensure that the equality still holds and everything is consistent.

The video below suggests some other reasons why we might make this definition:

33. Opening a lock on a locker requires one to spin a dial to 3 different numbers in a particular sequence, where each number is between $0$ and $39$, inclusive. How many different locker "combinations" are there? Is the term "locker combination" appropriate? Why or why not?

Notice there are $40$ possible numbers and order matters. Thus, the number of locker combinations is given by ${}_{40} P_3 = 59,280$.

Obviously, "locker combinations" would probably be better referred to as "locker permutations", given the calculation just used.

R
> factorial(3)*choose(40,3)

Excel
=PERMUT(40,3)

34. To unlock an iPhone requires the entry of a 4-digit pin number (with each digit among $0$ to $9$). How many possible pins are there?

$10^4$
35. In horse racing, a Quinella bet is one where the bettor will choose two horses in a race, and these horses must come in first and second place (although the order they place in does not matter) to win the bet. An Exacta bet is identical to a Quinella bet - except that one is now betting the horses also place in a particular order. If $19$ horses run in the race, in how many more ways can an Exacta bet be made as compared to a Quinella bet?

There are ${}_{19} P_2 = 342$ ways to make an Exacta bet, while there are only ${}_{19} C_2 = 171$ ways to make a Quinella bet. Thus, there are $171$ more ways to make an Exacta bet.
36. The Georgia Council of Teachers of Mathematics (GCTM) needs to select a new conference coordinator, program chair, and director of facilities, for the board that oversees its annual conference. It also needs to fill 4 vacancies in its group of regional representatives. If there are 10 qualified people available and a person can serve as a regional representative and also serve on the conference board at the same time but no other instances of a person serving in two capacities is allowed, in how many ways can these positions be filled?

There are ${}_{10} P_3$ ways the conference board positions can be filled. Given that a person can serve as a regional representative and on the conference board at the same time, there are still $10$ people to choose from to fill the regional representative positions. Thus, there are ${}_{10} C_4$ ways to select the regional representatives. By the fundamental counting principle, there are $({}_{10} P_3)({}_{10} C_4) = 720 \cdot 210 = 151200$ ways to fill all of these positions.

R
> factorial(3)*choose(10,3)*choose(10,4)

Excel
=PERMUT(10,3)*COMBIN(10,4)

37. Quite appropriately, the word hippopotomonstrosesquipedalianism is used to describe words that are enormously long. In how many ways can its letters be arranged?

In the $33$ letters of the word:

• there are 5 occurrences of o
• p, i and s both occur 4 times each, and
• t, m, n, e, and a all occur 2 times each

resulting in $\displaystyle{\frac{33!}{5! (4!)^3 2^5}}$ possible ways to arrange the letters.

For the curious, the above expression evaluates to $163576434454494269015808000000$.

R
> counts = c(1,4,4,5,2,2,2,4,1,2,1,1,1,2,1)
#  h i p o t m n s r e q u d a l
> factorial(sum(counts))/prod(factorial(counts))