×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V; Hopcroft, J.E; Ullman, J.D, The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Andrews, G.E, The theory of partitions, (1976), Addison-Wesley Reading, MA · Zbl 0371.10001
[3] Björner, A; Wachs, M, Generalized quotients in Coxeter groups, Trans. amer. math. soc., 308, 1-37, (1988) · Zbl 0659.05007
[4] Björner, A; Wachs, M, Permutation statistics and linear extensions of posets, (1988), preprint
[5] Foata, D, On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403
[6] Foata, D; Schützenberger, M.-P, Major index and inversion number of permutations, Math. nachr., 83, 143-159, (1978) · Zbl 0319.05002
[7] 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
[8] Garsia, A.M; Gessel, I, Permutation statistics and partitions, Adv. in math., 31, 288-305, (1979) · Zbl 0431.05007
[9] Knuth, D.E, Sorting and searching, () · Zbl 0777.68012
[10] MacMahon, P.A; MacMahon, P.A, The indices of permutations…, (), 35, 508-549, (1913), Reprinted · JFM 44.0076.02
[11] MacMahon, P.A; MacMahon, P.A, Two applications of general theorems in combinatory analysis: …, (), 556-563, Reprinted · JFM 39.0241.01
[12] Mallows, C.W; Riordan, J, The inversion enumerator for labelled trees, Bull. amer. math. soc., 74, 92-94, (1968) · Zbl 0242.05004
[13] Sagan, B, Enumeration of partitions with hooklengths, European J. combin., 3, 85-94, (1982) · Zbl 0483.05010
[14] Stanley, R.P, Ordered structures and partitions, Mem. amer. math. soc., 119, (1972) · Zbl 0246.05007
[15] 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.