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.

This is similar to my previous question, Number of 5 letter words over a 4 letter group using each letter at least once.

The only difference is that there are 3 letters to choose from instead of 4.

However, I've run into a problem.

Using inclusion exclusion I get:

$3^5 - 3 \cdot 2^5 + 3 \cdot 1^5 = 150$

Which is the correct answer.

But trying to solve it directly by counting the permutations of the strings $abccc$, $abbbc$ and $aaabc$ gives:

$3 \cdot \frac{5!}{3!}=60$

What am I missing in the combinatorial approach?

Also, could I solve this using generating functions?

So this is really two questions - bonus points for answering both :-)

share|improve this question

1 Answer 1

up vote 4 down vote accepted

You forgot that you can have strings with two copies of one letter, two of another, and one of the third. There are $3$ ways to choose which of the letters is used only once, and $5$ ways to place it in the string. There are then $\binom42=6$ ways to choose which two of the remaining four places get the two copies of the first of the other two letters in alphabetical order, for a total of $3\cdot 5\cdot 6=90$ strings, exactly the number that you’re missing.

Added: To do it with generating functions, let $a_n$ be the number of words of length $n$ over a $3$-letter alphabet that use each letter at least once. The first step is to find a recurrence for $a_n$. For brevity call such words good. Each good word of length $n-1$ can be extended to a good word of length $n$ in $3$ different ways, since each of the three letters can be added at the end of the word. In addition, each $(n-1)$-letter word that contains exactly two of the three letters can be extended to a good word in one way, by adding the missing letter. How many of these $(n-1)$-letter words are there? There are $3$ ways to choose which of the three letters is missing, and each of the $n-1$ positions in the word can contain either of the two remaining letters. However, we have to exclude the two possibilities that contain only one of the two letters, so there are $3(2^{n-1}-2)$ such words. This leads us to the recurrence

$$a_n=3a_{n-1}+3(2^{n-1}-2)\tag{1}\;.$$

Clearly $a_0=a_1=a_2=0$ and $a_3=3!=6$. However, if we assume that $a_n=0$ for $n<0$, $(1)$ requires a small adjustment to get $a_0$ and $a_1$ right: as it stands, it yields the values $-9/2$ and $-3$. To correct this, we add a couple of Iverson brackets to get

$$a_n=3a_{n-1}+3(2^{n-1}-2)+\frac92[n=0]+3[n=1]\tag{2}\;.$$

Now multiply through by $x^n$ and sum over $n$ to get the generating function $f(x)$:

$$\begin{align*}f(x)=\sum_na_nx^n&=3\sum_n\left(a_{n-1}+2^{n-1}-2+\frac32[n=0]+[n=1]\right)x^n\\ &=3\left(\sum_na_{n-1}x^n+\sum_n2^{n-1}x^n-2\sum_nx^n+\frac32+x\right)\\ &=3\left(x\sum_na_{n-1}x^{n-1}+\frac12\sum_n(2x)^n-\frac2{1-x}+\frac32+x\right)\\ &=3\left(x\sum_na_nx_n+\frac{1/2}{1-2x}-\frac2{1-x}+\frac32+x\right)\\ &=3xf(x)+\frac32\left(\frac{7x-3}{(1-x)(1-2x)}+2x+3\right)\\ &=3xf(x)+\frac{6x^3}{(1-x)(1-2x)}\;, \end{align*}$$

so $$(1-3x)f(x)=\frac{6x^3}{(1-x)(1-2x)}\;,$$ and

$$\begin{align*} f(x)&=\frac{6x^3}{(1-x)(1-2x)(1-3x)}\\ &=x^3\left(\frac3{1-x}-\frac{24}{1-2x}+\frac{27}{1-3x}\right)\\ &=3x^3\left(\sum_nx^n-8\sum_n2^nx^n+9\sum_n3^nx^n\right)\\ &=\sum_n\left(3-3\cdot 2^{n+3}+3^{n+3}\right)x^{n+3}\\ &=\sum_n\left(3-3\cdot 2^n+3^n\right)x^n\;. \end{align*}$$

Equating coefficients, we finally have $a_n=3^n-3\cdot 2^n+3$.

share|improve this answer
    
Thanks! So no application of generating functions here? –  Robert S. Barnes Feb 13 '12 at 19:56
    
$3\cdot\frac{5!}{2!2!}=90$ is easier for me to understand, but same thing... –  Robert S. Barnes Feb 13 '12 at 20:00
    
@Robert: Yes, it can be done with generating functions, but it’s a bit messy, and I’m still writing up that part. –  Brian M. Scott Feb 13 '12 at 20:34
    
Holy crap! Your cool! It's too late at night for me to actually try and read what you wrote, but I'll be on it first thing in the morning! –  Robert S. Barnes Feb 13 '12 at 23:06

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.