Combinatoric in binary sequence

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:

1. if $x1<x2<x3$ then this is pattern 123
2. if $x1<x3<x2$ then this is pattern 132
3. if $x2<x1<x3$ then this is pattern 213
4. if $x2<x3<x1$ then this is pattern 231
5. if $x3<x1<x2$ then this is pattern 312
6. 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!

• What is your question? Do you want to enumerate how many sequences give the different patterns for a given $n$? Or do you want to know how many patterns a given sequences exhibits? – Mosquite Apr 5 '17 at 20:25
• So would the sequence of all zeros give the same result as a sequence of all ones? – hardmath Apr 5 '17 at 20:26
• Yes, it is used later to check the randomness of the sequence, all zeros and all ones have the same complexity – DrFran Apr 5 '17 at 20:27
• Mosquite, the answer is how many patterns are there for any given m, the answer is $2^m - m$ but I can seem to figure out why – DrFran Apr 5 '17 at 20:29
• $123456$ could be arrived from $000000$, $000001$, $000011$, $000111$,... $111111$. Are there any other sequences with multiple preimages? – JMoravitz Apr 5 '17 at 20:39

The admissible patterns are exactly the image of your transformation for a sequence of length of length $m$. i.e two interleaved increasing sequences.
So to count them you merely need to count the number of ways to insert the sequence $1, \ldots, k$, which is $\binom{m}{k}$ ($2^m$ in total (including the empty sequence (k=0))). However, if $1, \ldots, k$ is at the beginning then it gives the same sequence so you subtract the $m$ duplicates, giving $2^m -m$.