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?

$\endgroup$
1
  • $\begingroup$ How did you get 2341? Perhaps if you show your working there we can point out the underlying mistake. $\endgroup$
    – Aryabhata
    Commented Feb 13, 2012 at 12:24

3 Answers 3

Reset to default
7
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ Wow, duhhh... I probably hit $5^5$ on the calculator by accident... $\endgroup$
    – Robert S. Barnes
    Commented Feb 13, 2012 at 13:32
  • $\begingroup$ Could I solve this with generating functions also? $\endgroup$
    – Robert S. Barnes
    Commented Feb 13, 2012 at 18:35
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Feb 13, 2012 at 23:50
  • $\begingroup$ @RobertS.Barnes, take a look at Wilf's 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. $\endgroup$
    – vonbrand
    Commented Feb 3, 2013 at 2:58
2
$\begingroup$

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$

$\endgroup$
1
0
$\begingroup$

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

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .