Suppose you have a binary sequence $s_t$ of length T. We transform this sequence in integers by replacing the zeroes with 1,2,3....,k and the ones by k+1,k+2....T.
For example 000000 is transformed in 123456 and 100000 is transformed in 612345 and finaly 101010 is 415263.
Now i would like to search for patterns in the transformed sequence, i grab subsequences of lenght 3 (m=3) and:
- if $x1<x2<x3$ then this is pattern 123
- if $x1<x3<x2$ then this is pattern 132
- if $x2<x1<x3$ then this is pattern 213
- if $x2<x3<x1$ then this is pattern 231
- if $x3<x1<x2$ then this is pattern 312
- if $x3<x2<x1$ then this is pattern 321
for example 101010 = 415236
415 = 213; 152 = 132; 523 = 231; 236 = 123
But opcion 6 (321) is never going to happen for the nature of the trasformation.
How many patterns are there? In this case the answer is 5 (all the listed but option six could happen)
If you want a subsequence for a greater m the answer is $2^m-m$ I do not understand how to arrive to this answer. If anyone could help me!