Increasing Trees and the Degree-Chromatic Polynomial

Abstract

This paper studies increasing trees on n labeled vertices, in which labels increase from the root to the leaves. It is known that the number of binary increasing trees coincides with the number of alternating permutations (Euler numbers). Riordan obtained explicit formulas for the numbers of ternary and quaternary trees. This article derives a general formula for the number of m-ary increasing trees for any m. The main result is expressed in terms of the degree-chromatic polynomial of the complete graph and Bell polynomials. It is shown how the corresponding generating function is related to the inversion problem and how combinatorial methods, including the lemma on coefficients of the multiplicative inverse function and the Lagrange inversion formula, can be used to compute the coefficients. A connection is also established between the values of the degree-chromatic polynomial at λ = −1 and the numbers of special permutations studied by Gessel.

More by Medet Jumadildayev

• Binomial coefficients and the operadic butterflyarXiv · 2026
• Enumeration of multipartite series-reduced treesarXiv · 2025
• One Model to Rule Them all: A Universal Transformer for Biometric MatchingIEEE Access · 2024 · Citations: 8
• Euler tangent numbers modulo 720 and Genocchi numbers modulo 45Proceedings of the Japan Academy Series A Mathematical Sciences · 2022