𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by E. Barcucci; A. Del Lungo; A. Frosini; S. Rinaldi

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
178 KB
Volume
26
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we tackle the problem of giving, by means of a regular language, a Ž . combinatorial interpretation of a positive sequence f defined by a linear n recurrence with integer coefficients. We propose two algorithms able to determine Ž . Ž . if the rational generating function of f , f x , is the generating function of some n 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.

📜 SIMILAR VOLUMES

A Combinatorial Problem on Polynomials a
A Combinatorial Problem on Polynomials and Rational Functions
✍ György Elekes; Lajos Rónyai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 190 KB

The structure of rational functions of two real variables which take few distinct values on large (finite) Cartesian products is described. As an application, a problem of G. Purdy is solved on finite subsets of the plane which determine few distinct distances.

The counting function for a λ–rational S
The counting function for a λ–rational Sturm–Liouville problem
✍ Leon Greenberg; Marco Marletta 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB

## Abstract We develop an oscillation theory for an equation of Hain–Lüst type, valid both outside and inside the essential spectrum. The results proved allow us to locate eigenvalues in the essential spectrum or resonances close to the essential spectrum. The numerical implementation of the oscill

A Parser for the Interval Evaluation of
A Parser for the Interval Evaluation of Analytical Functions and its Application to Engineering Problems
✍ J.-P. Merlet 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 311 KB

We have developed a parser which takes as input a file containing the analytical expression of one or more formulas and ranges for each unknown in the formula and returns an interval evaluation of the formula. We describe the use of this parser for solving robotics problems and, in a more general co