# a multiset where two consecutive numbers must be dissimilar

I am currently looking for a solution of following problem:

Let us assume that we have found types, e.g., S = {1, 2, 3, 4} and we are planning to create a multiset, M, by picking values from S with a constraint, which is: two consecutive picked numbers can not be similar. For instance, {1, 2, 1} is allowed, but {1, 1, 2} is not allowed since 1 appears consecutively. I would like to find out how many k-length subsets are possible for the given values where k is a positive integer number.

I checked it using brute-force technique, and the acquired results are: when k = 1 number of subsets = 4; when k = 2 number of subsets = 12; when k = 3 number of subsets = 36; when k = 4 number of subsets = 108; when k = 5 number of subsets = 324.

I know the result of k_i is the three times higher that k_{i-1}. However, I would like to know the mathematical details; preferably using equations. Your support would be highly appreciated.

• I wouldn't really call those multisets, since multisets count duplicates but not order. It sounds like you're just forming finite sequences with a condition on them. – Hayden Apr 28 '15 at 8:30

If you have $n$ types, there are $n$ choices for the first term of the $k$-tuple and $n-1$ for each subsequent term, so there are $n(n-1)^{k-1}$ sequences of length $k$.
Let $a_n,b_n,c_n,d_n$ the number of possible strings with lenght $n$ ending with $1,2,3,4$ respectively. Then $a_1=b_1=c_1=d_1=1$. Moreover $a_{n+1}=b_n+c_n+d_n$ and cyclically the others. Therefore $$a_{n+1}+b_{n+1}+c_{n+1}+d_{n+1}=3(a_n+b_n+c_n+d_n).$$ Considering that $a_1+b_1+c_1+d_1=4$ then $$a_n+b_n+c_n+d_n=4\cdot 3^{n-1}.$$