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!

Solutions Collecting From Web of "Combinatoric in binary sequence"

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