A Technology for Reverse-Engineering a Combinatorial Problem from a Rational Generating Function

AbstractIn this paper, we tackle the problem of giving, by means of a regular language, a combinatorial interpretation of a positive sequence (fn) defined by a linear recurrence with integer coefficients. We propose two algorithms able to determine if the rational generating function of (fn), f(x), is the generating function of some regular language, and, in the affirmative case, to find it. We illustrate some applications of this method to combinatorial object enumeration problems and bijective combinatorics and discuss an open problem regarding languages having a rational generating function