{"id":"8dd82691-806f-4209-a0e0-3be0c0610f09","arxiv_id":"2411.16113","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An explicit bivariate exponential generating function is derived for the number of up-up-or-down-down permutations of odd length with a fixed last entry.","lead":"This paper derives a two-variable exponential generating function that counts up-up-or-down-down permutations by their final entry, answering a question Donald Knuth posed. The formula makes the refined counts p_n(k) directly extractable as coefficients.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the proof of the bivariate EGF (4) is internally consistent and the key Lemma 5(b) symmetry hypothesis for R=P+Q holds.","rationale":"The paper gives a self-contained proof of a bivariate EGF solving Knuth's recurrence. I traced the argument: Lemma 1 verifies the recurrence; Lemmas 2-4 are straightforward and correct; Lemma 5 is a standard Seidel-array argument applied properly to R=P+Q. The only step that is terse is the claimed equivalence between Lemma 3 and L^2(P)=4P, but a direct coefficient extraction confirms it. The reader's weakest assumption correctly identifies the Lemma 5(b) symmetry condition as the pivotal point; I verified that P(-y,-x)=P(x,y) plus the definition of Q gives R(y,x)=R(-x,-y), so the hypothesis is satisfied. Small-n table values match the formula. No internal inconsistency or unsupported leap remains, so the ACCEPT verdict is appropriate.","tokens_in":6036,"tokens_out":20688,"duration_ms":160389,"concrete_test":"Run a symbolic check: compute p_n(k) from recurrence (2) for 0<=n<=8, expand the RHS of (4) in x and y, and compare the coefficient of x^{n+k} y^{n-k}/((n+k)!(n-k)!) with p_n(k). This tests the full chain Lemma 1 through Lemma 5, including the L^2(P)=4P step and the determination of B(x).","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the derivation line by line, I find no load-bearing concern. The most delicate step is the application of Lemma 5(b) to R=P+Q. The hypotheses are met: L(R)=2R by construction, and the needed symmetry R(y,x)=R(-x,-y) follows because P has only even total degree and p_n(-k)=p_n(k) gives P(-y,-x)=P(x,y); differentiating this identity gives Q(-y,-x)=Q(x,y). The paper's terse statement that Lemma 3 is equivalent to L^2(P)=4P is correct: extracting the degree-2(n-1) coefficient of L^2(P) gives 2 times the second difference of p_n, and Lemma 3 identifies this with 4p_{n-1}, so L^2(P)=4P. Lemma 2 and Lemma 4 also check out. The closed form therefore follows.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6246,"tokens_out":27427,"duration_ms":200168,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Introduction, Eq. (1) and Section 3"},{"comment":"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.","section":"Introduction, Eq. (1) expansion"},{"comment":"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}'.","section":"Introduction, definition of valley"},{"comment":"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.","section":"Table of p_n(k)"},{"comment":"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.","section":"Lemma 2"},{"comment":"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).","section":"Theorem proof, Lemma 5(b) application"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a short, elegant note whose main theorem is sound and well-proved. The only substantive defects are presentational: the index error in equation (1) and a few typos. These should be fixed before publication, but they do not affect the validity of the bivariate generating function (4). The paper is a good fit for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort version: the paper answers Knuth's question with an explicit bivariate EGF, and the proof is clean and checkable. I read the reader's report and the stress-test note; both are right. This is a genuine new result: the one-variable EGF (1) and Knuth's recurrence (2) were known, but the two-variable EGF (4) with last entry fixed is not in those references and is derived here from first principles.\n\nWhat the paper does well: Lemma 1 proves Knuth's recurrence from the combinatorial definition rather than assuming it. Lemma 3 then converts the second difference into the PDE L^2(P)=4P, and Lemma 5 is a tidy Seidel-array identity that does the heavy lifting. The boundary argument using Lemma 4 to get P(x,0)=1+xQ(x,0) is neat, and the derivation of (1) as a corollary is a nice sanity check. The remark on why a bivariate EGF rather than a Laurent-polynomial EGF is useful is sensible and the two examples (Entringer numbers and Eulerian polynomials) are well chosen.\n\nSoft spots: they are minor. The displayed expansion after (1) skips the x^11 term; the text says 'then' where it means 'than' once. In the proof of the Theorem, the claim that Lemma 3 is equivalent to L^2(P)=4P is asserted without intermediate steps; it is correct, but a referee might ask for a line or two. The proof of Lemma 5(b) also deserves a slightly fuller statement about the parity splitting, though it is sound. None of this touches the central argument.\n\nThe citation pattern looks right: La Croix, Zhuang, Knuth and Basset for (1), Dumont/Viennot for Seidel arrays, and no missing reference leaps out. The paper is self-contained modulo standard generating-function technique.\n\nWho is this for: enumerative combinatorists working on permutation statistics and Seidel arrays, and anyone interested in Knuth's whirlpool problem. It is not a broad-impact paper, but it is a correct, clean solution to a specific question. It should get a serious referee; the expected outcome is acceptance with minor editorial fixes.\n\nRecommendation: send it to review.","headline":"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.","tokens_in":6746,"tokens_out":6064,"would_cite":true,"duration_ms":48962,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a closed bivariate exponential generating function for up-up-or-down-down permutations refined by last entry.","keywords":["up-up-or-down-down permutations","bivariate exponential generating function","last-entry statistics","Seidel arrays","whirlpool permutations","hyperbolic generating function","permutation enumeration"],"falsifier":"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.","tokens_in":5868,"feed_emoji":"🔢","tokens_out":8096,"duration_ms":72678,"temperature":0.7,"pith_summary":"The paper answers a refined counting question for permutations whose rises and falls come in pairs, meaning every peak and valley sits at an odd position. It establishes that the bivariate exponential generating function for these up-up-or-down-down permutations, grouped by their last entry, is the closed hyperbolic rational expression in identity (4). The argument starts from a two-term recurrence for the counts and converts it into a partial differential equation for the generating function, which is then solved through a symmetry lemma about Seidel arrays. Along the way the proof recovers the known one-variable generating function for the total counts as a special case.","feed_headline":"One formula settles the up-up-or-down-down last-entry count","feed_subtitle":"Closed hyperbolic generating function gives the distribution of final values for every odd length.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the whirlpool-permutation problem and proves its connection to the paired-rises-and-falls permutation class","marker":"[4]"},{"why":"records the one-variable generating function and the context for the refined last-entry question","marker":"[5]"},{"why":"supplies the Euler-Seidel array background on which Lemma 5(a) is built","marker":"[2]"},{"why":"supplies the Seidel-array generating-function facts used in Lemma 5(b)","marker":"[3]"},{"why":"gives an earlier derivation of the one-variable generating function (1) that the bivariate result must specialize to","marker":"[6]"},{"why":"gives another independent derivation of (1) used as a consistency check","marker":"[8]"},{"why":"derives the generating function for the even-length whirlpool counts that the result also recovers","marker":"[1]"}],"fun_headline_variants":["Knuth's up-up-down-down puzzle solved by closed form","Hyperbolic formula settles last-entry counts for odd permutations","Bivariate generating function for up-up-down-down permutations","One identity answers Knuth's counting question","Closed form for up-up-down-down last entries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Knuth's up-up-down-down puzzle solved by closed form","Hyperbolic formula settles last-entry counts for odd permutations","Bivariate generating function for up-up-down-down permutations","One identity answers Knuth's counting question","Closed form for up-up-down-down last entries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2816,"prompt_tokens":890,"completion_tokens":1926,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":1851}},"tokens_in":506,"tokens_out":1926,"duration_ms":12555,"temperature":1.0,"reasoning_tokens":1851,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:33:42.847793+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the whirlpool-permutation problem and proves its connection to the paired-rises-and-falls permutation class"},{"cited_title":"Knuth, The Art of Computer Programming, Volume 4, Pre-Fascicle 7a","cited_arxiv_id":null,"evidence_quote":"records the one-variable generating function and the context for the refined last-entry question"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the Euler-Seidel array background on which Lemma 5(a) is built"},{"cited_title":"Discrete Math","cited_arxiv_id":null,"evidence_quote":"supplies the Seidel-array generating-function facts used in Lemma 5(b)"},{"cited_title":"306 (2006), no","cited_arxiv_id":null,"evidence_quote":"gives an earlier derivation of the one-variable generating function (1) that the bivariate result must specialize to"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives another independent derivation of (1) used as a consistency check"},{"cited_title":"4, 989–1034","cited_arxiv_id":null,"evidence_quote":"derives the generating function for the even-length whirlpool counts that the result also recovers"}],"review_version":1}