Non-commutative Rational Power Series and Algebraic Generating Functions

Sequences of numbers abound in combinatorics the generating functions of which are algebraic over the rational functions. Examples include Catalan and related numbers, numbers of words expressing an element in a free group, and diagonal coefficients of 2-variable rational generating functions (Furstenbergʹs theorem). Algebraicity is of practical as well as theoretical interest, since it guarantees an efficient recurrence for computing coefficients. Using now-classic results of Schützenberger of formal languages we prove the following: Theorem. Let K be a field and f(X1,…Xk, Y1,…,Yk) a rational power series in non-commuting indeterminates. Then any coefficient of f(X1,…,Xk, X-11,…,X-1k) converging w.r.t. a given valuation on K is algebraic over K. Many algebraic generating functions, including those mentioned above, are so as a consequence of this theorem; in particular, it gives a new elementary proof of Furstenbergʹs theorem.