Distributions of mesh patterns of short lengths on king permutations

Dan Li; Philip B. Zhang

REVIEW 4 major objections 2 minor 20 references

Distributions of mesh patterns of short lengths on king permutations

T0 review · 4 major / 2 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper derives exact distributions for 22 mesh patterns on king permutations.

desk verdict Solid, workmanlike enumeration paper extending mesh-pattern distributions to king permutations; the formulas pass consistency checks, but the load-bearing 'almost king' bijection in Theorems 4.6–4.7 needs a real proof before you trust the answers. read the letter →

arxiv 2411.18131 v1 pith:O5UJD67R submitted 2024-11-27 math.CO

Dan Li , Philip B. Zhang This is my paper · ORCID

classification math.CO MSC 05A0505A15

keywords meshpatternkingpermutationdistributionavoidancegeneratingfunctionpatterns

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

King permutations are permutations in which consecutive entries never differ by exactly 1. This paper extends the program of enumerating mesh-pattern occurrences to this restricted class, obtaining, for each of 22 short mesh patterns, an explicit bivariate generating function in which the first variable tracks length and the second tracks the number of occurrences. The same formulas yield the avoidance generating function for each pattern as the special case $u=0$. A sympathetic reader would care because such formulas convert a complicated combinatorial statistic into a rational expression in the known generating function of king permutations, making avoidance counts and distribution moments computable in closed form.

What carries the argument

The engine of the paper is a decomposition method: identify an extremal occurrence of the target pattern, split the permutation into the blocks left and right of that occurrence, and express the generating function of the whole class as a product or sum of generating functions for smaller, already-understood subclasses of king permutations, namely $A(t)$, $B(t)$ (king permutations not beginning with the smallest element), and $C(t)$ (those not beginning with the smallest element nor ending with the largest). Reverse and complement symmetries reduce the 22 patterns to a smaller number of cases. The resulting functional equations are solved to produce explicit rational formulas in $A(t)$, where $A(t)=\sum_{n\ge0} n!t^n(1-t)^n/(1+t)^n$ is the known generating function for king permutations.

What would settle it

Enumerate all king permutations of length $n$ for $n=5,6,\dots,10$ by brute force, compute the total number of occurrences of each of the 22 patterns, and compare the resulting polynomial in $u$ with the coefficient of $t^n$ in the stated $E(t,u)$ from the corresponding theorem. The paper's own initial expansions agree at least through $n=7$ or $8$ for most patterns, so a first mismatch beyond that range would identify a specific formula to correct.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that for 22 mesh patterns of length 2 the distribution generating function $E(t,u) = \sum_{n\ge0} t^n \sum_{\sigma\in K_n} u^{p(\sigma)}$ is a rational expression in the known generating function $A(t)$ of king permutations, and the avoidance generating function $P(t) = E(t,0)$ is likewise rational in $A(t)$. For six of these patterns no king permutation can contain an occurrence, so $E(t,u)=A(t)$; for several others a permutation can contain the pattern at most once, and the generating functions simplify accordingly. The remaining cases are resolved by decomposing a king permutation at the leftmost (or otherwise extremal) occurrence of the pattern and setting up functional equations whose solutions yield the stated formulas.

Load-bearing premise

For patterns Nr. 55 and Nr. 63 the proofs assume that a non-king prefix whose only violation is that its left part ends with the value one less than the next element can be turned into a king permutation by replacing the minimum element $1$ with $21$, and that this operation neither destroys nor creates any occurrence of the pattern; the formulas for those two patterns stand or fall on that correspondence.

Editorial extensions

If this is right

