Finding Generating Series for Number of "words" in an Alphabet

Question

Question: Find the generating series with the property that for each non-negative integer $n$, the coefficient of $x^n$ is the number of "words" of length $n$ coming from the alphabet $\{{a,b,c}\}$. Examples of words of length 3 are aaa, aab, baa, cba, etc.

So I believe this means you could choose anywhere from $0$ to $n$ numbers from the "alphabet", and the number of combinations for any length $n$ would just be $3^n$ for $n>0$. So would the coefficients simply be $3^n$? Would this yield: $\sum_{n=1}^33^nx^n $ ? This seems too incorrect, any help would be much appreciated.

On a side note, the question goes on to solve for the general case of any alphabet size $k$, where $k$ is any positive integer.

Yes, but why are we stopped at $n=3$? Also we should include $n=0$. The empty word is a word. — TheNumber23, Dec 04 '13 at 17:24
well wouldn't there be zero words for an empty word? The summation would yield $3^0x^0$=1. I'm not sure why I stopped at 3, I suppose it should be for any $n>0$ or $n>1$ — datascii, Dec 04 '13 at 17:30
Or by what you said the empty word is a word and therefore $n= 0$ yields 1, and the solution would be $\sum_{n=0}^\infty3^nx^n$ ? — datascii, Dec 04 '13 at 17:33
correct, there is one empty word like there is one empty set. The last solution is correct. — TheNumber23, Dec 04 '13 at 18:01

Duchamp Gérard H. E. · Answer 1 · 2015-04-01T10:52:49.563

For a three-letter alphabet, the number of words of length $n$ is $3^n$. For a general alphabet $X=\{a_1\dots a_k\}$, the number of words of length $n$ is $k^n$ and the generating series is $$\sum_{n=0}^\infty k^n\, z^n=\frac{1}{1-kz}$$ Length (number of letters) is a particular case of ``length function'' : to each letter you attribute a length (or a weight), hence you have a map $l:\ X\rightarrow \mathbb{N}_{\geq 1}$, the usual length being given by the constant function equal to $1$ $((\forall x\in X)(l(x)=1))$. In the general case, the number $a_n$ of words of length $n$ is given by the g.f. $$ \sum_{n\geq 0}a_n\, z^n=\frac{1}{1-\sum_{x\in X}z^{l(x)}}\ . $$ As a particular case, with the two letter alphabet ${a,b}$ and $l(a)=1,\ l(b)=2$, the number of words of length $n$ is $F_n$ the n-th Fibonacci number.

Finding Generating Series for Number of "words" in an Alphabet

1 Answers1