A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata

MaRDI QIDQ3575423zbMATH OpenFDO

Authors David Callan

Publication date 27 July 2010

Full work available at URL https://arxiv.org/abs/0704.0004, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/657/0.html

zbMATH Keywords

sign-reversing involutioncolumn-marked subdiagonal pathStirling cycle numberunlabeled acyclic automaton

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Algebraic theory of languages and automata (68Q70)

Abstract: We show that a determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata. The proof involves a bijection from these automata to certain marked lattice paths and a sign-reversing involution to evaluate the determinant.

Recommendations

• Exact enumeration of acyclic deterministic automata
• Counting on Determinants
• Enumeration of minimal acyclic automata via generalized parking functions
• scientific article; zbMATH DE number 2188477
• Accessible and deterministic automata: enumeration and Boltzmann samplers

Cited in

(3)

• Compacted binary trees admit a stretched exponential
• The pure descent statistic on permutations
• Enumerating regular expressions and their languages

This page was built for publication: A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575423)