3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mosquite Apr 5 '17 at 20:25
  • $\begingroup$ So would the sequence of all zeros give the same result as a sequence of all ones? $\endgroup$ – hardmath Apr 5 '17 at 20:26
  • $\begingroup$ Yes, it is used later to check the randomness of the sequence, all zeros and all ones have the same complexity $\endgroup$ – DrFran Apr 5 '17 at 20:27
  • $\begingroup$ 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 $\endgroup$ – DrFran Apr 5 '17 at 20:29
  • 1
    $\begingroup$ $123456$ could be arrived from $000000$, $000001$, $000011$, $000111$,... $111111$. Are there any other sequences with multiple preimages? $\endgroup$ – JMoravitz Apr 5 '17 at 20:39
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks Mosquite, do you happen to know where i can find more of interleaved increased sequences? I want to extend this to three, four ... interleaved increasing sequences. $\endgroup$ – DrFran Apr 5 '17 at 22:05
  • $\begingroup$ You might want to look into permutation patterns, en.wikipedia.org/wiki/Permutation_pattern. Though, by your terminology, I suspect you already have. $\endgroup$ – Mosquite Apr 5 '17 at 22:06
  • $\begingroup$ I suspect you can generalize to multiple increasing sequences results with en.wikipedia.org/wiki/Multinomial_theorem. $\endgroup$ – Mosquite Apr 5 '17 at 22:08

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.