Two bijective proofs for the arborescent form of the Good-Lagrange formula and some applications to colored rooted trees and cacti

摘要

Goulden and Kulkarni (J. Combin. Theory Ser. A 80 (2) (1997) 295) give a bijective proof of an arborescent form of the Good-Lagrange multivariable inversion formula, This formula was first stated explicitly by Bender and Richmond (Electron. J. Combin. 5 (1) (1998) 4pp) but is implicit in Goulden and Kulkarni (1997). In this paper, we propose two new simple bijective proofs of this formula and we illustrate the interest of these proofs by applying them to the enumeration and random generation of colored rooted trees and rooted m-ary cacti. (C) 2003 Elsevier B.V. All rights reserved. [References: 35]