Discrete Mathematics & Theoretical Computer Science |

Let $\pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $\pi_n$ is $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$. This exhibited the fact that random permutations pack consecutive patterns near-perfectly. We use entirely different methods, namely the Stein-Chen method of Poisson approximation, to reprove and slightly improve their result.

Source: arXiv.org:2310.14071

Volume: vol. 26:1, Permutation Patterns 2023

Section: Special issues

Published on: May 3, 2024

Accepted on: March 19, 2024

Submitted on: October 24, 2023

Keywords: Mathematics - Combinatorics,Mathematics - Probability,05A99, 60C05

This page has been seen 164 times.

This article's PDF has been downloaded 87 times.