1
$\begingroup$

Find an exponential generating function for ${a_r}$ , the number of $r$- letter words with no vowel used more than once (consonants can be repeated).

The answer is $(1 + x)^5e^{21x}$.

One solution I see is the following:

Since there can be one $(x^1 = x)$ OR no vowel $(x^0 = 1)$, the generating function for the vowels, by the additive principle, is $1 + x$. The exponential generating function for the consonants is $e^x =\sum_{n\ge 0}\frac{x^n}{n!}$. Since there are $21$ consonants, we have $e^{21x}$. By multiplying the two, we have: $(1 + x)^5e^{21x}$. My doubts are:

1) Why the generalized function for each of the consonants is $e^x$?

2) Why do we multiply it $21$ times?

3) Why, in the end, do we multiply both?

$\endgroup$
0
$\begingroup$

The number of $r$-letter words which have only constants is $21^r$. Hence the exponential g.f. is $$\sum_{r=0}^{\infty}\frac{21^r x^r}{r!}=e^{21x}.$$ Now consider the case of the $r$-letter words with a vowel "a". Their number is $r21^{r-1}$ (why?) and the exponential g.f. is $$\sum_{r=1}^{\infty}\frac{r21^{r-1} x^r}{r!}=x\sum_{r=1}^{\infty}\frac{21^{r-1} x^{r-1}}{(r-1)!}=xe^{21x}.$$ So the e.g.f. of the $r$-words with consonants and at most one "a" is $$\sum_{r=0}^{\infty}\frac{(21^r+r21^{r-1})x^r}{r!}=(1+x)e^{21x}.$$ Can you take it from here?

P.S. Recommended reading: Section 2.3 of Generatingfunctionology by Herbert Wilf.

$\endgroup$
1
  • $\begingroup$ @gmn_1450 Any feedback from your side? $\endgroup$
    – Robert Z
    Jun 26 '19 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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