Recurrences for permutations with long increasing subsequences

Manuel Kauers, Chen Wang

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 ran…