  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.

Combinatorics