# Exponential generating function in the case of a singular symbol

Suppose I have the following set {p, q, s, 0, 1, 2, 3} where we have $$l_n$$ is the number of strings with the symbols in this set of length $$n$$. However, there is exactly one number in each string that is a digit.

To find the generating function for this I started off by treating the alphabets as a ternary string and the digits 1 unit. Essentially we have our exponential generating function $$F(x) = x\sum _{n=0}^{\infty }\:3^nx^n\frac{1}{n!}$$. But I feel like my approach so far is wrong (it seems too simple) and this for the case where we only have 1 digit. I don't really know how to factor in the other 3 digits.

• If there are $a_n$ possible strings with exactly one $0$, then there are also $a_n$ possible strings with exactly one $1$, so there are $2 a_n$ strings with exactly one digit which is either $0$ or $1$. Of course, there are $4$ possible digits, not just those two. Don't forget to account for the different positions of a digit within the strings. – aschepler Mar 21 at 23:16

Summary: you were only off by a factor of four. You would be correct if you replaced $$x$$ with $$4x$$.

The EGF for choosing the digits is $$4x^1$$, since there can only be one digit, and there are $$4$$ choices for it.

The EGF for choosing the letters is $$\sum_{n\ge 0} 3^nx^n/n!=e^{3x}$$, since there can be any number $$n$$ of letters, and when there are $$n$$ letters, there are $$3^n$$ ways to choose the letters.

Therefore, the EGF for choosing the entire string (digits and numbers) is the product of these two EGF's. $$(4x)\cdot (e^{3x})$$ To finish, you then need to extract the coefficient of $$x^n$$ and multiply by $$n!$$.

There are $$3^{n-1}$$ strings of length $$n-1$$ with no digit; every string of length $$n$$ with exactly one digit is uniquely obtained by choosing one of these $$3^{n-1}$$ strings, choosing one of the $$4$$ digits, and inserting it in one of the $$n$$ possible positions in the chosen string. For $$n\ge 1$$ this can be done in $$4n\cdot 3^{n-1}$$ ways, so $$\ell_0=0$$, and $$\ell_n=4n\cdot 3^{n-1}$$ for $$n\ge 1$$. The exponential generating function must therefore be

\begin{align*} \sum_{n\ge 0}\ell_n\frac{x^n}{n!}&=\sum_{n\ge 1}\frac{4n}{n!}3^{n-1}x^n\\ &=4x\sum_{n\ge 1}\frac{3^{n-1}x^{n-1}}{(n-1)!}\\ &=4x\sum_{n\ge 0}\frac{3^nx^n}{n!}\,, \end{align*}

for which you should fairly easily be able to find a closed form.