In 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.
A technology for reverse-engineering combinatorial problem from a rational generating function / E. BARCUCCI; A. DEL LUNGO; A. FROSINI; S. RINALDI. - In: ADVANCES IN APPLIED MATHEMATICS. - ISSN 0196-8858. - STAMPA. - 26:(2001), pp. 129-153.
A technology for reverse-engineering combinatorial problem from a rational generating function
BARCUCCI, ELENA;FROSINI, ANDREA;
2001
Abstract
In 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.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.