3
$\begingroup$

(I asked this ten days ago on math.SE, but I received no reply, so I'm trying again here.)

A lot of work has been done on patterns in permutations, where a permutation is said to match a given pattern if it contains a subsequence of elements ordered according to the pattern (e.g., $\pi=(2\ 1\ 7\ 5\ 3\ 6\ 4)$ matches $4\ 1\ 3\ 2$ -- consider the subsequence $7\ 3\ 6\ 4$).

One could be more restrictive and require that the subsequence of elements to be tested against the pattern not only follows the same order, but that the gaps between the elements (or between some, but not all, pairs of elements) is the same. In the above example, for instance, $7\ 3\ 6\ 4$ would no longer be a match for $4\ 1\ 3\ 2$ (but $6\ 3\ 5\ 4$ would, had it been a subsequence of $\pi$).

Has there been work on such constrained patterns? If so, what are they called, and what would be good references to check?

$\endgroup$
2
  • $\begingroup$ Well, do you have reasons to assume that either some enumeration results of that sort are terribly cute or that patterns like that arise in some natural questions in maths where the words "permutation" and pattern" does not appear in the question? In both cases of pattern avoidance I am aware of both conditions are actually satisfied... $\endgroup$ Jul 18, 2011 at 16:23
  • $\begingroup$ I'm not interested -- yet -- in enumeration results. If I'm parsing the second part of your question correctly, which puzzles me somehow, then the answer is no. $\endgroup$ Jul 18, 2011 at 17:42

1 Answer 1

6
$\begingroup$

Yes, these things have been studied extensively in two ways:

1) As bivincular patterns, introduced in a 2010 paper by Bousquet-Mèlou, Claesson, Dukes and Kitaev.

2) If you require the occurrence in the permutation to be completely consecutive in values (like 6354) then the inverse of your pattern is called a consecutive pattern. These have been studied by Elizalde and many others.

$\endgroup$
2
  • $\begingroup$ For (2), I've also seen these referred to as "restricted words". $\endgroup$ Jul 18, 2011 at 21:12
  • $\begingroup$ Thanks, bivincular patterns do seem to be what I'm looking for. $\endgroup$ Jul 19, 2011 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.