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

zbMATH Open1196.05008arXiv0704.0004MaRDI QIDQ3575423FDOQ3575423

Authors: David Callan 

Publication date: 27 July 2010

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.

Full work available at URL: https://arxiv.org/abs/0704.0004

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

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)

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)