Recursively defined combinatorial functions: extending Galton's board

摘要

Many functions in combinatorics follow simple recursive relations of the type F(n,k) = a_(n-1,k)F(n - 1,k)+b_(n-1,k-1)F(n - 1,k - 1). Treating such functions as (infinite) triangular matrices and calling a_(n,k) and b_(n,k) generators of F, our paper will study the following question: Given two triangular arrays and their generators, how can we give explicit formulas for the generators of the product matrix? Our results can be applied to factor infinite matrices with specific types of generators (e.g. a_(n,k) = a'_n + a"_k) into matrices with 'simpler' types of generators. These factorization results then can be used to give construction methods for inverse matrices (yielding conditions for self-inverse matrices), and results for convolutions of recursively defined functions. Slightly extending the basic techniques, we will even be able to deal with certain cases of nontriangular infinite matrices. As a side-effect, many seemingly separate results about recursive combinatorial functions will be shown to be special cases of the general framework developed here.