Record-composition counts for alternating permutations

How many alternating permutations of 2n have a specified record composition α=(α₁,…,α_k) of n? The composition records finer information than the previously counted record partition.

Why it matters and what counts as progress

Why it matters: Record compositions retain ordered information lost in record partitions, linking finer permutation enumeration to noncommutative symmetric functions.

What counts as progress: Derive an exact composition formula or an algebraic interpretation refining the record-partition count.

How the problem developed

2026 · Partial result [1]
Tewodros Amdeberhan, John Shareshian, and Richard Stanley Interpreted a partition-indexed function from partition Eisenstein series as counting alternating permutations by record partition, and posed the refinement to ordered record compositions.
14 Jul 2026 · Reported claim [1]
Evan Chen, Michal Mogielnicki, and Ken Ono; AxiomProver Answered the record-composition question with an explicit product formula and a lift to noncommutative symmetric functions; the paper reports autonomous Lean verification.

AI contribution

Record compositions of alternating permutations and noncommutative symmetric functions

Evan Chen, Ken Ono, Michal Mogielnicki

For each composition α=(α₁,…,α_k) of n, the number of alternating permutations of 2n with record composition α is ∏_j binom(2s_j−1,2α_j−1)E_(2α_j−1), where s_j=α₁+…+α_j and E_m is an Euler number. The paper also realizes these counts in a noncommutative symmetric-function lift.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (Lean 4.31.0)

Human understandingFull