q-hook length formulas for forests (Q911620): Difference between revisions

If P is a finite poset with a one-one labeling w, then the set of linear extensions L(P,w) of (P,w) generates a set of permutations on w(P), which is normally the set \(\{\) 1,...,n\(\}\). The structure of the poset is therefore related directly to that of the set of permutations associated with it. Given (P,w), the descent set \(D(P,w)=\{x\in P|\) \(w(x)>w(y)\), y covers \(x\}\), the major index \(maj(P,w)=\sum \{x\in D(p,w)|\) \(h_ x\}\), where \(h_ x\) is the number of elements in the order ideal generated by x, inv(P,w) is the number of ordered pairs (x,y) such that \(x<y\) and \(w(x)>w(y)\). A forest is a poset such that every element is covered by at most one element. Knuth's hook-length formula is \(| L(P,w)| =n!/\prod \{x\in P|\) \(h_ x\}\). A labeling w on a poset P is regular if \(x<z\) and \(y\in P\) with \(w(x)<w(y)<w(z)\) or \(w(x)>w(y)>w(z)\) implies \(x<y\) or \(y<z\). Regular labelings include many important special types. If \([n]=1+q+...+q^{n-1}\) and \([n]!=[n]([n- 1]!)\), then the q-formulas reduce for \(=1\) to standard ones. Among others the authors prove the following very interesting analogues of Knuth's formula which may be used as tools for structural analysis of posets as well, especially as applied to forests. I. Let P be any forest of size n and let w be any regular labeling of P, then: \[ \sum \{\sigma \in L(P,w)| \quad q^{inv(\sigma)}\}=q^{inv(P,w)}[n]!/\prod \{x\in P| \quad [h_ x]\}. \] II. If w is any labeling of P in I, then: \[ \sum \{\sigma \in L(P,w)| \quad q^{maj(\sigma)}\}=q^{maj(P,w)}[n]!/\prod \{x\in P| \quad [h_ x]\}. \] III. If W(P) is the set of all labelings in P, then: \[ \sum \{w\in W(P)| \quad q^{inv(P,w)}\}=(n!/\prod \{x\in P| \quad h_ x\})\prod x\in P| \quad [h_ x]\}=\sum \{w\in W(P)| \quad q^{maj(p,w)}\}. \] IV. (P,w) is a regularly labeled forest iff for some \(k\geq 0:\) \(\sum \{\sigma \in L(P,w)| \quad q^{inv(\sigma)}\}=q^ k([n]!/\prod \{x\in P| \quad [h_ x]\}).\)V. (P,w) is a labeled forest iff for some \(k\geq 0:\) \(\sum \{\sigma \in L(P,w)| \quad q^{maj(\sigma)}\}=q^ k([n]!/\prod \{x\in P| \quad [h_ x]\}).\)In obtaining these results the authors also reprove an important result of Stanley in a purely combinatorial manner.