# Counting Permutation Patterns with Multidimensional Trees

arXiv: https://arxiv.org/abs/2407.04971 · HTML: https://mlsanity.com/paper/2407.04971/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2024.

## Built on by (most cited first, 2 of 2)

- [Tensor-to-Tensor Models with Fast Iterated Sum Features](https://mlsanity.com/paper/2506.06041/) (2025)
- [Global Permutation Entropy](https://mlsanity.com/paper/2508.19955/) (2025)

## Abstract (arXiv)

We consider the well-studied pattern counting problem: given a permutation π ∈ mathbbSn and an integer k > 1, count the number of order-isomorphic occurrences of every pattern τ ∈ mathbbSk in π. Our first result is an widetildeO(n2)-time algorithm for k=6 and k=7. The proof relies heavily on a new family of graphs that we introduce, called pattern-trees. Every such tree corresponds to an integer linear combination of permutations in mathbbSk, and is associated with linear extensions of partially ordered sets. We design an evaluation algorithm for these combinations, and apply it to a family of linearly-independent trees. For k=8, we show a barrier: the subspace spanned by trees in the previous family has dimension exactly |mathbbS8| - 1, one less than required. Our second result is an widetildeO(n7/4)-time algorithm for k=5. This algorithm extends the framework of pattern-trees by speeding-up their evaluation in certain cases. A key component of the proof is the introduction of pair-rectangle-trees, a data structure for dominance counting.