Title | ||
---|---|---|
A Technology for Reverse-Engineering a Combinatorial Problem from a Rational Generating Function |
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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1006/aama.2000.0711 | Advances in Applied Mathematics |
Keywords | Field | DocType |
generating function,reverse engineering,regular language | Generating function,Analytic combinatorics,Combinatorics,Bijection,Rational series,Algebra,Mathematical analysis,Combinatorial principles,Regular language,Combinatorial class,Rational function,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 2 | 0196-8858 |
Citations | PageRank | References |
10 | 0.81 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
E. Barcucci | 1 | 94 | 13.49 |
Alberto Del Lungo | 2 | 376 | 44.84 |
A. Frosini | 3 | 24 | 2.90 |
Simone Rinaldi | 4 | 174 | 24.93 |