1
$\begingroup$

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!

  • 0
    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!2012-09-24

1 Answers 1

3

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\;.$