Revisiting $q$-Derangement Numbers via Decorated Permutations

Kathy Q. Ji

REVIEW 1 major objections 4 minor 13 references

Revisiting $q$-Derangement Numbers via Decorated Permutations

T0 review · 1 major / 4 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read A sign-reversing involution on decorated permutations proves the q-derangement formula without binomial inversion.

desk verdict Clean inversion-free combinatorial proof of the classical q-derangement formula via decorated permutations; the only soft spot is a sketched multi-case involution. read the letter →

arxiv 2607.04798 v1 pith:D6XAZWE6 submitted 2026-07-06 math.CO

Kathy Q. Ji This is my paper · ORCID

classification math.CO MSC 05A3005A1505A19

keywords derangementsdescentsetmajorindexdecoratedpermutationsinvolutionshuffleq-analogues

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

The paper gives a direct combinatorial proof of the Gessel–Reutenauer–Wachs formula for q-derangement numbers, working entirely inside the model of decorated permutations (ordinary permutations whose fixed points may carry a sign). It first evaluates the major-index generating function on the subset of decorated permutations that have exactly k signed fixed points, obtaining a simple closed form involving a q-binomial coefficient and a quadratic power of q. It then constructs a sign-reversing, descent-set-preserving involution on every decorated permutation that still has at least one fixed point. After the involution cancels all such terms, only ordinary derangements remain and the classical formula follows at once. The construction answers a question of Chen by showing that the signed-fixed-point model already used for ordinary derangements extends cleanly to the q-analogue, without any appeal to inversion formulas.

What carries the argument

The involution Ψ, defined after mapping a decorated permutation to a shuffle of a reduced derangement word and a signed fixed-point word: the leftmost signed fixed-point letter is toggled and, when necessary, slid across a maximal run of letters in a prescribed open interval so that the descent set is left unchanged; applying the same rule twice recovers the original permutation.

What would settle it

Exhibit a single decorated permutation on which the sliding construction either changes the descent set or fails to invert itself; any such counter-example for n greater than 3 would refute the involution.

Watch

Extended reading notes

Core claim

There is a sign-reversing and descent-set-preserving involution on the set of all decorated permutations that possess at least one fixed point (signed or unsigned). Combined with the closed major-index formula for decorated permutations with a fixed number of signed fixed points, the involution immediately yields the Gessel–Reutenauer–Wachs identity for the q-derangement numbers, without invoking q-binomial inversion.

Load-bearing premise

The multi-case sliding rule for the distinguished letter always preserves the descent set and is an involution, a claim supported only by local adjacency checks, one worked example, and a table for n=3.

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

This note answers Chen’s question with a direct combinatorial proof of the Gessel–Reutenauer–Wachs formula that never invokes q-binomial inversion. That is the real contribution: it stays inside decorated permutations (Postnikov’s 2-arrangements), proves the fixed-signed-fixed-point major-index generating function by a short shuffle argument (MacMahon + Garsia–Gessel), then cancels everything with a sign-reversing, descent-set-preserving involution on the non-derangements.

Section 2 is clean and short. The bijection that turns a decorated permutation with k signed fixed points into a shuffle of the reverse word δ_k with an ordinary permutation of the remaining letters is natural, and the generating function falls out immediately. That half is solid.

Section 3 extends Wachs’ map ψ_n to the signed setting and then defines the involution Ψ by flipping the sign of the distinguished letter γ_1 and sliding it across a maximal interval of intermediate letters so that descents are preserved. The construction is elementary and the maximality conditions are designed so that only adjacent pairs involving the moved letter can change status; those pairs keep the same descent relation under the total order (1.9). The paper asserts this by “direct comparison,” gives one worked example and the full n=3 table, but does not write out a uniform invariant or exhaustive local check. That is a genuine verification gap, yet it is modest: the argument is finite, local, and fully elementary. Nothing else in the paper is load-bearing or circular.

The result is classical, so the significance is technical rather than conceptual, but the note does exactly what it claims and places the argument in a language that people working on totally nonnegative Grassmannians and k-arrangements already use. Anyone who cares about combinatorial proofs of q-identities or about decorated-permutation statistics will get value from it. I would send it to a referee; the gap is fixable by a short expansion of the case analysis or a computer check of small n. Worth engaging if that is your area.

Referee Report

1 major / 4 minor

