Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Rationality, irrationality, and Wilf equivalence in generalized factor order. | Rationality irrationality and Wilf equivalence in generalized factor order Sergey Kitaev The Mathematics Institute School of Computer Science Reykjavik University IS-103 Reykjavik Iceland sergey@ Jeffrey Liese Department of Mathematics California Polytechnic State University San Luis Obispo CA 93407-0403 USA jliese@ Jeffrey Remmel Department of Mathematics University of California San Diego La Jolla CA 92093-0112 USA remmel@ Bruce E. Sagan Department of Mathematics Michigan State University East Lansing MI 48824-1027 USA sagan@ Submitted Jun 1 2008 Accepted Nov 18 2009 Published Dec 2 2009 Mathematics Subject Classifications 05A15 68R15 06A07 Keywords composition factor order finite state automaton generating function partially ordered set rationality transfer matrix Wilf equivalence Dedicated to Anders Bjorner on the occasion of his 60th birthday. His work has very heavily influenced ours. Abstract Let P be a partially ordered set and consider the free monoid P of all words over P. If w w E P then w is a factor of w if there are words u v with w uw v. Define generalized factor order on P by letting u w if there is a factor w 1 of w having the same length as u such that u w where the comparison of u and w is done componentwise using the partial order in P. One obtains ordinary factor order by insisting that u w or equivalently by taking P to be an antichain. Given u E P we prove that the language F u w w u is accepted by a finite state automaton. If P is finite then it follows that the generating function F u Ew u w is rational. This is an analogue of a theorem of Bjorner and Sagan for generalized subword order. The work presented here was supported by the Icelandic Research Fund grant no. 090038011. 1 Partially supported by NSF grant DMS 0654060 Work partially done while a Program Officer at NSF. The views expressed are not necessarily those of the NsF. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2 2009 R22 1 We also .
