2023/10/28 by Jonas Iskander, Iskander, Jonas
Computer Science · Mathematics · #05A15 (Primary) 05E10 (Secondary) #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2310.18798
openalex publication_date 2023/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given permutations π∈ Sn and σ∈ Sk, let Nσ(π) denote the number of occurrences of σ in π. While pattern avoidance and the distribution of pattern occurrences in permutations have been extensively studied, their interactions with the group structure on Sn are still poorly understood. Gaetz and Ryba showed that the expected value of χλ[n](π)Nσ(π) for π∈ Sn is given by a polynomial aσλ(n). More recently, Gaetz and Pierson derived explicit formulas for aidkλ(n) when |λ| ≤ 2, which led them to conjecture that the polynomials aidkλ(n) are real-rooted and nonnegative for n ≥ k. We show that for all partitions λ, the polynomials aidkλ(n) admit explicit closed forms in n and k. These formulas allow us to exhibit counterexamples to Gaetz and Pierson's real-rootedness conjecture as well as to prove special cases of their nonnegativity conjecture. Lastly, we note that our results imply that the expected value of f ⋅ Nidk on Sn admits a closed form whenever f is a permutation statistic expressible as a polynomial in the functions mj \colon \bigsqcupn ≥ 0 Sn → ℤ which count j-cycles in their inputs.