Summary. The paper gives a direct combinatorial proof of the Gessel–Reutenauer–Wachs formula for the q-derangement numbers dn(q) in the language of decorated permutations (Postnikov’s 2-colored fixed points). It first establishes a closed major-index generating function for the set En,k of decorated permutations with exactly k signed fixed points (Theorem 1.4 / (1.10)), via a descent-preserving bijection to shuffles of a fixed decreasing word with an ordinary permutation and an application of MacMahon and Garsia–Gessel. It then constructs a sign-reversing, descent-set-preserving involution on the complementary set Gn of decorated permutations that possess at least one fixed point (signed or unsigned), thereby proving that the alternating major-index sum over Gn vanishes (Theorem 1.5 / (1.11)). Combining the two identities immediately yields the desired formula without q-binomial inversion, answering a question of Chen. The involution is obtained by extending Wachs’ reduction map ψn to the signed setting and then sliding a distinguished signed letter across a maximal interval so that descents are preserved.

Significance. The result supplies a genuinely direct combinatorial explanation of the Gessel–Reutenauer–Wachs formula that stays inside Chen’s signed-fixed-point model and avoids the usual q-binomial inversion step. The generating-function half (Section 2) is short, transparent and rests only on classical identities. The involution half answers an explicit open question of Chen and is of independent interest as a descent-preserving sign-reversing involution on decorated permutations. The manuscript is a concise research note whose main contribution is the construction itself; if the involution is verified, the paper cleanly closes a natural combinatorial gap.

major comments (1)

Section 3, Cases 1(a)–2(c): the multi-case sliding rule that defines the involution Ψ is asserted to preserve the descent set (“a direct comparison of adjacent letters shows Des(τ̃)=Des(π̃)”) and to be an involution, yet the manuscript supplies only a single worked example and the n=3 table. Because the rule is the sole load-bearing ingredient of Theorem 1.5, a short uniform argument (or an exhaustive local check of the finitely many adjacent-pair configurations that can change) should be written out so that a reader can verify the claim without reconstructing the case analysis.

minor comments (4)

The abstract and introduction mention that the involution was discovered through human–AI collaboration; a brief remark on how the collaboration was used (e.g., case enumeration versus verification) would be useful for readers interested in the methodology.
Notation for signed fixed points is occasionally inconsistent (i versus s(σ)+1 versus the bar notation of the order (1.9)); a single convention should be fixed early and used throughout.
In the definition of ψn the phrase “its ith smallest (in absolute value) fixed point” is slightly ambiguous when both signed and unsigned fixed points are present; a clarifying parenthetical would help.
The table for G3 is helpful; adding one further medium-size example (say n=4 or 5) that exercises a non-trivial sliding case would strengthen the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a self-contained combinatorial construction that invokes only independent external identities (MacMahon, Garsia–Gessel, Wachs) and does not reduce the target formula to a fit or a tautology.

full rationale

The paper proves the Gessel–Reutenauer–Wachs formula by two independent combinatorial ingredients: (i) a descent-preserving bijection φ that reduces the major-index generating function over En,k to the Garsia–Gessel shuffle formula plus MacMahon’s formula (Theorem 1.4 / §2), and (ii) an explicit sign-reversing, descent-set-preserving involution Ψ on Gn constructed by extending Wachs’ map ψn and sliding a distinguished letter across a maximal interval of intermediate values (Theorem 1.5 / §3). Both steps are constructive and elementary; they cite only classical external results whose statements do not presuppose the q-derangement formula. The embedding of ordinary derangements inside decorated permutations is definitional, not circular. There are no fitted parameters, no load-bearing self-citations of uniqueness theorems, and no renaming of a known empirical pattern. The only soft spot is the verification gap on the multi-case sliding rule, which is a correctness concern, not circularity. Score 0 is therefore the honest finding.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper is pure enumerative combinatorics. It relies only on standard definitions (permutations, major index, q-factorials, q-binomial coefficients) and two classical external theorems (MacMahon’s major-index formula and the Garsia–Gessel shuffle formula). No free parameters are fitted, and the only new combinatorial objects are the involution Ψ and the signed extension of Wachs’ map, both of which are explicitly constructed rather than postulated.

assumptions (4)

standard math MacMahon’s formula: sum of q^maj(π) over Sn equals [n]_q!
Invoked in the proof of Theorem 1.4 (Section 2) to evaluate the generating function after the shuffle identity is applied.
standard math Garsia–Gessel shuffle theorem: the major-index generating function of shuffles of two disjoint permutations factors as a q-binomial times the product of the individual major indices.
Used both for the generating-function identity (1.7) and inside the proof of Theorem 1.4.
standard math Wachs’ unsigned map that rearranges a permutation according to subcedants, fixed points and excedants preserves the descent set.
Extended to the signed setting in Lemma 3.2; the paper claims the signed extension inherits the descent-preservation property.
domain assumption Decorated permutations are words over the totally ordered alphabet of barred and unbarred letters, and the descent set is defined with respect to that order.
Standard definition following Postnikov/Corteel/Williams; used throughout to define maj on En.