For each of the 22 patterns, the coefficient of $t^n$ in the stated $P(t)$ gives the number of king $n$-permutations avoiding that pattern, so avoidance counts can be computed for every $n$ at once.
The bivariate generating functions $E(t,u)$ determine the full distribution of the occurrence statistic, including the probability that a uniformly random king $n$-permutation contains exactly $k$ occurrences.
Six of the patterns are impossible in king permutations, and several others can occur at most once, so their distributions collapse to simple expressions in $A(t)$.
Apart from the six impossible patterns, the 22 distributions are pairwise different, showing that on king permutations no further coincidental equidistributions among these short patterns exist.
The paper explicitly lists ten additional short patterns whose distribution on king permutations remains open, so the enumeration program is not yet complete.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

We infer that the leftmost-occurrence decomposition developed here should apply to longer mesh patterns as well, since the block generating functions $A(t)$, $B(t)$, and $C(t)$ recur in every formula and no step seems to depend on the pattern having length exactly 2.
Because $A(t)$ is known explicitly, one could use these formulas to derive asymptotic estimates for the mean and variance of occurrence counts in random king permutations, a direction the paper does not pursue.
The insertion bijection used for patterns Nr. 55 and Nr. 63, replacing the minimum element $1$ by $21$ to repair a single adjacency violation, looks like a general repair operation that might be transplantable to other restricted permutation classes with a similar consecutive-difference condition.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this is a genuinely useful paper, not a routine relabeling. King permutations have a different decomposition structure than unrestricted permutations (the leftmost strong fixed point splits into blocks in K^l and K^s), so turning Kitaev-Zhang's machinery onto them takes real work. The authors deliver explicit generating functions for 22 mesh patterns of length 2, with the known king-permutation generating function A(t) as the only external input. No fitted parameters, no circularity: the derivations come from first-principles decompositions, and the consistency checks hold — set u=1 and you get A(t), set u=0 and you get the paper's own avoidance series, and the small coefficients match. That is a solid package.

The soft spot is exactly where the stress-test note points: the 'almost king' bijection in Theorem 4.6 (and its sister in 4.7) carries the (t+t^2) factor in equation (23). The proof asserts that the only non-king prefix that can arise is one whose sole violation is that A ends with b+1, and that inserting a removes that violation without creating new occurrences of the pattern. That is load-bearing, and it is asserted rather than proved. The small-n expansions do not test it, because a failure of that classification could first appear at larger n. I don't think the formulas are wrong — the same trick appears in both theorems and the stated coefficients line up — but if I were refereeing, I would ask for a proof of that classification, or at least an independent coefficient check up to n=10 or so.

Minor issue: the mesh-pattern diagrams are omitted, so you cannot audit the correspondence between pattern numbers and the schematic figures. That is an editorial shortcoming, not a mathematical one, but it makes the paper harder to check than it should be.

The six 'impossible' patterns are a trivial observation, but the authors are upfront about that, and the remaining sixteen are substantive. The paper is well-organized, the writing is clear, and the citations are appropriate. It is a modest but honest advance in a specific subfield — the kind of paper that belongs in a good combinatorics journal.

My recommendation: send it to a serious referee. The central claims look right, and the one genuinely fragile step is local and fixable. I would cite this if I worked on mesh patterns or restricted permutations, and I'd probably assign it in a reading group for graduate students learning generating function techniques. Accept with the request to tighten the almost-king argument.

Referee Report

4 major / 2 minor

Summary. This paper initiates a systematic study of distributions of short mesh patterns on king permutations. It derives bivariate generating functions E(t,u) and avoidance generating functions P(t) for 22 length-2 mesh patterns indexed by the numbering of Kitaev and Zhang, after first obtaining auxiliary series for the strong-fixed-point statistic on king permutations and two restricted classes (Theorem 2.2). Results are divided into 'trivial' cases (Section 3) and further cases (Section 4); Section 5 lists 11 patterns left open. The proofs are bijective and use decompositions of king permutations around a chosen occurrence of a pattern.

