Source-linked AI summary
Recurrences for permutations with long increasing subsequences
Manuel Kauers, Chen Wang
TL;DR
The paper addresses the lack of uniform bivariate recurrences for permutation counts by proving two coupled recurrences in the sector n/2 ≤ k ≤ n. These recurrences establish regional D-finiteness and, as a corollary, prove Kauers and Koutschan’s conjectured recurrence for b_2n,n.
Problem
Uniform recurrences sufficient for bivariate D-finiteness are not available across the full array, motivating a restricted-region result.
Method
The paper proves two recurrences using the Robinson–Schensted correspondence, representation-theoretic operators, and character orthogonality.
Results
Up to normalization, the derived recurrence for b_2n,n is precisely the recurrence conjectured by Kauers and Koutschan.
Takeaways & Limitations
The bivariate sequence is D-finite inside n/2 ≤ k ≤ n, and the conjectured sequence b_2n,n is thereby settled.
Takeaways & Limitations
The paper proves only the two recurrences for the sector k ≥ n/2; broader slices such as k ≥ n/r remain conjectural.
Abstract
from arXiv · showhide
We prove two simple bivariate recurrences for the number of permutations with a long increasing subsequence. The two recurrences imply D-finiteness of the sequence in a certain range. As a consequence, we also obtain a proof of a conjecture posed by Kauers and Koutschan in 2023.
1. Introduction
The paper identifies a gap in establishing uniform bivariate D-finiteness for permutation counts, then proves two coupled recurrences in the sector n/2 ≤ k ≤ n. These recurrences yield D-finiteness there and establish Kauers and Koutschan’s conjecture as a corollary.
- Notation: The sequence a_n,k counts permutations of length n whose longest increasing subsequence has exactly length k.The convention sets a_n,k to zero outside 1 ≤ k ≤ n.
- Motivation: Uniform recurrences in both n and k are required for bivariate D-finiteness, rather than separate recurrences for individual rows or columns.The relevant recurrences must work simultaneously across the array.
- Main result: The recurrences imply that the bivariate sequence is D-finite inside the sector n/2 ≤ k ≤ n.Here, D-finiteness inside a region means coincidence with a D-finite array throughout that region.
- Conjecture: Kauers and Koutschan conjectured that b_2n,n, counting permutations of length 2n with an increasing subsequence of length n, satisfies an order-4 D-finite recurrence.The paper derives precisely that recurrence up to normalization from Theorem 1.
- Proof strategy: The proof uses Robinson–Schensted, representation dimensions, branching and rim-hook operators, and character orthogonality.The long-first-row condition in the target range makes the relevant operators particularly simple.
2. Large scale calculation of an,k
Large-scale computation combines determinantal formulas, truncated power-series elimination, modular arithmetic, and Chinese-remainder reconstruction to generate data for recurrence guessing. The experiments reveal more complicated bivariate recurrences beyond k=n/2, while the paper proves D-finiteness only in the stated sector.
- Computational method: Gessel’s determinantal formula for cumulative counts provides the data needed to guess recurrences for a_n,k.The computation uses the cumulative counts u_k(n).
- Computational method: Gaussian elimination computes leading principal minors of a K × K matrix with truncated power-series entries.The calculation is performed without pivoting, using series truncated to degree N.
- Computational method: Modular computation over many primes followed by the Chinese remainder theorem controls large integer arithmetic during reconstruction of u_k(n).Each prime exceeds N + K, and their product exceeds N!.
- Computational results: N = 300 and K = 200 required about 1 hour and produced enough data to guess recurrences (1) and (2).A larger modular computation with N = K = 1200 took about 1 day for further recurrence investigation.
- Computational results: On the other side of k = n/2, the array experimentally satisfies more complicated bivariate recurrences with higher order.These recurrences appear to extend the observed structure beyond the sector where D-finiteness is proved.
- Scope of results: The paper proves D-finiteness for n/2 ≤ k ≤ n, while the experimentally observed recurrences in broader regions remain outside the proved result.The guessed recurrences in the light-gray region are only reported as appearing to hold.
3. Proof of Theorem 1
The proof encodes permutation counts as squared norms of representation-theoretic vectors, then combines rim-hook and branching identities through adjointness to derive the two recurrences.
- Representation-theoretic setup: Robinson–Schensted and character methods establish the regular-representation identity underlying the norm formula.The proof uses character restriction, induction, orthogonality, and the Robinson–Schensted correspondence.
- Representation-theoretic setup: an,k equals the squared norm of Wk,n−k, linking permutation counts to the auxiliary vector-space construction.The vectors are built from formal basis vectors indexed by integer partitions and equipped with the standard inner product.
- Operator identities: In the long-first-row regime, rim-hook removal simplifies to DsWk,m = −Wk+s,m−s when m ≤ k + 1 and 2 ≤ s ≤ m.The proof rules out rim hooks meeting both the first row and lower part under these size conditions.
- Operator identities: One-box branching gives D1Wl,m = (l + m)Wl,m−1 − Wl+1,m−1 for 1 ≤ m ≤ l + 1.This is proved coefficientwise by summing over ways to add one box below the first row.
- Deriving the recurrences: Adding identities cancels mixed inner products, and adjointness then yields recurrence (1), with boundary cases handled directly.The proof explicitly identifies the resulting identity with recurrence (1) and separately treats m = 0.
- Deriving the recurrences: Applying rim-hook and branching identities to adjacent vectors, eliminating mixed products by adjointness, and rearranging yields recurrence (2).The argument covers 1 ≤ m ≤ k after handling the m = 0 case separately.