Combinatorial Sums and Inversions

Traditional methods used for solving combinatorial sums (see, e.g., J. Riordan [18] or L. Comtet [1]) are used in R. L. Graham, D. E. Knuth, and O. Patashnik [8], where it is shown how to use the rules of binomial coefficients, Stirling numbers, and so on, for computing combinatorial sums. G. P. Egorychev [3] developed the method known as integral representation of sums. Gosper’s method [7] and the Petkovšek-Wilf-Zeilberger approach [17, 22, 23] are other well-known methods which nowadays are embodied in every system for computer algebra. An interesting method for evaluating combinatorial sums has emerged in the Riordan arrays concept, with significant early contributions due to R. Sprugnoli [19, 20]. As a matter of fact, Riordan arrays correspond to a special application of the method of coefficients that allows one to compute a vast number of combinatorial sums and inversions in a uniform and often very simple way. In particular, R. Sprugnoli showed how to prove with the Riordan array approach almost all identities in H. W. Gould’s book [5]. In this chapter the computation of combinatorial sums and inversions with Riordan arrays is presented in detail. Many other applications of the method can be found in [9, 11–16], while other characteristic combinatorial identities in several parameters have been recently studied with a Riordan array approach by A. Luzón, D. Merlini, M. A. Morón and R. Sprugnoli [10].