My question involves the number of ways to add up to a positive integer $n$ such that the order in which we add the terms up matter (so ignoring commutativity) and we are restricted to only using $1$'s, $2$'s and $3$'s. Hence I want to count observations such that $1+2+1$ is different from $2+1+1$
If we didn't care about order mattering or we weren't restricted to the first three numbers, this problem could have simply been solved with the partition function.
Denote $\lambda(n)$ to be the function mapping a positive integer $n$ to the number of ways you can sum to $n$ using various summations of $1$s, $2$s, and $3$s.
What I know so far
I am only really concerned for finding it up to $n=8$, but should a generalization for $n\in \mathbb{Z}^+$ exist, I would be glad to see it.
I've worked it out for $1 \le n \le 3$ using the following argument:
By observation, we can pick out $\lambda (1) = 1$. Setting up however many ones we need, let's say $2$ for this case, we have $$1\_ 1$$
Where we can choose either to fill the gap with a $+$ or a $:$, where a $:$ between two numbers means combine them into one term, so $1:1$ would represent the possibility of $2$ and $1+1$ is itself the other possibility. Therefore $\lambda(2) = 2$
Similarly for $n=3$, we have $$1\_1\_1$$
Using the argument above, we have two options for each blank, so we have that $\lambda (3) = 2^2 = 4$.
This strategy however falls apart for $n\ge 4$. The argument would say that $\lambda (4) = 8$, but this doesn't consider that one of those options includes filling all the gaps with a "$:$" which represents using the number $4$. We are restricted to only the first three positive integers, so after subtracting this invalid option we now have that $\lambda (4) = 7$.
So now our argument no longer works, and if it wasn't for the fact that the case of $n=5$ isn't hard to quickly subtract the invalid options (which are $5, 4+1,$ and $1+4$) I wouldn't have known so fast that $\lambda (5) = 13$.
I really don't want to sit and continue counting off the invalid options to find $\lambda (6)$ onwards, but I'm aware it can be done with patience. So right now the general formula I am using is $$\lambda (n) = 2^{n-1} – \text{the # of invalid options}$$ but I would like to find an improvement to this formula or maybe find a nicer formula instead.
Any help is greatly appreciated.
Best Answer
The last number is either a $1$, a $2$, or a $3$. If it's a $1$, there are $\lambda(n-1)$ ways to fill in the preceding numbers; if it's a $2$, there are $\lambda(n-2)$ ways; if it's a $3$, $\lambda(n-3)$.
This gives us the recursive equation $$ \lambda(n)=\lambda(n-1)+\lambda(n-2)+\lambda(n-3) $$ which, along with the initial values $\lambda(1)=1$, $\lambda(2)=2$, $\lambda(3)=4$ you've computed, is enough to compute $\lambda(n)$ for any $n$: $$ \lambda(4)=1+2+4=7\\ \lambda(5)=2+4+7=13\\ \lambda(6)=4+7+13=24 $$ and so on.
This is a homogeneous linear difference equation. You could work out an formula for $\lambda(n)$ using the method given in the link, but it would involve the roots of an irreducible cubic polynomial. So for most practical purposes it's probably better to just use the recursion.