Disposition Polynomials and Plane Trees

William Y. C. Chen and Janet F.F. Peng

  Abstract:   We define the disposition polynomial Rm(x1, x2,..., xn) as k=0m-1(x1 + x2 + ... + xn + k). When m=n-1, this polynomial becomes the generating function of plane trees with respect to the number of younger children and the number of elder children obtained by Guo and Zeng. They asked for a combinatorial proof of the formula. We find a combinatorial interpretation of the disposition polynomials in terms of the number of right-to-left minima of each linear order in a disposition. Then we establish a bijection between plane trees on n vertices and dispositions from {1, 2,..., n-1} to {1, 2,..., n} in the spirit of the Prüfer correspondence, which gives an answer to the question of Guo and Zeng. This bijection also provides an answer to another question of Guo and Zeng concerning an identity on the plane tree expansion of a polynomial introduced by Gessel and Seo.

  AMS Classification:  05A15, 05A19.

  disposition, disposition polynomial, plane tree, Prüfer correspondence

  Download:   pdf