کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437065 690071 2006 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rationality of the Möbius function of a composition poset
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Rationality of the Möbius function of a composition poset
چکیده انگلیسی

We consider the zeta and Möbius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Mélou, and Dulucq. The Möbius 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öbius 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 μ using this machinery. These results are closely related to those of Björner and Reutenauer about subword order, and we discuss a common generalization.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 359, Issues 1–3, 14 August 2006, Pages 282-298