Counting with two-level polynomials

We examine combinatorial counting functions with two parameters, $n$ and $q$.

For fixed $q$, these functions are (quasi-)polynomial in $n$.

As $q$ varies, the degree of this polynomial is itself polynomial in $q$, as are the leading coefficients.

We carefully define these two-level polynomials, lay out their basic algebraic properties, and provide a schema for showing a function is a two-level polynomial.

Using the schema, we prove that a variety of counting functions arising in different areas of combinatorics are two-level polynomials.

These include chromatic polynomials for many infinite families of graphs, partitions of an integer into a given number of parts, placing non-attacking chess pieces on a board, Sidon sets, and Sheffer sequences (including binomial type and Appell sequences).