Number of monotonic sequence on $\{1,2,3,4\}$

Question

How many number of monotonic sequences ($1$ can be followed by $1$, but $2,3,4$ can be followed by $1$, etc..) of length $n$ are on $\{1,2,3,4\}$ ?

Attempt -

So i can look at this problem such that $1,2,3,4$ are my "bags", i have $n$ identical balls to put inside them, each bag can get at most $n$ balls, and i can leave bags empty, than after the balls are in the bag - I build my sequence such that $1$ is placed the number of times the balls he is containing, same for $2,3,4$.

So - the solution for this problem would be $S(n,4) = {\binom{n+4-1}{4}}$

What do you think ? is this approcah true ? Thank you !

Answer 1

Basicly you have to solve the equation $$a_1+a_2+a_3+a_4=n$$ where $a_i$ is a number of $i$. And this is well know to have $${n+4-1\choose 4-1}$$ solutions. So your solution is incorrect.

Answer 2

You start with 1 and place 3 "$+1$"s in $n-1$ different crates without ordering, which is $C_{n-1}^{3}$.

Answer 3

If the sequences are supposed to be monotonic then applying stars and bars I would go for: $$2\binom{n+4-1}{4-1}-4$$ taking into account that the sequence can be monotonic non-decreasing and can be monotonic non-increasing.

Doing it with $2\binom{n+4-1}{4-1}$ gives double counting of the constant sequences which must be repaired by subtraction of $4$.