permotif

Permotif is a term used in some branches of combinatorics and sequence analysis to denote a recurring local ordering motif extracted from a permutation or finite sequence. It emphasizes motif-like substructures within a larger arrangement, akin to biological or textual motifs.

Formally, let sigma be a permutation of length n and k a fixed positive integer. A pattern p in the symmetric group S_k is an order type. An occurrence (a permotif) of p in sigma is a k-tuple of indices i1<...<ik such that the relative order of sigma(i1),...,sigma(ik) matches p. For example, in sigma = 5 1 4 2 3, the indices (2,4,5) give the subsequence (1,2,3), which is pattern 123, and (1,3,4) gives (5,4,2), pattern 321. The set of all occurrences of p in sigma is the permotif of type p in sigma. If P is a fixed finite set of patterns of length k, the permotif signature of sigma with respect to P is the vector counting occurrences of each p in P.

Permotifs are studied alongside permutation patterns and pattern avoidance. They are transformed predictably under reversal or complementation of the permutation, and relabeling values preserves pattern type.

Computationally, counting all occurrences of a fixed pattern p in a permutation of length n can be done by enumeration in O(n^k) time; faster algorithms exist for small k or restricted pattern sets.

Applications include characterizing and comparing permutations by their permotif signatures, analyzing structural properties in genome rearrangements, and providing a motif-based lens in the study of permutation classes.

Origin and status: the term permotif is not universally standardized; it appears in some recent texts to emphasize motif-like structure within permutations rather than as a separate, widely used concept.