Permutation descents, Eulerian numbers, and the cd-index
A Rocq / MathComp formalization of Stanley EC1 §1.4 + §1.6

5.3 Stanley Corollary 1.6.5 — the headline

Corollary 5.4 Stanley Cor 1.6.5: alternating maximizes \(\beta \)

Stanley’s statement (EC1 p. 61):

Let \(S \subseteq [n-1]\). Then \(\beta _n(S) \leq E_n\), with equality if and only if \(S = \{ 1, 3, 5, \dots \} \cap [n-1]\) or \(S = \{ 2, 4, 6, \dots \} \cap [n-1]\).

Here \(E_n\) is the \(n\)-th Euler number, realized as \(\beta (\mathrm{Alt}_n)\).

Our formalization, in contrapositive form: for \(n \geq 2\) and \(D \subseteq \{ 0, \dots , n-1\} \),

\[ \neg \, (D \text{ set-alternating}) \; \Longrightarrow \; \beta (D) {\lt} \beta (\mathrm{Alt}_n). \]
Proof

Reduce to \(n = m + 2\). By 4.13, \(\omega (D) \subsetneq \mathrm{set\_ T} = \omega (\mathrm{Alt}_n)\) (the second equality by 4.12). Apply 5.3: the strict inequality follows.

This exactly mirrors Stanley’s “Proof: Immediate from Proposition 1.6.4 and equation (1.65)” (p. 61).

The “\(S = \{ 2, 4, 6, \dots \} \)” alternative in Stanley’s statement reduces to the complementation symmetry already proved at the \(\beta \)-level (, see also 1.15): the two alternating descent sets have equal \(\beta \).