Counting subsequences matching a pattern

Question

Given a sequence $(a_1, a_2, \ldots, a_n)$ and a number $m$, I'd like to count the number of subsequences $(a_{i_1},a_{i_2},a_{i_3})$ such that $a_{i_2} < m \leq a_{i_1}, a_{i_3}$.

For example, if the sequence is $(4,2,1,3)$ and $m = 3$, then there are two such subsequences, namely $(4,2,3)$ and $(4,1,3)$.

I solved the problem in two steps: transforming the list into a $0-1$ list using

binary[list_List, m_Integer] := 
  Table[If[list[[i]] < m, 0, 1], {i, 1, Length[list]}]

allows us to count the $(1,0,1)$ subsequences several different ways, including

SequenceCount[binary[list, m], {1, ___, 0, ___, 1}, Overlaps -> All]

This seems to work fine, but now I'm trying to eliminate the first transformation and use SequenceCount with a pattern on the original list directly; however the following does not work as it returns 1 instead of 2:

list = {4, 2, 1, 3}; m = 3;
SequenceCount[list, {x_, ___, y_, ___, z_} /; x >= m && y < m && z >= m, Overlaps -> All]

What is the problem with the second approach? I suspect that the conditional pattern is wrong, but I cannot figure out why. Neither SequenceCases nor SequencePosition help.

Bonus question: is there a 'better', more efficient way to do this?

Answer 1

I think there is some sort of pattern bug here. It appears that, as expected, SequenceCases deletes duplicates before it returns its result.

With

list = {4, 2, 1, 3};

Your pattern

{x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m)

in the sequence function will return the entire list in both cases as both start with 4 and end with 3. When duplicates are deleted only once result is returned.

SequenceCases[list, 
   {x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m), 
   Overlaps -> All]

{{4, 2, 1, 3}}

You need to specify which items your want to return so that unique subsets are return for each case.

SequenceCases[list, 
   {x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m) :> {x, y, z}, 
   Overlaps -> All]

{{4, 2, 3}, {4, 1, 3}}

However, this presents a dilemma for SequenceCount as without the RuleDelayed it finds only one sequence, as explained above.

SequenceCount[list, 
   {x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m), 
   Overlaps -> All]

1

But it completely fails when the sublist to return is specified.

SequenceCount[list, 
   {x_, ___, y_, ___, z_} /; (x >= m && y < m && z >= m) :> {x, y, z}, 
   Overlaps -> All]

0

I am of the opinion that this is a bug in SequenceCount. Comments?