Solution: 2019 Winter Final - 7

Author: Michiel Smid

Question

A string that is obtained by rearranging the letters of the word

POOPERSCOOPER

is called cool, if each occurrence of E has the letter R to its left or right, and each occurrence of R has the letter E to its left or right. Thus, both

POOPERSCOOPER

and

OPRECSOOOERPP

are cool, whereas

EPOOPRSCOOPER

is not cool. What is the number of cool strings?

(a)

${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 3$

(b)

${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 2$

(c)

${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1}$

(d)

${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 4$

Solution

Find stuff out

We can pair each E with an R and treat each as one entity

This leaves us with
- P: 3
- O: 4
- (ER): 2
- S: 1
- C: 1
Calculate

So now, POOP(ER)SCOOP(ER) has 11 entities/positions

Now, we need to figure out how many possible permutations of ER across the string there are
- ER____ER
- RE____ER
- ER____RE
- RE____RE
This is 4 permutations

We choose 3 of the 11 positions for P: $\binom{11}{3}$

We choose 4 of the remaining 8 positions for O: $\binom{8}{4}$

We choose 2 of the remaining 4 positions for ER: $\binom{4}{2}$

We choose 1 of the remaining 2 positions for S: $\binom{2}{1}$

We choose 1 of the remaining 1 positions for C: $\binom{1}{1}$

Now, we multiply all of these together to get the total number of cool strings:

$\binom{11}{3} \cdot \binom{8}{4} \cdot \binom{4}{2} \cdot \binom{2}{1} \cdot \binom{1}{1} \cdot 4$