Find the maximum number of words given the length.

Question

Given that $\alpha \in \mathbb{N}$ and $\Sigma = \{\text{a,b,c}\}$ how can we find the number of different words of length $\alpha$? I can see that the sequence of the words is not important, i.e. it can start off with and have any letter in its sequence which is random, and you have to reuse the letters. As a visual exercise I wrote down all possible words with maximum length $1$ which is equal to $3$, all possible words with maximum length $2$ which is equal to $13$ and all possible words with maximum length $3$ which is equal to $39$. But I'm looking for a way to make a formula that can calculate the maximum number of words that can be generated for any given the maximum length $\alpha$. I'm also thinking if I can include $\epsilon$ since $\alpha$ can be $0$.

Answer 1

Let us denote $\lvert m \rvert$ the length of a word and $\Sigma_n = \{ m \mid \exists (m_1, \ldots, m_n) \in \Sigma^n, m = m_1 m_2 \ldots m_n \}$, words of length $n$ and then: $\Sigma^{*} = \bigcup_{n \in \mathbb{N}} \Sigma_n$, all words over $\Sigma$.

Now, let us denote $\Sigma_{\leq n}$ the words of maximum length $n$ as $\Sigma_{\leq n} = \bigcup_{i \leq n} \Sigma_i$.

We want the cardinal of $\Sigma_{\leq n}$, we have (because the union is disjoint):

\begin{align*} \mathrm{card}\, \Sigma_{\leq n} & = \sum_{i=0}^n \mathrm{card}\, \Sigma_i \end{align*}

Let us denote $N_i = \mathrm{card}\, \Sigma_i = \left(\mathrm{card}\, \Sigma\right)^i$, let us denote $M = \mathrm{card}\, \Sigma$.

Now, we have: $\mathrm{card}\, \Sigma_{\leq n} = \dfrac{M^{n + 1} - 1}{M - 1}$.

We can see for $M = 3$ and $n = 2$, we have $13$, which is the result we expected.

If you want to exclude $\varepsilon$ the empty word, just sum from $1$ to $n$.

Answer 2

Hint:

$(3^0+3^1+\cdots+3^{\alpha})(3-1)=3^{\alpha+1}-1$