A family of invariants of rooted forests |
| |
Authors: | Wenhua Zhao |
| |
Institution: | Department of Mathematics, Washington University in St. Louis, St. Louis, MO 63130-4899, USA |
| |
Abstract: | Let A be a commutative k-algebra over a field of k and Ξ a linear operator defined on A. We define a family of A-valued invariants Ψ for finite rooted forests by a recurrent algorithm using the operator Ξ and show that the invariant Ψ distinguishes rooted forests if (and only if) it distinguishes rooted trees T, and if (and only if) it is finer than the quantity α(T)=|Aut(T)| of rooted trees T. We also consider the generating function with , where is the set of rooted trees with n vertices. We show that the generating function U(q) satisfies the equation . Consequently, we get a recurrent formula for Un (n?1), namely, U1=Ξ(1) and Un=ΞSn−1(U1,U2,…,Un−1) for any n?2, where are the elementary Schur polynomials. We also show that the (strict) order polynomials and two well-known quasi-symmetric function invariants of rooted forests are in the family of invariants Ψ and derive some consequences about these well-known invariants from our general results on Ψ. Finally, we generalize the invariant Ψ to labeled planar forests and discuss its certain relations with the Hopf algebra in Foissy (Bull. Sci. Math. 126 (2002) 193) spanned by labeled planar forests. |
| |
Keywords: | 05C05 05A15 |
本文献已被 ScienceDirect 等数据库收录! |
|