Journal of Integer Sequences, Vol. 23 (2020), Article 20.5.5

Recurrent Combinatorial Sums and Binomial-Type Theorems

Michael Z. Spivey
Department of Mathematics and Computer Science
University of Puget Sound
Tacoma, WA 98416-1043


We prove that several known combinatorial sum identities, including identities featuring the binomial coefficients, both kinds of Stirling numbers, the Lah numbers, both kinds of associated Stirling numbers, and first- and second-order Eulerian numbers, are all special cases of a single identity satisfying a simple one-term recurrence. Moreover, subject to a certain set of restrictions, these special cases are the only identities featuring the aforementioned numbers that also satisfy this one-term recurrence. We then derive formulas for the coefficients involved when converting between multifactorial powers (a generalization of rising and of falling factorial powers) and ordinary powers, as well as some conditions under which numbers satisfying a general two-term combinatorial recurrence can be considered inverses of each other. Next, we derive conditions under which numbers that satisfy a general two-term recurrence also satisfy a binomial-type theorem, and we show that the binomial coefficients and the Stirling numbers of the first kind are the only numbers mentioned earlier that exhibit these conditions. Finally, we give a combinatorial proof of a binomial-type theorem satisfied by the Stirling numbers of the first kind.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000142 A001147 A007318 A008275 A008277 A008292 A008297 A008299 A008306 A008517 A048994 A105278.)

Received May 9 2019; revised version received December 13 2019; January 9 2020. Published in Journal of Integer Sequences, June 3 2020.

Return to Journal of Integer Sequences home page