The expected number of distinct consecutive patterns in a random permutation

Austin Allen; Dylan Cruz Fonseca; Veronica Dobbs; Egypt Downs; Evelyn Fokuoh; Anant Godbole; Sebastián Papanikolaou Costa; Christopher Soto; Lino Yoshikawa

doi:10.2478/puma-2022-0031

.blurhash-client-img { display: none !important; }

The expected number of distinct consecutive patterns in a random permutation

Pure Mathematics and Applications

Volume 30 (2022): Issue 4 (December 2022)

By: Austin Allen, Dylan Cruz Fonseca, Veronica Dobbs, Egypt Downs, Evelyn Fokuoh, Anant Godbole, Sebastián Papanikolaou Costa, Christopher Soto and Lino Yoshikawa

Open Access

|Feb 2023

Abstract

Let π_n be a uniformly chosen random permutation on [n]. Using an analysis of the probability that two overlapping consecutive k-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths k ∈ {1, 2,…, n} in π_n is n22(1-o(1)) {{{n^2}} \over 2}\left( {1 - o\left( 1 \right)} \right) as n → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.

References

[1] M. Albert, M. Coleman, R. Flynn and I. Leader, Permutations containing many patterns, Ann. Comb., 11 (2007) 265—270.10.1007/s00026-007-0319-9
Open DOI Search in Google Scholar Back to article
[2] Y. Biers-Ariel, A. Godbole and E. Kelley, Expected number of distinct subsequences in randomly generated binary strings, Discrete Math. Theor. Comput. Sci., 19 (2018) #10.
Search in Google Scholar Back to article
[3] M. Bóna, On non-overlapping patterns of permutations, Pure Math. Appl. (PU.M.A.), 22 (2011) 99–105.
Search in Google Scholar Back to article
[4] J. Borga and R. Penaguiao, The feasible region for consecutive patterns of permutations is a cycle polytope, available at https://arxiv.org/pdf/1910.02233.pdf.
Search in Google Scholar Back to article
[5] J. Borga and R. Penaguiao, The feasible regions for consecutive patterns of pattern-avoiding permutations, available at https://arxiv.org/pdf/2010.06273.pdf.
Search in Google Scholar Back to article
[6] M. Coleman, An answer to a question by Wilf on packing distinct patterns in a permutation, Electron. J. Combin., 11 (2004) #N8.10.37236/1849
Open DOI Search in Google Scholar Back to article
[7] A. Duane and J. Remmel, Minimal overlapping patterns in colored permutations, Electron. J. Combin., 18 (2011) #P25.10.37236/2021
Open DOI Search in Google Scholar Back to article
[8] A. Flaxman, A. Harrow and G. Sorkin, Strings with maximally many distinct subsequences and substrings, Electron. J. Combin., 11 (2004) #R8.10.37236/1761
Open DOI Search in Google Scholar Back to article
[9] E. Fokuoh, The expected number of patterns in a randomly generated permutation on [n] = {1, 2, ..., n}, M.Sc. Thesis, East Tennessee State University, 2018, available at https://dc.etsu.edu/cgi/viewcontent.cgi?article=4916&context=etd.
Search in Google Scholar Back to article
[10] A. Miller, Asymptotic bounds for permutations containing many different patterns, J. Combin. Theory Ser. A, 116 (2009) 92–108.10.1016/j.jcta.2008.04.007
Open DOI Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/puma-2022-0031 | Journal eISSN: 1788-800X

Journal RSS Feed

Language: English

Page range: 1 - 10

Submitted on: Nov 24, 2020

Published on: Feb 13, 2023

Published by: Corvinus University of Budapest

In partnership with: Paradigm Publishing Services

Keywords:

random permutation,

permutation pattern,

consecutive pattern

MSC:

05D40,

60C05,

05A05

Related subjects:

Computer sciences,

Theoretical computer sciences,

Business and economics,

Mathematics and statistics for economists,

Mathematics,

Analysis,

Differential equations and dynamical systems

© 2023 Austin Allen, Dylan Cruz Fonseca, Veronica Dobbs, Egypt Downs, Evelyn Fokuoh, Anant Godbole, Sebastián Papanikolaou Costa, Christopher Soto, Lino Yoshikawa, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 30 (2022): Issue 4 (December 2022)