Objetos combinatorios y fracciones continuas asociadas a autómatas ponderados infinitos

Abstract

En este trabajo presentamos una metodología general para resolver una gran variedad de problemas clásicos de conteo sobre trayectorias en el plano. Estos problemas están relacionados con trayectorias de Dyck, trayectorias de Motzkin y algunas de sus generalizaciones. La metodología usa autómatas ponderados, ecuaciones de funciones generatrices y fracciones continuas. Hemos llamado a esta nueva metodología ``Metodología de Autómatas de Conteo'', la cual es una variación de la técnica propuesta por Rutten, llamada ``Conteo por Coinducción'' (Texto tomado de la fuente).

In this work, we present a general methodology to solve a wide variety of classical lattice path counting problems in a uniform way. These counting problems are related to Dyck paths, Motzkin paths and some of their generalizations. The methodology uses weighted automata, equations of ordinary generating functions and continued fractions. We refer this new methodology as “Counting Automata Methodology”. It is a variation of the technique proposed by Rutten, which is called “Coinductive Counting”.