Bijective enumeration of permutations starting with a longest increasing subsequence

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.

arXiv commentRevised version: added a bijection via permutations only, without RSK; incorporated referee's suggestions. To appear in DMTCS Proceedings