
5
In This Way, but Nicely. Pattern Avoidance.
Follow-Up.
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 S
n
(q) are. In this chapter, we will mostly concentrate on
how nice they are, or rather, how nice the sequence {S
n
(q)}
1≤n
is. By abuse
of language, we will often refer to this sequence as the sequence S
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 ...