A lattice-path reduction for canon permutations avoiding {12ʲ1, 21ʲ2}

Abstract

A canon permutation is a k-regular word over [n] in which, for every j, the subsequence of j-th copies of the letters is one and the same permutation. Laudone enumerated the canon permutations avoiding the symmetric pattern set O(12ʲ1)={12ʲ1,21ʲ2} in every regime except one, and asked what the count is in the remaining range n ≥ 3, 4 ≤ j<k<2(j-1), printing seven terms of the smallest open case (j,k)=(4,5). We give a column-merging reduction which turns the count, for every such (j,k), into an excursion count for a lattice path in an orthant of dimension 2j-k-1; on the diagonal k=2j-3, which contains the smallest open case, the model is a walk in the quarter plane with the three steps (1,0), (-s,s), (0,-1), where s=k-j+1. The reduction makes the open cells computable in polynomial time, where direct enumeration is not: we extend the smallest open case from Laudone's seven terms to forty, and give the first terms of the nine further open cells with j ≤ 7, for which no values have been published. We then prove a negative structural result: the smallest open case admits no P-recursive recurrence with rational polynomial coefficients in any of seven (order, degree) boxes — none of order ≤ 15 and degree ≤ 7, none of order ≤ 1 and degree ≤ 63, and no constant-coefficient recurrence of order ≤ 74 — so the open row of Laudone's table has no answer of the shape its other rows have. A Denisov–Wachtel computation on the quarter-plane model predicts an irrational polynomial-correction exponent, which leads us to conjecture that the generating function is not D-finite on the whole diagonal k=2j-3. All finite statements below are formally verified in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   3dc92632a57ddb36d84c1990f85c51a4135087303b2f56f6af9bb2c6ed78c3a5