Significance. If the formulas are correct, this is a useful and fairly systematic extension of the Kitaev-Zhang census to king permutations, with explicit parameter-free generating functions. The formulas pass basic internal consistency checks: for each pattern, setting u=1 recovers A(t) and setting u=0 recovers the paper's own avoidance series P(t), and the displayed expansions agree with the small coefficients. These checks are encouraging but do not by themselves validate the bijective decompositions used to obtain the formulas.

major comments (4)

[Theorem 4.6, Eq. (23)] The proof of the avoidance formula is incomplete. The paper asserts that when an occurrence ab with a chosen as high as possible is removed, every non-king prefix AbB that can appear has as its only violation that A ends with b+1, and that inserting a into that prefix removes the violation without creating a new occurrence of p. This classification is exactly what produces the factor (t+t^2) in Eq. (23); if other non-king prefixes occur, or if the insertion creates an occurrence of p inside AbB, the formula for P(t) is wrong. Please provide a proof of this classification and of the 'no new occurrence' part.
[Theorem 4.6, after Eq. (24)] The derivation of the distribution formula uses the relation E*(t,u)=E(t,u)-tE*(t,u), where E*(t,u) is defined as the generating function for king permutations not beginning with the largest element. As written this relation is not correct: it would imply E(t,u)=(1+t)E*(t,u), but prefixing the largest element n to a king (n-1)-permutation that starts with n-1 does not produce a king permutation (for instance, 5 2 4 1 3 with n=6 gives 6 5 2 4 1 3). Since this relation is used to go from Eq. (24) to the closed form for E(t,u), the proof of the distribution formula needs repair; if the printed formula is a typo, the intended relation should be stated and proved.
[Theorem 4.7, Eq. (25)] The 'almost king permutation' case in the proof of Theorem 4.7 is another unproved load-bearing assertion. The paper claims that replacing the minimum element 1 by 21 in a non-empty p-avoiding king permutation yields a p-avoiding almost king permutation and that this introduces no new occurrence of p; this is what explains the factor t(P(t)-1) and hence the (1+t) factor in Eq. (25). Please provide a proof for this bijection, since an occurrence of p in the resulting AbB would change the avoidance formula.
[All sections (missing figures)] The manuscript as provided does not display the mesh-pattern diagrams: pattern entries such as 'Nr. 55 =' in Theorem 4.6 are followed by blank space, and Figures 1-11 are absent. Because each theorem is about a specific mesh pattern and the proofs refer to these figures, the paper is not auditable without them. Please include all pattern diagrams, or equivalent coordinate/shading descriptions, in the final version.

minor comments (2)

[Theorem 4.4] In the proof of Theorem 4.4, the phrase 'counted by C(t)-1 given by Theorem 3.4' is a cross-reference error; C(t) is introduced in Lemma 2.1, while Theorem 3.4 concerns a different pattern.
[Theorem 4.6, around Eq. (24)] The expression E*(t,u)-1 in equation (24) would benefit from an explicit specification of the constant term of E* and of how the empty permutation is treated in the decomposition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivations are self-contained given the external A(t) from Flajolet and Sedgewick.

full rationale

This paper's derivation chain is self-contained. The central input A(t) is quoted from Flajolet and Sedgewick [8], an external source, and B(t) and C(t) are derived from it by explicit decompositions in Lemma 2.1. The bivariate generating functions A(t,u), B(t,u), and C(t,u) in Theorem 2.2 are obtained by solving the functional equations (11)-(14), which come from leftmost-occurrence decompositions rather than from the target formulas. The later Theorems 3.1 through 4.8 each set up a decomposition, for example P(t)=A(t)-t(B(t)-1) in Theorem 3.3 or P(t)+(B(t)-1)(P(t)-1)(t+t^2)=A(t) in Theorem 4.6, and solve algebraically for the unknown P(t) or E(t,u); the unknown appears on both sides as a genuine combinatorial equation and is not fitted to data. Citations to [15,16] supply pattern numbering and background, but no load-bearing result is imported from those self-citations: the distribution formulas are rederived for king permutations. The 'almost king permutation' step in Theorems 4.6 and 4.7 is an unproved bijective assertion and therefore a correctness risk, but it is not circular, because the class of non-king prefixes is not defined by the generating function being computed. No fitted parameter is renamed as a prediction, and no known result is merely relabeled.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted; every formula is an explicit rational or infinite-sum expression in the known king-permutation generating function A(t). No new combinatorial objects are postulated beyond the mesh patterns themselves, which come from prior literature. The only input from outside is A(t) and the pattern definitions.

