Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 1 h ago
PreprintCC BY 4.0arXiv

Recurrences for permutations with long increasing subsequences

  • Manuel Kauers
  • Chen Wang
Open at sourcePDFDOICite

Abstract

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.

Related

  1. The longest increasing subsequences of Luce permutations and permutons
    Jacopo Borga, Victor Dubach
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityHALarXiv
  2. Caged subsequences in permutations
    Niranjan Balachandran, Omkar Ramdas, Umesh Shankar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Longest increasing subsequences of dyadic-type chaotic orbits
    Shinsuke Iwao, Fumihiko Nakamura, Yushi Nakano
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsDynamical systemsarXiv
  4. Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
    Henning Arnór Skeggi Úlfarsson
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Quotients of L1 by subsequences of the Haar system have cotype 2
    Stephen Dilworth, Denka Kutzarova, Mikhail Ostrovskii +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{kauers2026recurrences,
  title = {{Recurrences for permutations with long increasing subsequences}},
  author = {Manuel Kauers and Chen Wang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02220},
  eprint = {2609.02220},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02220},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Recurrences for permutations with long increasing subsequences
AU  - Manuel Kauers
AU  - Chen Wang
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02220
UR  - https://arxiv.org/abs/2609.02220
AB  - 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.
ER  -