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.

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?

share|improve this question
    
How did you get 2341? Perhaps if you show your working there we can point out the underlying mistake. –  Aryabhata Feb 13 '12 at 12:24

3 Answers 3

up vote 7 down vote accepted

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$

share|improve this answer
    
Wow, duhhh... I probably hit $5^5$ on the calculator by accident... –  Robert S. Barnes Feb 13 '12 at 13:32
    
Could I solve this with generating functions also? –  Robert S. Barnes Feb 13 '12 at 18:35
    
I don't know. You could let $a_n$ be the number of $n$-letter words on an $(n-1)$-letter alphabet using each letter exactly once, try to find a recurrence satisfied by the sequence $a_n$, and then try to solve that recurrence by generating functions. More generally, the problems is a special case of finding the number of onto maps from an $n$-element set to a $k$-element set. The answer to that question can be expressed in terms of Stirling numbers of the second kind. There is a lot of information out there for those numbers, possibly including generating functions. –  Gerry Myerson Feb 13 '12 at 23:50
    
@RobertS.Barnes, take a look at Wiles' delicious "generationfunctionology" <math.upenn.edu/~wilf/DownldGF.html>;, 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. –  vonbrand Feb 3 '13 at 2:58
    
@vonbrand, Wilf \ne Wiles. –  Gerry Myerson Feb 3 '13 at 9:34

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$

share|improve this answer
    
@Aryabhata I am banging myself on the wall quite vigorously. Thank You for the edit :) –  user21436 Feb 13 '12 at 12:25
    
You are welcome :-) –  Aryabhata Feb 13 '12 at 12:27

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 $$

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.