Combinatorics of Permutations, 3rd Edition

5In This Way, but Nicely. Pattern Avoidance. Follow-Up.

DOI: 10.1201/9780429274107-5

5.1 Polynomial Recurrences

5.1.1 Polynomially Recursive Functions

In the previous chapter, we spent considerable time and effort to find out how large the numbers ${\text{Av}}_n(q)$ are. In this chapter, we will mostly concentrate on how nice they are, or rather, how nice the sequence ${\{{\text{Av}}_n(q)\}}_{1\le n}$ is. By abuse of language, we will often refer to this sequence as the sequence ${\text{Av}}_n(q)$.

First, of course, we should define what we mean by “nice.” We have already made one important definition, that of P-recursive (or polynomially recursive) sequences in Exercise 29 of Chapter 1, but for easy reference we repeat that definition here.

DEFINITION 5.1 A sequence $f:N\to C$ is called ...