REVIEW 6 minor 8 references
Counting up-up-or-down-down permutations
T0 review · 0 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper proves a closed bivariate exponential generating function for up-up-or-down-down permutations refined by last entry.
desk verdict A clean, self-contained answer to Knuth's refined last-entry question; the bivariate EGF is genuinely new and the proof checks out line by line, with only minor editorial blemishes. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is Lemma 5, a Seidel-array lemma: a two-index array satisfying $a_{i+1,j}-a_{i,j+1}=2a_{i,j}$ together with the skew-symmetry $a_{j,i}=(-1)^{i+j}a_{i,j}$ has bivariate exponential generating function $e^{x-y}B(x+y)$ with $B$ an even power series. The proof constructs the generating function $P$, shows from a second-difference identity that $(\partial_x-\partial_y)^2P=4P$, sets $Q=\tfrac12(\partial_x-\partial_y)P$, and forms $R=P+Q$ so that $(\partial_x-\partial_y)R=2R$. Lemma 5(b) then forces $R=e^{x-y}B(x+y)$ with $B$ even, and $B$ is determined from the boundary relation $P(x,0)=1+xQ(x,0)$, which follows from Lemma 4, the identity $(n-1)p_n(n)=np_n(n-1)$.
What would settle it
Compute $p_n(k)$ from the recurrence $p_{n+1}(k)=\sum_{j=-n}^{n}|j-k|p_n(j)$ up to, say, $n=10$, and compare each value with the coefficient of $x^{n+k}y^{n-k}/((n+k)!(n-k)!)$ in the right-hand side of (4); any discrepancy at any $n$ and $k$ refutes the identity.
Extended reading notes
Core claim
The paper's central claim is identity (4): $$\sum_{n=0}^{\infty}\sum_{k=-n}^{n} p_n(k)\, \frac{$x^{{n+k}}$}{(n+k)!}\frac{$y^{{n-k}}$}{(n-k)!} = \frac{\$\cosh$\!\left(\frac{1}{\sqrt{2}}(x-y)\right)}{\$\cosh$\!\left(\frac{1}{\sqrt{2}}(x+y)\right) - \frac{1}{\sqrt{2}}(x+y)\,\$\sinh$\!\left(\frac{1}{\sqrt{2}}(x+y)\right)},$$ where $p_n(k)$ is the number of up-up-or-down-down permutations of the set $\{-n,-n+1,\dots,n\}$ whose last entry is $k$. The left side is the natural two-variable exponential generating function, with a term of length $2n+1$ and last entry $k$ contributing exponents $n+k$ and $n-k$ in $x$ and $y$. The right side is a closed rational expression in hyperbolic functions with no free parameters. The theorem therefore gives a closed-form solution to the recurrence $p_{n+1}(k)=\sum_{j=-n}^{n}|j-k|\,p_n(j)$, resolving the refined enumeration.
Load-bearing premise
The whole argument rests on the symmetry $p_n(-k)=p_n(k)$ holding for every $n$, since that symmetry is what lets the Seidel-array lemma rewrite the generating function as $e^{x-y}B(x+y)$; if it ever failed, the closed form would not follow.
Editorial extensions
If this is right
- Setting $y=0$ in (4) gives the exponential generating function for the boundary counts $p_n(n)$; subtracting the $n=0$ term and doubling recovers the generating function for the even-length counts and, after division by $x$, the known one-variable formula (1).
- Summing over all last entries through a beta-integral trick reproduces the known odd-length generating function (1) independently of the earlier derivations, providing a consistency check on the bivariate identity.
- The bivariate rational form supplies the complete last-entry distribution at every $n$ at once, rather than requiring the recurrence to be solved step by step.
- The same two-variable exponential generating-function encoding, treating positive and negative labels as two sorts with the final entry distinguished, matches the Entringer-number and Eulerian-polynomial examples discussed in Section 3, pointing to a general method for fixed-last-entry permutation counts.
Reading between the lines
- The proof uses only a diagonal boundary case of the Seidel-array symmetry, so any permutation class whose last-entry counts satisfy the same recurrence plus a sign symmetry would inherit the same closed-form structure; testing another recurrence with the kernel $|j-k|$ and a different boundary condition would reveal the method's scope.
- The denominator $\cosh(x+y)-(x+y)\sinh(x+y)$ is the same function appearing in the one-variable generating function, so a combinatorial interpretation of this denominator would likely turn the bivariate formula into a direct bijective proof of the refined counts.
- Because the formula expresses $p_n(k)$ as one coefficient of a closed rational function, it should be possible to derive asymptotic profiles for the last-entry distribution as $n$ grows with $k/n$ fixed, which the paper does not attempt.
- The recurrence $p_{n+1}(k)=\sum_j |j-k|p_n(j)$ resembles a discrete heat-kernel or absolute-value walk, suggesting the same differential-equation-plus-symmetry method may transfer to other walks with nonlocal transition weights, though the paper does not explore that connection.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper answers a question of Donald Knuth by deriving the bivariate exponential generating function for p_n(k), the number of up-up-or-down-down permutations of {-n,...,n} whose last entry is k. The proof begins with Knuth's recurrence (2), which is proved combinatorially in Lemma 1. The recurrence is transformed into a system of difference relations (Lemmas 2-4) and then into a PDE via a Seidel-array lemma (Lemma 5); the PDE is solved with a boundary relation to obtain the closed form (4). The paper also shows how the known one-variable generating function (1) follows from (4) by specializing or integrating.
Significance. The central claim is well-supported. The derivation is elementary, self-contained, and does not rely on unproved inputs: the recurrence is proved, not assumed, and the final expression contains no fitted parameters. The bivariate EGF (4) is an explicit closed-form solution to a refined counting problem and specializes to the known univariate generating function. The Seidel-array lemma is a clean tool that may be useful beyond this example. The proof has been checked for consistency, and the most delicate step, the application of Lemma 5(b) to R=P+Q, is justified.
minor comments (6)
- [Introduction, Eq. (1) and Section 3] Equation (1) has an index shift: with the stated definition of U_n as the number of permutations of {1,...,2n-1}, the sum should be \sum_{n\ge1} U_n x^{2n-1}/(2n-1)! rather than \sum_{n\ge0} U_n x^{2n+1}/(2n+1)!; as written, the coefficient of x^3/3! is U_1=2, contradicting the definition and the relation p_n(n)=nU_n used in Section 3. The subsequent statement that 'Dividing by x gives (1)' should be adjusted to match the corrected index.
- [Introduction, Eq. (1) expansion] In the expansion following (1), the x^11 term is omitted; the series jumps from x^9 to x^13 without the n=5 term, so the displayed expansion is incomplete.
- [Introduction, definition of valley] In the introduction, the definition of a valley contains a typo: 'a_{i-1}>a_i<a_i' should read 'a_{i-1}>a_i<a_{i+1}'.
- [Table of p_n(k)] The table of p_n(k) values is misaligned in the typeset version; the row for n=1 should display the values for k=-1,0,1 as 1,0,1.
- [Lemma 2] Lemma 2's proof is only one sentence; a short indication of the induction step (for instance, the substitution j\mapsto -j in (2)) would improve readability.
- [Theorem proof, Lemma 5(b) application] In the proof of the theorem, the step 'It is easy to check that since P(-y,-x)=P(x,y), we have Q(-y,-x)=Q(x,y)' is correct but terse; spelling out the differentiation would help the reader verify the hypothesis of Lemma 5(b).
Circularity Check
No significant circularity: the bivariate exponential generating function is derived from a recurrence that is proved from the combinatorial definition, and the known one-variable generating function is a consequence rather than an input.
full rationale
The paper's central derivation is self-contained. Knuth's recurrence (2) is not assumed as a black box: Lemma 1 proves it directly from the combinatorial definition of up-up-or-down-down permutations. Lemmas 2, 3, and 4 are all derived from recurrence (2) by direct summation and do not presuppose the final generating function. Lemma 5 is a general fact about Seidel arrays, proved in full within the paper using uniqueness of formal power series solutions to the differential equation. The main theorem constructs P, Q, and R, verifies the hypotheses of Lemma 5(b): L(R)=2R holds by construction from L^2(P)=4P, which is Lemma 3 recast in generating-function form, and the symmetry condition R(y,x)=R(-x,-y) follows from Lemma 2's symmetry p_n(-k)=p_n(k) together with the parity of total degree in P. The unknown series B(x) is then determined from the boundary values P(x,0) and Q(x,0), using Lemma 4 to simplify xQ(x,0). No parameter is fitted to the data being predicted, no conclusion is assumed, and no load-bearing self-citation is used. The paper cites external works for the previously known one-variable generating function (1), but (1) is not an input to the proof; it is derived from (4) in the further-remarks section. Overall, the derivation chain is internally consistent and independently verifiable from the stated recurrence and definitions.
Assumptions & free parameters
assumptions (2)
- standard math Formal power series over a field are determined by initial values, and the differential equation dR/dx - dR/dy = 2R has a unique formal solution given R(x,0).
- standard math Exponential generating function coefficient extraction and two-variable EGF manipulation are valid for the counts p_n(k).
Cite this review
Pith. "Pith review of Counting up-up-or-down-down permutations." pith.science (2026). https://pith.science/paper/NSPNUOLM
@misc{pith2026241116113,
author = {Pith},
title = {Pith review of: Counting up-up-or-down-down permutations},
year = {2026},
howpublished = {\url{https://pith.science/paper/NSPNUOLM}},
note = {Machine review of arXiv:2411.16113}
}
abstract
Answering a question of Donald Knuth, we find the bivariate exponential generating function for "up-up-or-down-down'' permutations of odd length according to their last entry. An up-up-or-down-down permutation is a permutation $a_1a_2\cdots a_n$ satisfying $a_{2i-1}<a_{2i}$ if and only if $a_{2i}<a_{2i+1}$ for $1\le i <n/2$. Equivalently, an up-up-or-down-down permutation is one in which every peak and every valley is odd.
Reference graph
Works this paper leans on
-
[1]
Nicolas Basset, Counting and generating permutations in regular classes , Algorithmica 76 (2016), no. 4, 989–1034
work page 2016
-
[2]
Dominique Dumont, Matrices d’Euler-Seidel, S´ eminaire Lotharingien de Combinatoire 5 (1981), B05c, 16 pp
work page 1981
-
[3]
Dominique Dumont and G´ erard Viennot, A combinatorial interpretation of the Seidel generation of Genocchi numbers, Ann. Discrete Math. 6 (1980), 77–87. COUNTING UP-UP-OR-DOWN-DOWN PERMUTATIONS 8
work page 1980
-
[4]
Don Knuth, Whirlpool permutations, https://www-cs-faculty.stanford.edu/ ~knuth/papers/whirlpool.pdf, 2020
work page 2020
-
[5]
Knuth, The Art of Computer Programming, Volume 4, Pre-Fascicle 7a
Donald E. Knuth, The Art of Computer Programming, Volume 4, Pre-Fascicle 7a. A Draft of Section 7.2.2.3: Constraint Satisfaction , Addison-Wesley, 2024
work page 2024
-
[6]
Michael La Croix, A combinatorial proof of a result of Gessel and Greene , Discrete Math. 306 (2006), no. 18, 2251–2256
work page 2006
-
[7]
N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences , published electronically at https://oeis.org, 2024
work page 2024
-
[8]
Yan Zhuang, Counting permutations by runs , J. Combin. Theory Ser. A 142 (2016), 147–176. Department of Mathematics, Brandeis University, W altham, MA 02453 Email address : gessel@brandeis.edu
work page 2016
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.