Bijective enumeration of permutations starting with a longest increasing subsequence

MaRDI QIDQ4591360zbMATH OpenFDO

Authors Greta Panova

Publication date 14 November 2017

Full work available at URL https://arxiv.org/abs/0905.2013, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAN0174

zbMATH Keywords

\(q\)-analoguelongest increasing subsequencemajor indexpermutationsRSK

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Abstract: We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain Goupil. We give two `elementary' bijective proofs of this result and of its $q$-analogue, one proof using the RSK correspondence and one only permutations.

Recommendations

• Enumerating \(r\)c-invariant permutations with no long decreasing subsequences
• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• Permutation q-enumeration with the Schur row adder
• Longest increasing subsequences and log concavity
• Bijections for refined restricted permutations

Cited in

(4)

• Permutation q-enumeration with the Schur row adder
• Signed mahonians on some trees and parabolic quotients
• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• Enumerating \(r\)c-invariant permutations with no long decreasing subsequences

This page was built for publication: Bijective enumeration of permutations starting with a longest increasing subsequence

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