UCLA

An integer sequence {a n } is called polynomially recursive, or P-recursive, if it satisfies a nontrivial linear recurrence relation of the form

q_0(n)a_n + q_1(n)a_{n−1} + . . . + q_k(n)a_{n−k} = 0 ,

for some q_i(x) ∈ Z[x], 0 ≤ i ≤ k. The study of P-recursive sequences plays a major role in modern Enumerative and Asymptotic Combinatorics. P-recursive sequences have D-finite (also called holonomic) generating functions.

This dissertation is on the application of automata theory to the analysis of P-recursive integer sequences, and is broken into three self-contained chapters. Chapters 1 and 2 contain negative results, simulating Turing machines within combinatorial structures to show these structures are not counted by a P-recursive sequence. In Chapter 1, we answer a question of Maxim Kontsevich by showing [1]u_n is not always P-recursive when u ∈ Z[GL(k, Z)]. In Chapter 2, we disprove the celebrated Noonan-Zeilberger conjecture by showing that pattern avoidance is not P-recursive. These two chapters give the first results that disprove P-recursiveness using automata theory. Historically, results of this form have been mostly proven using analysis of the asymptotics.

Chapter 3 gives a full analysis of the class of integer sequences counting irrational tilings of a constant height strip. This class is a subset of P-recursive sequences, and we prove the equivalence of three definitions of this class: counting functions of irrational tilings, binomial multisums, and diagonals of N-rational generating functions. In this analysis, we count paths through a labelled graph in a way that is equivalent to counting strings accepted by a given deterministic finite automaton where each letter appears n times.