A refinement of the formula for $k$-ary trees and the Gould-Vandermonde's convolution

Abstract

In this paper, we present an involution on some kind of colored $k$-ary trees which provides a combinatorial proof of a combinatorial sum involving the generalized Catalan numbers $C_{k,\gamma }(n)=\frac{\gamma }{kn+\gamma }\left(\genfrac{}{}{0ex}{}{kn+\gamma }{n}\right)$. From the combinatorial sum, we refine the formula for $k$-ary trees and obtain an implicit formula for the generating function of the generalized Catalan numbers which obviously implies a Vandermonde type convolution generalized by Gould. Furthermore, we also obtain a combinatorial sum involving a vector generalization of the Catalan numbers by an extension of our involution.

Another informative title may be "A linear recurrence for generalized Catalan numbers and its applications"