2
$\begingroup$

I have a problem in which I need to solve for a number of sequences using exponential generating functions. I understand how finding the coefficients of ordinary generating functions work, however, I cannot seem to wrap my head around how to find the coefficients using exponential generating functions.

I was given the following problem to solve:

How many 10-letter words are there in which each of the letters e, n, r, s occur at most once?

I produced the following generationg function.

$(x^0+x^1)^4 (x^0 + x^1 + x^2/2! + x^3/3! + \cdots)^{26-4}$

which simplifies to

$(1+x)^4 e^{22x}$

However now I am completely lost on how to solve for the coefficients. Could somebody explain to me how to do this? Thanks

2 Answers 2

3

The coefficients are given by $\left [\frac{x^n}{n!} \right] (1+x)^4e^{22x} = \sum_{k=0}^{\min\{ 4, n\}} \binom{4}{k}\frac{n!}{n-k!}22^{n-k}.$ To calculate the coefficients of a product of formal power series $\left( \sum_{n=0}^\infty a_nx^n \right) \cdot \left(\sum_{n=0}^\infty b_nx^n \right) = \sum_{n=0}^\infty c_nx^n$ in general, you have to simply form the Cauchy product of the coefficients, that is $c_n = \sum_{k=0}^n a_kb_{n-k}.$

2

In this simple case, you can take @AlexanderThumm's answer a step further: \begin{align} \left[ \frac{x^{10}}{10!} \right] (1 + x)^4 \cdot e^{22 x} &= 10! \left[ x^{10} \right] (1 + 4 x + 6 x^2 + 4 x^3 + x^4) \cdot e^{22 x} \\ &= 10! \left( \frac{22^{10}}{10!} + 4 \frac{22^9}{9!} + 6 \frac{22^8}{8!} + 4 \frac{22^7}{7!} + \frac{22^6}{6!} \right) \end{align} Further simplification and getting numerical values I leave to you.