assumptions (5)

domain assumption A(t) = sum_{n>=0} n! t^n (1-t)^n/(1+t)^n is the generating function for king permutations (Eq. (1)).
Taken from Flajolet and Sedgewick [8]; every later formula in the paper is expressed in terms of this A(t) and the paper does not re-prove it.
domain assumption The 22 mesh patterns under study are exactly those numbered in [10,15,16], with the visual shading shown in the figures.
The text-only version does not render the pattern images; the combinatorial meaning of each theorem depends on those figures.
domain assumption Each decomposition around a leftmost, rightmost, or highest occurrence is bijective, and reconstructed 'almost king' permutations introduce exactly the stated number of pattern occurrences and no others (Theorems 4.6-4.8).
These are the novel bijective steps of the paper; they are argued in prose with figure references but not machine-checked.
standard math Formal power series can be manipulated coefficient-wise, including iterating functional equations as in Theorem 4.1.
Standard analytic combinatorics background; no extra assumptions.
standard math The class of king permutations is closed under reverse and complement, used repeatedly for symmetry reductions.
Immediate from the definition; used in Theorems 2.2 and 3.2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributions of mesh patterns of short lengths on king permutations." pith.science (2026). https://pith.science/paper/O5UJD67R

@misc{pith2026241118131,
  author       = {Pith},
  title        = {Pith review of: Distributions of mesh patterns of short lengths on king permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O5UJD67R}},
  note         = {Machine review of arXiv:2411.18131}
}

abstract

Br\"{a}nd\'{e}n and Claesson introduced the concept of mesh patterns in 2011, and since then, these patterns have attracted significant attention in the literature. Subsequently, in 2015, Hilmarsson \emph{et al.} initiated the first systematic study of avoidance of mesh patterns, while Kitaev and Zhang conducted the first systematic study of the distribution of mesh patterns in 2019. A permutation $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n$ in the symmetric group $S_n$ is called a king permutation if $\left| \sigma_{i+1}-\sigma_i \right| > 1$ for each $1 \leq i \leq n-1$. Riordan derived a recurrence relation for the number of such permutations in 1965. The generating function for king permutations was obtained by Flajolet and Sedgewick in 2009. In this paper, we initiate a systematic study of the distribution of mesh patterns on king permutations by finding distributions for 22 mesh patterns of short length.

Figures

Figures reproduced from arXiv: 2411.18131 by the authors.

**Figure 1.** Related to the proof of Theorem 3.4 Proof. The only possible occurrence of p can be formed by the element 1 in the leftmost position, and the largest element in the rightmost position. Any non-empty permutation σ ′ , red(σ ′ ) ∈ Ks ∩ Kℓ , formed by the elements of σ is counted by C(t) − 1 given by (3). The king permutations avoiding p are counted by P(t). To get P(t), we take all king permutations and subtract those… view at source ↗

