0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – aschepler Mar 21 at 23:16
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.