The Combinatorics of Polynomial Sequences

Abstract

We present a combinatorial model for the several kinds of polynomial sequences of binomial type and develop many of the theorems about them from this model. In the first section, we present a prefab model for the binomial formula and the generating‐function theorem. In Sec. 2, we introduce the notion of U‐graph and give examples of binomial prefabs of U‐graphs. The umbral composition of U‐graphs provides an interpretation of umbral composition of polynomial sequences in Sees. 3 and 5. Rota's interpretation of the Stirling numbers of the first kind as sums of the Mobius function in the partition lattice inspired our model for inverse sequences of binomial type in Sec. 4. Section 6 contains combinatorial proofs of several operator‐theoretic results. The actions of shift operators and delta operators are explained in set‐theoretic terms. Finally, in Sec. 6 we give a model for cross sequences and Sheffer sequences which is consistent with their decomposition into sequences of binomial type. This provides an interpretation of shift‐invariant operators. Of course, all of these interpretations require that the coefficients involved be integer and usually non‐negative as well.