Unique longest increasing subsequences in 132-avoiding permutations

MaRDI QIDQ6586840zbMATH OpenFDO

Authors Nicholas Van Nimwegen

Publication date 13 August 2024

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

longest increasing subsequencepermutation patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial inequalities (05A20)

Review text

\textit{M. Bóna} and \textit{E. Dejonge} [Electron. J. Comb. 27, No. 4, Research Paper P4.44, 11 p. (2020; Zbl 1454.05006)] established that as \(n\) tends to infinity, the proportion of \(132\)-avoiding permutations of length \(n\) with a unique longest increasing subsequence (ULIS) approaches \(1/2\), and they posed the question: are there always at least as many \(132\)-avoiding permutations of length \(n\) with a ULIS as without?\N\NThe author answers this question affirmatively by constructing an injection from \(132\)-avoiding permutations of length \(n\) without a ULIS to those with a ULIS. This injection also increases the length of the longest increasing subsequence (LIS) by precisely \(1\).

Recommendations

• Pattern avoiding permutations with a unique longest increasing subsequence
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Longest increasing subsequences in involutions avoiding patterns of length three
• Longest increasing subsequences in pattern-restricted permutations
• scientific article; zbMATH DE number 7250398

Cites work

• A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Pattern avoiding permutations with a unique longest increasing subsequence

Cited in

(1)

• A computer algebra package for bivariate asymptotics with effective error bounds

This page was built for publication: Unique longest increasing subsequences in 132-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6586840)