Rationality of the Möbius function of a composition poset

DOI10.1016/J.TCS.2006.03.025MaRDI QIDQ2503301zbMATH OpenOpenAlexFDO

Authors Bruce E. Sagan, Anders Bjoerner

Publication date 14 September 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

automatoncompositiongenerating functionhypergeometric seriesmonoidrationalitysubword order

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Arithmetic functions; related numbers; inversion formulas (11A25) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We consider the zeta and M"obius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-M'elou, and Dulucq. The M"obius function of this poset was determined by Sagan and Vatter. We prove rationality of various formal power series in noncommuting variables whose coefficients are evaluations of the zeta function and the M"obius function. The proofs are either directly from the definitions or by constructing finite-state automata. We also obtain explicit expressions for generating functions obtained by specializing the variables to commutative ones. We reprove Sagan and Vatter's formula for the M"obius function using this machinery. These results are closely related to those of Bj"orner and Reutenauer about subword order, and we discuss a common generalization.

Recommendations

• The Möbius function of a restricted composition poset.
• The Möbius function of a composition poset
• The Möbius function of generalized subword order
• The Möbius function of generalized subword order
• Rationality, irrationality, and Wilf equivalence in generalized factor order

Cites work

• A \textit{Mathematica} version of Zeilberger's algorithm for proving binomial coefficient identities
• A fast algorithm for proving terminating hypergeometric identities
• A holonomic systems approach to special functions identities
• Differential Posets
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3513846 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 854872 (Why is no real title available?)
• Rationality of the Möbius function of subword order
• Simple permutations and pattern restricted permutations
• Standard paths in another composition poset
• The patterns of permutations
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(13)

• On the Möbius function of a lower Eulerian Cohen-Macaulay poset
• Standard paths in another composition poset
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• Reconstructing compositions
• The Möbius function of a composition poset
• The Möbius function of a restricted composition poset.
• Rationality, irrationality, and Wilf equivalence in generalized factor order
• scientific article; zbMATH DE number 1972790 (Why is no real title available?)
• Rook theory, compositions, and zeta functions
• On the dimension of downsets of integer partitions and compositions
• The Möbius function of generalized subword order
• Compositions inside a rectangle and unimodality
• Avoidance of partitions of a three-element set

This page was built for publication: Rationality of the Möbius function of a composition poset

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