<abstract xmlns="http://www.w3.org/1999/xhtml">

Let <italic>π</italic><italic>n</italic> be a uniformly chosen random permutation on [<italic>n</italic>]. Using an analysis of the probability that two overlapping consecutive <italic>k</italic>-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths <italic>k</italic> ∈ {1, 2,…, <italic>n</italic>} in <italic>π</italic><italic>n</italic> is <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_puma-2022-0031_eq_001.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mfrac><mrow><msup><mrow><mi>n</mi></mrow><mn>2</mn></msup></mrow><mn>2</mn></mfrac><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mi>o</mi><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow></math>
<tex-math>{{{n^2}} \over 2}\left( {1 - o\left( 1 \right)} \right)</tex-math>
</alternatives>
</inline-formula> as <italic>n</italic> → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.
</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.

The expected number of distinct consecutive patterns in a random permutation

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"The expected number of distinct consecutive patterns in a random permutation"}

Let πn be a uniformly chosen random permutation on [n]. Using an analysis of the probability that two overlapping consecutive k-permutations are order...

The expected number of distinct consecutive patterns in a random permutation

Data publikacji: 13 lut 2023

Zakres stron: 1 - 10

Otrzymano: 24 lis 2020

DOI: https://doi.org/10.2478/puma-2022-0031

Słowa kluczowe
random permutation, permutation pattern, consecutive pattern

© 2022 Austin Allen et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

The expected number of distinct consecutive patterns in a random permutation

Data publikacji: 13 lut 2023

Zakres stron: 1 - 10

Otrzymano: 24 lis 2020

DOI: https://doi.org/10.2478/puma-2022-0031

Słowa kluczowerandom permutation, permutation pattern, consecutive pattern

© 2022 Austin Allen et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Słowa kluczowe
random permutation, permutation pattern, consecutive pattern