Abstract:   We define the disposition polynomial R_m (x₁, x₂,..., x_n) as ∏_k=0^m-1 (x₁ + x₂ + ... + x_n + 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

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

  Download:   pdf