Let [n]=1,…,n and let S_n be the set of permutations of [n]. A permutation a_1… a_n is alternating if a_1>a_2 a_4 a_3 …. Let d_k(n) and d_k^(n) denote, respectively, the numbers of alternating and reverse alternating permutations in S_n with k fixed points. Let D_n be the number of derangements in S_n, that is, permutations with no fixed points. Stanley's conjecture. For n≥4 and n≥5, respectively, d_lceil n/2 rceil(n)=D_lfloor n/2 rfloor, and d^_lceil (n+1)/2 rceil(n)=D_lfloor (n-1)/2 rfloor. This conjecture asserts an equidistribution between derangements and alternating or reverse alternating permutations having the maximal possible number of fixed points. The source presents it as Stanley's conjecture; no resolution status is supplied here.

Stanley's equidistribution conjecture for alternating permutations and derangements

About 19 years old · traced to 2007

Let $[n]=\{1,\dots,n\}$ and let $S_n$ be the set of permutations of $[n]$ . A permutation $a_1\cdots a_n$ is alternating if $a_1>a_2<a_3>a_4<\dots$ , and it is reverse alternating if $a_1<a_2>a_3<a_4>\dots$ . Let $d_k(n)$ and $d_k^*(n)$ denote, respectively, the numbers of alternating and reverse alternating permutations in $S_n$ with $k$ fixed points. Let $D_n$ be the number of derangements in $S_n$ , that is, permutations with no fixed points.

Stanley's conjecture. For $n\geq4$ and $n\geq5$ , respectively,

d_{\lceil n/2\rceil}(n)=D_{\lfloor n/2\rfloor},

and

d^*_{\lceil (n+1)/2\rceil}(n)=D_{\lfloor (n-1)/2\rfloor}.

This conjecture asserts an equidistribution between derangements and alternating or reverse alternating permutations having the maximal possible number of fixed points. The source presents it as Stanley's conjecture; no resolution status is supplied here.

References

Primary source

Robin Chapman and Lauren K. Williams, “A conjecture of Stanley on alternating permutations”, arXiv:math/0702808 (2007).

Posted 1 month ago

Progress summary

Refreshed 4 weeks ago

Claimed solved

A 2007 paper gives a bijective proof of both identities, and later sources treat the conjecture as settled, although this report has not independently verified the proof.

Stanley’s conjecture equates derangements with alternating and reverse alternating permutations having the maximum possible number of fixed points. No date for Stanley’s original formulation is supplied.

May 18, 2007 bijective proof

Chapman and Williams’s paper, whose arXiv version is dated May 18, 2007, claims two bijective proofs. It establishes $d_m(2m)=D_m$ and $d^*_{m+1}(2m)=D_{m-1}$ , together with $d_m(2m-1)=d^*_m(2m-1)=D_{m-1}$ ; these identities imply both formulas in the problem. Later work cites the result as established.

Community submission (unverified) — September 8, 2026

A submitted note identifies the result with Chapman and Williams, Electronic Journal of Combinatorics 14(1) (2007), paper N16, and gives the generating-function interpretation $\sum_{m\ge0}d_m(2m)z^m/m!=e^{-z}/(1-z)$ . This interpretation is not independently assessed here.

Current status (as of September 2026): Both conjectured identities are claimed as proved by Chapman and Williams and are treated as established in later sources, but this automated report records the resolution as unverified.

Sources

ProofAI-assistedChapman and Williams proved the conjecture in EJC 14(1) (2007), #N16 (arXiv:math/0702808), Theorems 2-3. Their bijection compresses extremal alternating permutations to derangements, giving SET(CYC_{>=2}(Z)) and the compressed-size EGF exp(-z)/(1-z). This contribution records the published resolution, not a new proof.See full solutionHide full solution

This conjecture is already proved by Robin Chapman and Lauren K. Williams in A Conjecture of Stanley on Alternating Permutations, Electronic Journal of Combinatorics 14(1) (2007), #N16, DOI 10.37236/1017; arXiv:math/0702808.

Their Theorem 2 proves

d_m(2m)=D_m \qquad(m\ge0),

and their Theorem 3 proves

d^*_{m+1}(2m)=D_{m-1},\qquad d_m(2m-1)=d_m^*(2m-1)=D_{m-1}\qquad(m\ge1).

Together these imply both identities in the problem, with the stated ranges. Thus the entry should record the conjecture as resolved, rather than leave its resolution status unspecified.

There is also a useful symbolic-method interpretation. In a down-up permutation of [2m] with m fixed points, each pair {2i-1,2i} has exactly one moved position. The Chapman--Williams bijection compresses these moved positions to a derangement of [m]. On the compressed labels, the resulting class is SET(CYC_{>=2}(Z)). Therefore

\sum_{m\ge0}d_m(2m)\frac{z^m}{m!} =\exp\!\left(\sum_{r\ge2}\frac{z^r}{r}\right) =\frac{e^{-z}}{1-z}.

Here z marks the number of compressed pairs, not the original permutation length.

This contribution records the existing published resolution and its generating-function interpretation; it does not claim a new proof or a new solution.