Recurrence relation over a finite alphabet

Question

Let $A_n$ be the set of all finite words over the alphabet $\{1,2,3\}$ whose digits sum to $n$. I am trying to find a recurrence relation with initial conditions for $|A_n|$. I have checked the first few $n$ and got that $|A_1|=1$ , $|A_2|=2$, $|A_3|=4$, $|A_4|=7$, $|A_5|=13$, $|A_6|=24$. I can't seem to find a pattern that allows me to create a recurrence relation, nor I am I sure how I could check that such a pattern would be correct.

Answer 1

To set up a recurrence, note that to get a sequence with value $n$ you add a one to one of the sequences giving $n - 1$, a two to a $n - 2$ or a three to $n - 3$. So the number $S_n$ of sequences with value $n$ satisfies:

$\begin{align*} S_n &= S_{n - 1} + S_{n - 2} + S_{n - 3} \end{align*}$

For initial values, we have $S_0 = 1$ (the empty sequence), $S_1 = 1$ (just $1$), $S_2 = 2$ (sequences $11, 2$), $S_3 = 4$ ($111, 12, 21, 3$).

We see that this is just shifted tribonacci numbers (they satisfy the same recurrence, but with $T_0 = T_1 = 0, T_2 = 1$). So $S_n = T_{n + 2}$.

Answer 2

A way to solve this is by using generating functions.

A single digit has weight 1, 2 or 3, so it is represented by $z + z^2 + z^3$, we want a sequence of those, that is:

$\begin{align*} 1 + (z + z^2 + z^3) + (z + z^2 + z^3)^2 + \dotsb &= \frac{1}{1 - (z + z^2 + z^3)} \\ &= \frac{1}{1 - z - z^2 - z^3} \end{align*}$

Consider the tribonacci sequence:

$\begin{align*} T_{n + 3} &= T_{n + 2} + T_{n + 1} + T_n \qquad T_0 = T_1 = 0, T_2 = 1 \end{align*}$

It's generating function is:

$\begin{align*} T(z) &= \sum_{n \ge 0} T_n z^n \\ &= \frac{z^2}{1 - z - z^2 - z^3} \end{align*}$

We see that:

$\begin{align*} \sum_{n \ge 0} T_{n + 2} z^n &= \frac{T(z) -T_0 - T_1 z - T_2 z}{z^2} \\ &= \frac{1}{1 - z - z^2 - z^3} \end{align*}$

So the number of sequences that sum to $n$ is $T_{n + 2}$.