Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.