Discrete Mathematics & Theoretical Computer Science |

- 1 Institute of Mathematics
- 2 Department of Mathematics [Univ California San Diego]
- 3 Department of Mathematics [Lansing]

Let $P$ be a partially ordered set and consider the free monoid $P^{\ast}$ of all words over $P$. If $w,w' \in P^{\ast}$ then $w'$ is a factor of $w$ if there are words $u,v$ with $w=uw'v$. Define generalized factor order on $P^{\ast}$ by letting $u \leq w$ if there is a factor $w'$ of $w$ having the same length as $u$ such that $u \leq 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 \in P^{\ast}$, we prove that the language $\mathcal{F}(u)=\{w : w \geq u\}$ is accepted by a finite state automaton. If $P$ is finite then it follows that the generating function $F(u)=\sum_{w \geq u} w$ is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider $P=\mathbb{P}$, the positive integers with the usual total order, so that $\mathbb{P}^{\ast}$ is the set of compositions. In this case one obtains a weight generating function $F(u;t,x)$ by substituting $tx^n$ each time $n \in \mathbb{P}$ appears in $F(u)$. We show that this generating function is also rational by using the transfer-matrix method. Words $u,v$ are said to be Wilf equivalent if $F(u;t,x)=F(v;t,x)$ and we can prove various Wilf equivalences combinatorially. Björner found a recursive formula for the Möbius function of ordinary factor order on $P^{\ast}$. It follows that one always has $\mu (u,w)=0, \pm 1$. Using the Pumping Lemma we show that the generating function $M(u)= \sum_{w \geq u} | \mu (u,w) | w$ can be irrational.

Source: HAL:hal-01185380v1

Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)

Section: Proceedings

Published on: January 1, 2009

Imported on: January 31, 2017

Keywords: Wilf equivalence,rational generating function,partially ordered set,finite state automaton,factor order,composition,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Funding:

- Source : OpenAIRE Graph
*Combinatorial Structures for Permutation Enumeration and Macdonald Polynomials*; Funder: National Science Foundation; Code: 0654060

This page has been seen 204 times.

This article's PDF has been downloaded 188 times.