invented entities (1)

The multi-case sign-reversing involution Ψ on decorated permutations with a fixed derangement part
purpose: To cancel all non-derangement terms while preserving the descent set, thereby proving the alternating sum vanishes.
Explicitly constructed in Section 3 by flipping the sign of a distinguished letter and sliding it across a maximal intermediate run; independent evidence is the small-n verification table, but no external falsifiable prediction is claimed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Revisiting $q$-Derangement Numbers via Decorated Permutations." pith.science (2026). https://pith.science/paper/D6XAZWE6

@misc{pith2026260704798,
  author       = {Pith},
  title        = {Pith review of: Revisiting $q$-Derangement Numbers via Decorated Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D6XAZWE6}},
  note         = {Machine review of arXiv:2607.04798}
}

abstract

This note aims to provide a direct combinatorial proof of the Gessel--Reutenauer--Wachs formula for $q$-derangement numbers in the setting of decorated permutations, without using the $q$-binomial inversion formula. Decorated permutations, introduced by Postnikov in his study of the totally nonnegative Grassmannian, provide a natural framework for Chen's signed fixed-point model. Our proof is based on a major-index generating function for decorated permutations with a fixed number of signed fixed points, together with a sign-reversing and descent-set-preserving involution, thereby answering a question raised by Chen. This involution was discovered through human--AI collaboration.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 1 linked inside Pith

[1]

Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979

M. Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979

1979
[2]

Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976

G.E. Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976

1976
[3]

Blitvić and E

N. Blitvić and E. Steingrímsson, Permutations, moments, measures, Trans. Amer. Math. Soc. 374(8) (2021), 5473–5508. 9

2021
[4]

W. Y. C. Chen, Some observations and questions via Maple, talk at AlCoVE: an Algebraic Combinatorics Virtual Expedition, virtual conference, June 8–9, 2026

2026
[5]

W. Y. C. Chen and D. Xu, Labeled partitions and theq-derangement numbers, SIAM J. Discrete Math. 22(3) (2008) 1099–1104

2008
[6]

Corteel, Crossings and alignments of permutations, Adv

S. Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38 (2007), no. 2, 149–163

2007
[7]

I. M. Gessel and C. Reutenauer, Counting permutations with given cycle struc- ture and descent set, J. Combin. Theory Ser. A 64 (1993) 189–215

1993
[8]

A. M. Garsia and I. M. Gessel, Permutation statistics and partitions, Adv. in Math. 31 (1979) 288–305

1979

Show all 13 references

[9]

S. Fu, G. -N. Han and Z. Lin,k-Arrangements, statistics, and patterns, SIAM J. Discrete Math., 34 (2020) 1830–1853

2020
[10]

Postnikov, Total positivity, Grassmannians, and networks, preprint, 2006, arXiv:math/0609764

A. Postnikov, Total positivity, Grassmannians, and networks, preprint, 2006, arXiv:math/0609764

2006 arXiv
[11]

Stanley,Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 2012

Richard P. Stanley,Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 2012

2012
[12]

M. L. Wachs, Onq-derangement numbers, Proc. Amer. Math. Soc. 106 (1989), no. 1, 273–278

1989
[13]

L. K. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319–342. 10

2005

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.

[1] [1]

Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979

M. Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979

1979

[2] [2]

Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976

G.E. Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976

1976

[3] [3]

Blitvić and E

N. Blitvić and E. Steingrímsson, Permutations, moments, measures, Trans. Amer. Math. Soc. 374(8) (2021), 5473–5508. 9

2021

[4] [4]

W. Y. C. Chen, Some observations and questions via Maple, talk at AlCoVE: an Algebraic Combinatorics Virtual Expedition, virtual conference, June 8–9, 2026

2026

[5] [5]

W. Y. C. Chen and D. Xu, Labeled partitions and theq-derangement numbers, SIAM J. Discrete Math. 22(3) (2008) 1099–1104

2008

[6] [6]

Corteel, Crossings and alignments of permutations, Adv

S. Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38 (2007), no. 2, 149–163

2007

[7] [7]

I. M. Gessel and C. Reutenauer, Counting permutations with given cycle struc- ture and descent set, J. Combin. Theory Ser. A 64 (1993) 189–215

1993

[8] [8]

A. M. Garsia and I. M. Gessel, Permutation statistics and partitions, Adv. in Math. 31 (1979) 288–305

1979