A technology for reverse-engineering a combinatorial problem from a rational generating function

DOI10.1006/aama.2000.0711zbMath0984.05005OpenAlexW1963721416MaRDI QIDQ5933434

Simone Rinaldi, Elena Barcucci, Alberto del Lungo, Andrea Frosini

Publication date: 7 May 2002

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aama.2000.0711

zbMATH Keywords

generating functionenumerationcombinatorial interpretationcontext-free languagelinear recurrenceregular language

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics in computer science (68R05) Formal languages and automata (68Q45) Polyominoes (05B50)

Related Items (10)

Recurrence relations, succession rules and the positivity problem ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Regular languages and their generating functions: The inverse problem ⋮ Another proof of Soittola's theorem ⋮ Characteristic polynomials of nonnegative real square matrices and generalized clique polynomials ⋮ Definability of Combinatorial Functions and Their Linear Recurrence Relations ⋮ \(\mathbb Z\)-rationality of a certain class of formal series ⋮ Recurrence Relations, Succession Rules, and the Positivity Problem ⋮ On the equivalence problem for succession rules ⋮ In memoriam: Alberto Del Lungo (1965--2003)

Uses Software

• OEIS

Cites Work

• Algebraic complexity of computing polynomial zeros
• Positive rational sequences
• Bijective recurrences concerning Schröder paths
• Algebraic languages and polyominoes enumeration
• A combinatorial interpretation of the recurrence \(f_{n+1}=6f_n-f_{n-1}\)
• A combinatorial interpretation of the area of Schröder paths
• Generating trees and the Catalan and Schröder numbers
• Effective asymptotics of linear recurrences with rational coefficients
• Self-avoiding walks, the language of science, and Fibonacci numbers
• Planar Maps are Well Labeled Trees
• Succession rules and Deco polyominoes
• Star-height of an N-rational series
• Directed column-convex polyominoes by recurrence relations
• On positive matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A technology for reverse-engineering a combinatorial problem from a rational generating function