2
$\begingroup$

Given the set $\{a,b,c,d\}$ how many 5 letter words can be formed such that each letter is used at least once?

I tried solving this using inclusion - exclusion but got a ridiculous result:

$4^5 - \binom{4}{1}\cdot 3^5 + \binom{4}{2}\cdot 2^5 - \binom{4}{3}\cdot 1^5 = 2341$

It seems that the correct answer is:

$\frac{5!}{2!}\cdot 4 = 240$

Specifically, the sum of the number of permutations of aabcd, abbcd, abccd and abcdd.

I'm not sure where my mistake was in the inclusion - exclusion approach. My universal set was all possible 5 letter words over a set of 4 letters, minus the number of ways to exclude one letter times the number of 5 letter words over a set of 3 letters, and so on.

Where's my mistake?

  • 0
    How did you get 2341? Perhaps if you show your working there we can point out the underlying mistake.2012-02-13

3 Answers 3

7

Your mistake is in the arithmetic. What you think comes out to 2341 really does come out to 240.

$4^5=1024$, $3^5=243$, $2^5=32$, $1024-(4)(243)+(6)(32)-4=1024-972+192-4=1216-976=240$

  • 0
    @RobertS.Barnes, take a look at Wilf's delicious "generationfunctionology" , it gives a formulation of the inclusion-exclusion principle using generating functions. As a bonus, instead of the traditional mess you get a _very_ simple relation that can be used to compute many results directly or derive the mess when required in a few lines.2013-02-03
2

I am writing this answer in case you also need to know about the second way: (Ignore if you know the details of the second method.)

Since you need to use each letter atleast once you really have choice only over one of the letters. This can be chosen in $4$ ways and they can be permuted in $\dfrac{5!}{2!}$ ways.

Hence the number of words, is, $\dfrac{5!}{2!} \cdot 4 =240$ words. $\blacksquare$

  • 0
    Could you employ this approach for - https://math.stackexchange.com/questions/2704480?2018-03-23
0

Another take on @Aryabhata's solution: If we have the set $\{a, a, b, c, d\}$, it can be permuted in $\binom{5}{2 \; 1 \; 1 \; 1}$ ways (multinomial coefficient, lower story records the numbers of repetitions of each symbol), and as the duplicated letter can be selected in 4 ways the result is: $ \binom{5}{2 \; 1 \; 1 \; 1} \cdot 4 = \frac{5!}{2! 1! 1! 1!} \cdot 4 = \frac{5!}{2!} \cdot 4 = 240 $

  • 0
    Could you employ this approach for - https://math.stackexchange.com/questions/2704480?2018-03-23