0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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