# sampling with replacement (choosing 6 items from a set of 4 elements)

I'm having trouble finding the number of $6$ ordered letter sequences from a $4$-set (i.e. $\{a, b, c, d\}$), that contain at least one of each different letter.

Should it be $4\times 4\times 4!$ because there are $4\times 4$ ways to choose the first two letters, and then the next $4$ are the permutations of the set, or something else? I have a feeling I'm missing something...

Thanks!

-
Hint: the only possibilities are one each of 3 letters and three copies of the fourth for a total of six letters, and one each of 2 letters and two each of the other 2 for a total of six letters. Count the cases separately, and remember that the order matters. –  Dilip Sarwate Sep 23 '12 at 21:51
Oh, nice! So C(6; 3,1,1,1) * 4 + C(4,2) * C(6; 2,2,1,1) would also solve the problem. Thanks! –  Kane Sep 24 '12 at 2:51
add comment

## 1 Answer

Use inclusion-exclusion. There are $4^6$ sequences altogether. For each of the $4$ letters there are $3^6$ sequences that don’t contain that letter, so subtract $4\cdot3^6$. Unfortunately, some sequences miss two letters, and we’ve subtracted each of these twice. There are $\binom42=6$ pairs of letters, and for each pair there are $2^6$ sequences that miss both letters, so we have to add back in $6\cdot2^6$. Finally, there are $4$ sequences that contain only one of the letters; we subtracted each of these three times and added them back in three times, so we need to subtract them one more time. The final result is

$$4^6-4\cdot3^6+6\cdot2^6-4=1560\;.$$

If you know the inclusion-exclusion formula, you can write this directly as

$$\sum_{k=0}^4(-1)^k\binom4k(4-k)^6\;.$$

-
add comment