Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A refinement of the formula for k-ary trees and the Gould-Vandermonde’s convolution. | A refinement of the formula for k-ary trees and the Gould-Vandermonde s convolution Ricky X. F. Chen Center for Combinatorics LPMC-TJKLC Nankai University Tianjin 300071 P. R. China ricky_chen@ Submitted Jul 10 2007 Accepted Mar 25 2007 Published Apr 3 2008 Mathematics Subject Classification 05A19 05C05 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 Ck 7 n fcn 7 W . 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. 1 Introduction Recently the author obtained the following identity involving the Catalan numbers Cn n V by accident which is similar to the identity 2 a in Riordan s book 6 p. 152-153 i 1 i 1 Ci ố0n for n 0 1 Ạ- n V i 0 X z where ỗ0n is the Kronecker symbol. It is well known 10 that Cn counts the number of 2-ary trees or complete binary trees with n internal vertices vertices with outdegree at least 1 . Now suppose the number of ordered forests with 7 h-ary trees and with total number of n internal vertices is C i7 n which is a natural generalization of the Catalan numbers. It is also well known 4 10 that i - 7 7 7 C n hn 7k n Then by generalizing the case Cn C2 1 n to C 7 n we obtain a generalization identity of 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R52 1 Theorem . For n 0 a p 7 2 C n E -i - i 0 p 1 i a n i 7 pi 7 pi 7 i 2 Actually we can even generalize 2 by introducing following notations For any vectors a a1 . at and b b1 . bt we denote a b if ai bi for all 1 i t We also define b a b1 a1 . bt at and a b Pk 1 akbk As usual any dimension vector with constant .
