Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rationality of the Mobius function of a composition poset
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0002-7497-2764
2006 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 359, no 3-Jan, 282-298 p.Article in journal (Refereed) Published
Abstract [en]

We consider the zeta and Mobius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Melou, and Dulucq. The Mobius 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, zeta, and the Mobius function, mu. 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 it using this machinery. These results are closely related to those of Bjorner and Reutenauer about subword order, and we discuss a common generalization.

Place, publisher, year, edition, pages
2006. Vol. 359, no 3-Jan, 282-298 p.
Keyword [en]
automaton, composition, generating function, hypergeometric series, monoid, rationality, subword order, identities, permutations, algorithm
Identifiers
URN: urn:nbn:se:kth:diva-15927DOI: 10.1016/j.tcs.2006.03.025ISI: 000239885600020Scopus ID: 2-s2.0-33746508424OAI: oai:DiVA.org:kth-15927DiVA: diva2:333969
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Björner, Anders

Search in DiVA

By author/editor
Björner, Anders
By organisation
Mathematics (Div.)
In the same journal
Theoretical Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf