{"id":"arxiv/2601.13194","url":"https://arxiv.org/abs/2601.13194","tags":["math.CO","math.PR"],"score":0,"title":"A Lower Bound on the Expected Number of Distinct Patterns in a Random Permutation","domain":"math.CO","source":"arxiv","authors":["Verónica Borrás-Serrano","Isabel Byrne","Anant Godbole","Nathaniel Veimau"],"reviews":0,"subject":"math.CO","summary":"Let $π_n$ be a uniformly chosen random permutation on $[n]$. The authors of [2] showed that the expected number of distinct consecutive patterns of all lengths $k\\in\\{1,2,\\ldots,n\\}$ in $π_n$ was $\\frac{n^2}{2}(1-o(1))$ as $n\\to\\infty$, exhibiting the fact that random permutations pack consecutive patterns near-perfectly. A conjecture was made in [11] that the same is true for non-consecutive patterns, i.e., that there are $2^n(1-o(1))$ distinct non-consecutive patterns expected in a random permutation. This conjecture is false, but, in this paper, we prove that a random permutation contains…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-19","reactions":{}}