q-hook length formulas for forests
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.
- Axioms and hulls
- Buildings of spherical type and finite BN-pairs
- Enumeration of partitions with hooklengths
- Generalized Quotients in Coxeter Groups
- scientific article; zbMATH DE number 3577263 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Major Index and Inversion Number of Permutations
- On the Netto Inversion Number of a Sequence
- Ordered structures and partitions
- Permutation statistics and partitions
- The Hook Graphs of the Symmetric Group
- The inversion enumerator for labeled trees
- Permutation statistics and linear extensions of posets
- The major index polynomial for conjugacy classes of permutations
- Mahonian statistics on labeled forests
- Descent classes of permutations with a given number of fixed points
- On intervals in some posets of forests
- A simple transformation for Mahonian statistics on labelings of rake posets
- Connected order ideals and \(P\)-partitions
- Linear extensions and comparable pairs in partial orders
- An analogue of the plactic monoid for binary search trees
- Weighted-inversion statistics and their symmetry groups
- Non-ambiguous trees: new results and generalisation
- Whitney numbers for poset cones
- Counting shellings of complete bipartite graphs and trees
- A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions
- Trees, parking functions and factorizations of full cycles
- Tree descent polynomials: unimodality and central limit theorem
- Alternation acyclic tournaments
- Dyck tilings, increasing trees, descents, and inversions
- A multivariate ``inv hook formula for forests
- Hook length formulas for partially colored labeled forests
- Counting linear extensions of posets with determinants of hook lengths
- Sorting index and Mahonian-Stirling pairs for labeled forests
- How often are two permutations comparable?
- Signed mahonians on some trees and parabolic quotients
- Combinatorics of Poincaré's and Schröder's equations
- Generalized Dyck tilings
- The metric space of limit laws for \(q\)-hook formulas
- On \(q\)-integrals over order polytopes
- The algebra of binary search trees
- Polytopes and large counterexamples
- Counting linear extensions of posets with determinants of hook lengths
- Naruse hook formula for linear extensions of mobile posets
- Naruse hook formula for linear extensions of mobile posets
- Effective Poset Inequalities
- \(k\)-factorizations of the full cycle and generalized Mahonian statistics on \(k\)-forests
- Mahonian pairs
- Cyclotomic generating functions
- Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
- Chow rings of matroids as permutation representations
- q-hook length formulas for signed labeled forests
- Trees, forests, and total positivity. I: \(q\)-trees and \(q\)-forests matrices
- Tree hook length formulae, Feynman rules and B-series
- Trees, functional equations, and combinatorial Hopf algebras
This page was built for publication: q-hook length formulas for forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911620)
