# zbMATH — the first resource for mathematics

q-hook length formulas for forests. (English) Zbl 0697.06002
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.

##### MSC:
 06A06 Partial orders, general 05C05 Trees 06A05 Total orders 05A05 Permutations, words, matrices
Full Text:
##### References:
  Aho, A.V; Hopcroft, J.E; Ullman, J.D, The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029  Andrews, G.E, The theory of partitions, (1976), Addison-Wesley Reading, MA · Zbl 0371.10001  Björner, A; Wachs, M, Generalized quotients in Coxeter groups, Trans. amer. math. soc., 308, 1-37, (1988) · Zbl 0659.05007  Björner, A; Wachs, M, Permutation statistics and linear extensions of posets, (1988), preprint  Foata, D, On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403  Foata, D; Schützenberger, M.-P, Major index and inversion number of permutations, Math. nachr., 83, 143-159, (1978) · Zbl 0319.05002  Frame, J.S; Robinson, G.de B; Thrall, R.M, The hook graphs of the symmetric group, Canad. J. math., 6, 316-324, (1954) · Zbl 0055.25404  Garsia, A.M; Gessel, I, Permutation statistics and partitions, Adv. in math., 31, 288-305, (1979) · Zbl 0431.05007  Knuth, D.E, Sorting and searching, () · Zbl 0777.68012  MacMahon, P.A; MacMahon, P.A, The indices of permutations…, (), 35, 508-549, (1913), Reprinted · JFM 44.0076.02  MacMahon, P.A; MacMahon, P.A, Two applications of general theorems in combinatory analysis: …, (), 556-563, Reprinted · JFM 39.0241.01  Mallows, C.W; Riordan, J, The inversion enumerator for labelled trees, Bull. amer. math. soc., 74, 92-94, (1968) · Zbl 0242.05004  Sagan, B, Enumeration of partitions with hooklengths, European J. combin., 3, 85-94, (1982) · Zbl 0483.05010  Stanley, R.P, Ordered structures and partitions, Mem. amer. math. soc., 119, (1972) · Zbl 0246.05007  Tits, J, Buildings of spherical type and finite BN-pairs, () · Zbl 0295.20047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.