**Figure 2.** Related to the proof of Theorem 3.5 • When B is empty, then A must be non-empty (or else, b = a + 1 and σ 6∈ K). But then to the left of b in σ we must have a non-empty permutation σ ′ ∈ Kℓ (of length at least 2). Such king permutations are counted by t [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Related to the proof of Theorem 3.6 Proof. Let us first consider king permutations containing one occurrence of p, say ab, depicted in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Related to the proof of Theorem 3.7 Proof. Suppose that a permutation σ ∈ K contains an occurrence ab of the pattern p, that is presented schematically in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

**Figure 5.** Figure 5: Related to the proof of Theorem 4.1 4 The other distributions In this section, we derive the remaining distributions in this paper. 4.1 Distribution of the pattern Nr. 16 Our next theorem establishes the avoidance and distribution of the pattern Nr. 16 = . Theorem 4.1.…

**Figure 6.** Figure 6: Related to the proof of Theorem 4.3 Theorem 4.3. Let p = , E(t, u) = P n≥0 t n P σ∈Kn u p(σ) , and P(t) be the generating function for K(p). Then, P(t) = t + 1 1 + t − t 2A2 (t) (1 + t) [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]

**Figure 7.** Figure 7: Related to the proof of Theorem 4.4 17 [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

**Figure 8.** Figure 8: Related to the proof of Theorem 4.5 formed by B can be any non-empty permutation in Ksℓ that avoids (since b is the leftmost possible). These permutations are counted by C(t, 0) − 1 given by Theorem 3.4. Finally, C can be any permutation in Ks , which is counted by B(t…

**Figure 9.** Figure 9: Related to the proof of Theorem 4.6 Proof. We claim that P(t) + (B(t) − 1)(P(t) − 1)(t + t 2 ) = A(t). (23) Indeed, each permutation σ ∈ K, counted by A(t), either avoids p (which is counted by the P(t) term in (23)), or contains at least one occurrence of p. Among all…

**Figure 10.** Figure 10: Related to the proof of Theorem 4.7 Proof. We claim that P(t) + (P(t) − 1)(B(t) − 1)(1 + t) = A(t). (25) Indeed, each permutation σ ∈ K, which is counted by the right-hand side in (25), either avoids p (which is counted by the P(t) term in (25)), or contains at least …

**Figure 11.** Figure 11: Related to the proof of Theorem 4.8 Proof. Suppose that a permutation σ ∈ K contains at least one occurrence of p, and ab in [PITH_FULL_IMAGE:figures/full_fig_p023_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Avgustinovich, S

S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Avoidance of b oxed mesh patterns on permutations, Discrete Appl. Math. , 161 (2013), 43– 51

work page 2013
[2]

Bagno, E

E. Bagno, E. Eisenberg, S. Reches, and M. Sigron, On the poset of non-attacking king permutations, Eur. J. Comb. , 87 (2020), 103119

work page 2020
[3]

Bagno, E

E. Bagno, E. Eisenberg, S. Reches, and M. Sigron, Counting king per- mutations on the cylinder, Enumer. Comb. Appl. , 2 (2022), S4PP5

work page 2022
[4]

C. Bean, B. Gudmundsson, T. K. Magnusson, and H. Ulfarsson, Algo- rithmic coincidence classiﬁcation of mesh patterns, Inf. Comput. , 292 (2023), 105014

work page 2023
[5]

Borie, On the combinatorics of quadrant marked mesh patter ns in 132-avoiding permutations, Australas

N. Borie, On the combinatorics of quadrant marked mesh patter ns in 132-avoiding permutations, Australas. J. Comb. , 64(1)(2016), 140–153

work page 2016
[6]

Br¨ and´ en and A

P. Br¨ and´ en and A. Claesson, Mesh patterns and the expansio n of per- mutation statistics as sums of permutation patterns, Electron. J. Comb., 18(2) (2011), #P5

work page 2011
[7]

Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebr

A. Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebr. Comb. , 5(6) (2022), 1257–1277. 25

work page 2022
[8]

Flajolet and R

P. Flajolet and R. Sedgewick, Analytic combinatorics , Cambridge Uni- versity Press, Cambridge, 2009

work page 2009

Show all 20 references

[9]

Han and J

B. Han and J. Zeng, Equidistributions of mesh patterns of length two and Kitaev and Zhang’s conjectures, Adv. in Appl. Math. , 127 (2021), 102149

2021
[10]

Hilmarsson, I

I. Hilmarsson, I. J´ onsd´ ottir, S. Sigurdard´ ottir, L. Vidars d´ ottir, and H. Ulfarsson, Wilf-classiﬁcation of mesh patterns of short length, Elec- tron. J. Comb. , 22(4) (2015), #P4.13

2015
[11]

Jones, S

M. Jones, S. Kitaev, and J. Remmel, Frame patterns in n-cycles, Dis- crete Math. , 338 (2015), 1197–1215

2015
[12]

Kitaev, Patterns in permutations and words , Springer, 2011

S. Kitaev, Patterns in permutations and words , Springer, 2011

2011
[13]

Kitaev and J

S. Kitaev and J. Liese, Harmonic numbers, Catalan’s triangle and mesh patterns, Discrete Math., 313 (2013), 1515–1531

2013
[14]

Kitaev and J

S. Kitaev and J. Remmel, Quadrant marked mesh patterns in alte rnating permutations, S´ eminaire Lotharingien de Combinatoire, B68a (2012)

2012
[15]

Kitaev and P

S. Kitaev and P. B. Zhang, Distributions of mesh patterns of sh ort lengths, Adv. in Appl. Math. , 110 (2019), 1–32

2019
[16]

Kitaev, P

S. Kitaev, P. B. Zhang, and X. Zhang, Distributions of several inﬁnite families of mesh patterns, Appl. Math. Comput. , 372 (2020), 124984

2020
[17]

Riordan, A recurrence for permutations without rising or fa lling suc- cessions, Ann

J. Riordan, A recurrence for permutations without rising or fa lling suc- cessions, Ann. Stat. , 36 (1965), 708–710

1965
[18]

B. E. Tenner, Coincidental pattern avoidance, J. Comb. , 4 (2013), 311– 326

2013
[19]

B. E. Tenner, Mesh patterns with superﬂuous mesh, Adv. in Appl. Math., 51 (2013), 606–618

2013
[20]

Thamrongpairoj and J

S. Thamrongpairoj and J. B. Remmel, Positional marked patter ns in permutations, Discrete Math. Theor. Comput. Sci. , 24 (2022), no. 1, 23. 26

2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Avgustinovich, S

S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Avoidance of b oxed mesh patterns on permutations, Discrete Appl. Math. , 161 (2013), 43– 51

work page 2013

[2] [2]

Bagno, E

E. Bagno, E. Eisenberg, S. Reches, and M. Sigron, On the poset of non-attacking king permutations, Eur. J. Comb. , 87 (2020), 103119

work page 2020

[3] [3]

Bagno, E

E. Bagno, E. Eisenberg, S. Reches, and M. Sigron, Counting king per- mutations on the cylinder, Enumer. Comb. Appl. , 2 (2022), S4PP5

work page 2022

[4] [4]

C. Bean, B. Gudmundsson, T. K. Magnusson, and H. Ulfarsson, Algo- rithmic coincidence classiﬁcation of mesh patterns, Inf. Comput. , 292 (2023), 105014

work page 2023

[5] [5]

Borie, On the combinatorics of quadrant marked mesh patter ns in 132-avoiding permutations, Australas

N. Borie, On the combinatorics of quadrant marked mesh patter ns in 132-avoiding permutations, Australas. J. Comb. , 64(1)(2016), 140–153

work page 2016

[6] [6]

Br¨ and´ en and A

P. Br¨ and´ en and A. Claesson, Mesh patterns and the expansio n of per- mutation statistics as sums of permutation patterns, Electron. J. Comb., 18(2) (2011), #P5

work page 2011

[7] [7]

Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebr

A. Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebr. Comb. , 5(6) (2022), 1257–1277. 25

work page 2022

[8] [8]

Flajolet and R

P. Flajolet and R. Sedgewick, Analytic combinatorics , Cambridge Uni- versity Press, Cambridge, 2009

work page 2009