Kauers–Koutschan 2023 conjecture on long increasing subsequences

Let $b_{2n,n}$ denote the number of permutations of length $2n$ that contain an increasing subsequence of length $n$ , and define $B(z)=\sum_{n\geq 0} b_{2n,n}z^n$ . The conjecture is that $B(z)$ is D-finite; equivalently, the sequence $(b_{2n,n})_{n\geq 0}$ is P-recursive, so there exist polynomials $p_0(n),\ldots,p_r(n)$ , not all zero, such that $\sum_{j=0}^r p_j(n)b_{2(n+j),n+j}=0$ for all sufficiently large $n$ .

References

Primary source

arXiv

Additional references

Recurrences for permutations with long increasing subsequences — arXiv

enumerative-combinatorics permutation-patterns

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2026 preprint claims to settle the conjecture about counting permutations with long increasing subsequences, but the result has not been independently verified.

Kauers and Koutschan posed the conjecture in 2023, concerning recurrence properties of permutation counts involving long increasing subsequences.

September 2026 preprint

The preprint claims two bivariate recurrences for $a_{n,k}$ , the number of permutations of length $n$ whose longest increasing subsequence has length $k$ , valid when $n/2\leq k\leq n$ . It then derives the conjectured recurrence for $b_{2n,n}$ , counting permutations of length $2n$ containing an increasing subsequence of length $n$ , and claims the associated D-finiteness conclusion in that range. No independent verification, error report, or retraction was found.

Current status (as of September 2026): Kauers–Koutschan's conjecture is claimed proved by the 2026 preprint, with the D-finiteness statement established only for $n/2\leq k\leq n$ ; independent verification remains outstanding.

Sources

No solutions have been posted yet.