2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Hayden Apr 28 '15 at 8:30
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @anonymous: You're welcome. $\endgroup$ – Brian M. Scott Apr 28 '15 at 9:28
0
$\begingroup$

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

| cite | improve this answer | |
$\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.