On Generalizations of the Stirling Number Triangles^{1}

Wolfdieter Lang

Institut für Theoretische Physik Universität Karlsruhe Kaiserstraße 12, D-76128 Karlsruhe, Germany

Email address: wolfdieter.lang@physik.uni-karlsruhe.de Home page: http://www-itp.physik.uni-karlsruhe.de/˜ wl

Abstract

Sequences of generalized Stirling numbers of both kinds are introduced. These sequences of triangles (i.e. infinite-dimensional lower triangular matrices) of numbers will be denoted by S2(k; n, m) and S1(k; n, m) with k ∈ Z. The original Stirling number triangles of the second and first kind arise when k = 1. S2(2; n, m) is identical with the unsigned S1(2; n, m) triangle, called S1p(2; n, m), which also represents the triangle of signless Lah numbers. Certain associated number triangles, denoted by s2(k; n, m) and s1(k; n, m), are also defined. Both s2(2; n, m) and s1(2; n + 1, m + 1) form Pascal’s triangle, and s2(−1, n, m) turns out to be Catalan’s triangle.

Generating functions are given for the columns of these triangles. Each S2(k) and S1(k) matrix is an example of a Jabotinsky matrix. The generating functions for the rows of these triangular arrays therefore constitute exponential convolution polynomials. The sequences of the row sums of these triangles are also considered.

These triangles are related to the problem of obtaining finite transformations from infinitesimal ones generated by x^{k} \frac{d}{dx}, for k ∈ Z.

AMS MSC numbers: 11B37, 11B68, 11B83, 11C08, 15A36

1 Overview

Stirling’s numbers of the second kind (also called subset numbers), and denoted by S2(n, m) (or \{ \begin{matrix}n \\ m \end{matrix} \} in

the notation of [3], or S_{n}^{(m)} in [1], or A008277 in the data-base [10]) can be defined by

E_{x}^{n} ≡ (x d_{x})^{n} = ∑_{m=1}^{n} S2(n, m) x^{m} d_{x}^{m} , n ∈ N,  (1)

1In memory of my mother Else Gertrud Lang.

where the derivative operator d_{x} ≡ \frac{d}{dx}, and E_{x} is the Euler operator satisfying E_{x} x^{k} = k x^{k}. A recursion relation can be derived from eq. 1 by considering x d_{x}(x d_{x})^{n−1}, using the convention S2(n, m) = 0 if n < m to interpret S2(n, m) as a lower triangular, infinite-dimensional matrix S2:

S2(n, m) = m S2(n − 1, m) + S2(n − 1, m − 1),  (2)

with initial values S2(n, 0) ≡ 0 and S2(1, 1) = 1. Because of eq. 1 these numbers arise when one asks how finite scale transformations (dilations) look, given infinitesimal ones. This is a special case of the exponentiation operation for Lie groups. The generator of the abelian Lie group of scale transformations x′ = λ x, λ ∈ R_{+}, is E_{x}. In order to exhibit these numbers within this framework consider first

e^{c x d_{x}} = ∑_{n=0}^{∞} \frac{c^{n}}{n!} E_{x}^{n} = 1 + ∑_{n=1}^{∞} \frac{c^{n}}{n!} ∑_{m=1}^{n} S2(n, m) x^{m} d_{x}^{m}  (3)

= 1 + ∑_{m=1}^{∞} ( ∑_{n=m}^{∞} \frac{c^{n}}{n!} S2(n, m)) x^{m} d_{x}^{m} = 1 + ∑_{m=1}^{∞} G2_{m}(c) x^{m} d_{x}^{m} .

In the third step an interchange of summation has been performed (we ignore questions of convergence here), and in the last step an exponential generating function (e.g.f.) has been introduced for the m−th column of the number triangle, or lower triangular matrix, S2. The recursion relation implies G2_{m}(c) = \frac{1}{m!} (G2(c))^{m}, with G2(c) = exp(c) − 1; therefore we obtain

e^{c x d_{x}} = ∑_{m=0}^{∞} \frac{1}{m!} (G2(c) x)^{m} d_{x}^{m} = : e^{(exp(c)−1)x d_{x}} : ,  (4)

where we have used the linear normal order symbol : A : from quantum physics. (: A : means expand A in powers of x and d_{x}, and move all operators d_{x} to the right-hand side, ignoring the usual commutation rule [d_{x}, x] ≡ d_{x} x − x d_{x} = 1. For example, : (x d_{x})^{m} : = x^{m} d_{x}^{m}.) This normal order prescription is applied to each term of the expanded exponential in eq. 4. From Taylor’s theorem, we see that for suitable functions f we have

e^{c x d_{x}} f(x) = : e^{(exp(c)−1)x d_{x}} : f(x) = f(x + (e^{c} − 1)x) = f(x′) ,  (5)

with x′ = e^{c} x. Therefore the parameter λ for finite scale transformations is λ = e^{c} if c is the parameter for infinitesimal transformations. In the context of Lie groups this fact is found by integrating the ordinary differential equation (see for example [2] and the references given there):

\frac{dx(α)}{dα} = c x(α),  (6)

for curves starting at a fixed x := x(α = 0). The finite transformation maps x to x′ := x(α = 1). x′ should not be confused with a derivative. In this work we will generalize this to the case E_{k;x} ≡ x^{k} d_{x} with k ∈ Z. It is clear from the solution of the differential equation

\frac{dx(α)}{dα} = c x^{k}(α), with initial condition x(α = 0) =: x and its transform x′ := x(α = 1),  (7)

that the scale transformation case k = 1 which has been treated above is special. For k ≠ 1, after separation of variables, we obtain the equation (x′)^{1−k} − x^{1−k} = (1 − k) c. Setting

x′ = (1 + g(k; c; x)) x  (8)

we have

1 + g(k; c; x) = (1 − (k − 1) c x^{k−1})^{− \frac{1}{k−1}} .  (9)

Therefore

e^{c x^{k} d_{x}} f(x) = f(x′) = f ((1 − (k − 1) c x^{k−1})^{− \frac{1}{k−1}} x)  (10)

for k ∈ Z \ {1}. The case k = 1 has been dealt with in eq. 5. It can be recovered from eq. 10 by taking the limit k − 1 → 0.

k−Stirling numbers of the second kind, which we will denote by S2(k; n, m), with S2(1; n, m) = S2(n, m) the ordinary Stirling subset numbers, emerge in a proof, independent of the one implied by eq. 10, of the following operator identity, valid for k ∈ Z,

e^{c x^{k} d_{x}} = : e^{g(k;c;x) x d_{x}} : ,  (11)

where g(k; c; x) is defined by eq. 9 for k ≠ 1 and g(1; c; x) = G2(c) (see eq. 4). By analogy with eq. 1 the S2(k; n, m) number triangle is defined by

E_{k;x}^{n} ≡ (x^{k} d_{x})^{n} = ∑_{m=1}^{n} S2(k; n, m) x^{m+(k−1) n} d_{x}^{m} , n ∈ N, k ∈ Z ,  (12)

with the further convention that S2(k; n, m) = 0 for n < m and S2(k; n, 0) = 0. These numbers will be shown to satisfy the recursion relation

S2(k; n, m) = ((k − 1)(n − 1) + m) S2(k; n − 1, m) + S2(k; n − 1, m − 1),  (13)

with S2(k; 1, 1) = 1 from eq. 12. The e.g.f. for the m−th column of the S2(k) triangle,

G2(k; m; x) := ∑_{n=m}^{∞} S2(k; n, m) \frac{x^{n}}{n!} ,  (14)

satisfies

G2(k; m; x) = \frac{1}{m!} (G2(k; x))^{m}  (15)

for k ≠ 1, with

G2(k; x) = (k − 1) g2(k; \frac{x}{k − 1}) ,  (16)

where

g2(k; y) := ∑_{n=1}^{∞} s2(k; n, 1) y^{n}  (17)

is the ordinary generating function (o.g.f.) for the first column of the triangle of numbers s2(k; n, m) which is associated to triangle S2(k; n, m) by^{2}

s2(k; n, m) := (k − 1)^{n−m} \frac{m!}{n!} S2(k; n, m) .  (18)

These number triangles, or lower triangular infinite-dimensional matrices, s2(k), which are here only defined for k ∈ Z \ {1}, obey the recursion relation

s2(k; n, m) = \frac{k − 1}{n} [(k − 1)(n − 1) + m] s2(k; n − 1, m) + \frac{m}{n} s2(k; n − 1, m − 1) ,  (19)

with

s2(k; n, m) = 0, n < m , s2(k; n, 0) = 0, s2(k; 1, 1) = 1 .  (20)

2These associated Stirling numbers of the second kind are not the ones of [5], p. 76, Table 2.

It follows that these numbers are nonnegative. At this stage it is not obvious that they are integers for every k ∈ Z \ {1}. The o.g.f. of the m-th column of the s2(k) matrix is

g2(k; m; y) := ∑_{n=m}^{∞} s2(k; n, m) y^{n} = (g2(k; y))^{m} ,  (21)

with

g2(k; y) = y c2(1 − k; y),  (22)

and, for l ∈ Z \ {0},

c2(l; y) = \frac{1 − (1 − l^{2} y)^{\frac{1}{l}}}{l y} .  (23)

It is clear from eq. 21 that s2(k) is a convolution triangle generated from its first column (cf. [4],[6],[9]). Such ordinary convolution triangles will be called Bell matrices [9] (see Note 7). For k ∈ Z \ {1}, eq. 16 now yields

G2(k; x) = −1 + (1 + (1 − k) x)^{\frac{1}{1−k}} ,  (24)

and letting k − 1 → 0 we obtain G2(1; x) = e^{x} − 1 = G2(x). The infinite-dimensional lower triangular matrices S2(k) with integer entries are examples of Jabotinsky matrices (cf. [4], which also contains earlier references). Therefore the o.g.f. of the rows of the triangle S2(k) are exponential (or binomial) convolution polynomials. In other words, the polynomials

S2_{n}(k; x) := ∑_{m=1}^{n} S2(k; n, m) x^{m} , S2_{0}(k; x) := 1 ,  (25)

satisfy

S2_{n}(k; x + y) = ∑_{p=0}^{n} \binom{n}{p} S2_{p}(k; x) S2_{n−p}(k; y) = ∑_{p=0}^{n} \binom{n}{p} S2_{p}(k; y) S2_{n−p}(k; x)  (26)

for k ∈ Z. In the notation of the umbral calculus (cf. [7]) the polynomials S2_{n}(k; x) are a special type of Sheffer polynomials called associated polynomial sequences. An equivalent notation used there for the general case is “Sheffer for (1, f(t))”. In our case f(t) = \overline{G2(k; t)}), where \overline{G2(k; t)} = (−1 + (1 + t)^{1−k})/(1 − k) if k ≠ 1. This is the compositional inverse of G2(k; t) from eq. 24. Also \overline{G2(1; t)} = ln(1 + t) can be obtained in the limit as 1 − k → 0. For negative k the S2(k) matrices also contain negative entries. The recursion of eq. 13 shows that it is possible to define nonnegative matrices by

S2p(−k; n, m) := (−1)^{n−m} S2(−k; n, m) , k ∈ N_{0}.  (27)

The e.g.f. for column m of the triangle S2p(−|k|) is

G2p(−|k|; m; x) = \frac{1}{m!} (G2p(−|k|; x))^{m}  (28)

with

G2p(−|k|; x) = − G2(−|k|; −x) = 1 − (1 − (|k| + 1) x)^{\frac{1}{|k|+1}} .  (29)

Eqs. 19 and 20 will be seen to imply that the s2(−|k|) matrices have always nonnegative entries. In Tables 1 and 2 we have listed for some of these s2(k) and S2(k) triangles the A-numbers under which they can be viewed in the on-line data-base [11] (see also [10]). This data-base will henceforth be quoted as EIS (Encyclopedia of Integer Sequences). These tables also give the A-numbers of the sequences formed by the first columns of the lower triangular matrices, and of the sequences of the row sums of these matrices. For l = 2 the function c2(l; y) defined in eq. 23 generates the well-known Catalan numbers. For l ∈ Z \ {0} it defines what we call l−Catalan numbers. For positive l these sequences were introduced by O. Gerard in EIS, who called them Patalan numbers. It will be proved later (see Note 11) that c2(l; y) does indeed generate integers. Their explicit form can be found in eq. 77.

The Stirling numbers of the first kind, S1(n, m) (S_{n}^{(m)} in [1], EIS: A008275), can be defined from the inversion of eq. 1 by

x^{n} d_{x}^{n} = ∑_{m=1}^{n} S1(n, m) (x d_{x})^{m} .  (30)

We also set S1(n, 0) ≡ 0 and S1(n, m) := 0 for n < m. In (infinite-dimensional) matrix notation we can write [4]

S1 · S2 := 1 = S2 · S1 .  (31)

The signless Stirling numbers of the first kind, also known as cycle numbers, S1p(n, m) (or [ \begin{matrix}n \\ m \end{matrix} ] in the

notation of [3]), are

S1p(n, m) := (−1)^{n−m} S1(n, m) .  (32)

Their recurrence formula is

S1p(n + 1, m) = n S1p(n, m) + S1p(n, m − 1) ,  (33)

with S1p(1, 1) = 1, S1p(n, 0) = 0 and S1p(n, m) = 0 for n < m.

The generalized k−Stirling numbers of the first kind S1(k; n, m) are defined analogously by inverting eq. 12, i.e.

x^{kn} d_{x}^{n} = ∑_{m=1}^{n} S1(k; n, m) x^{(k−1)(n−m)} (x^{k} d_{x})^{m} for k ∈ Z , n ∈ N .  (34)

In matrix notation:

S1(k) · S2(k) = 1 = S2(k) · S1(k) for k ∈ Z.  (35)

For k ∈ N we define the nonnegative k−Stirling numbers of the first kind by

S1p(k; n, m) := (−1)^{n−m} S1(k; n, m) .  (36)

For −k ∈ N_{0} the numbers S1(k; n, m) are nonnegative. The recurrence relation for k−Stirling numbers of the first kind is

S1(k; n, m) = −[(k − 1) m + n − 1] S1(k; n − 1, m) + S1(k; n − 1, m − 1) ,  (37)

with S1(k; 1, 1) = 1, S1(k; n, 0) = 0 and S1(k; n, m) = 0 for n < m. For k ≠ 1 we also introduce the associated k−Stirling numbers of the first kind ^{3}

s1(k; n, m) := (1 − k)^{n−m} \frac{m!}{n!} S1(k; n, m) ,  (38)

which turn out to be always nonnegative. They satisfy the recursion

s1(k; n, m) = \frac{k − 1}{n}((k − 1) m + n − 1) s1(k; n − 1, m) + \frac{m}{n} s1(k; n − 1, m − 1)  (39)

3These associated Stirling numbers of the first kind are not the ones appearing in [5], p. 75, table 2.

with s1(k; n, m) = 0 for n < m, s1(k; 1, 1) = 1 and s1(k; n, 0) := 0. At this stage it is not obvious that the s1(k; n, m) are in fact integers. The o.g.f. for the m−th column of the number triangle s1(k; n, m) will be shown to be

g1(k; m; y) = ∑_{n=m}^{∞} s1(k; n, m) y^{n} = (g1(k; y))^{m} ,  (40)

for k ∈ Z \ {1}, with

g1(k; y) = y c1(k − 1; y),  (41)

and, for l ∈ Z \ {0},

c1(l; y) = \frac{−1 + (1 − l y)^{−l}}{l^{2} y} .  (42)

Hence s1(k) is, like s2(k), a convolution triangle generated from its m = 1 column, i.e. both are Bell matrices. For l ∈ N the function c1(l; y) generates the numbers

c1(l; y) = ∑_{n=0}^{∞} c1_{n}^{(l)} y^{n} , c1_{n}^{(l)} = \binom{n + l}{l − 1} l^{n−1} .  (43)

For l = 2 this is the EIS sequence A001792 {1, 3, 8, 20, 48, ...}. For negative l, c1(l; y) becomes a polynomial in y; e.g. c1(−2; y) = 1 + y, or g1(−1; y) = y + y^{2}. The coefficients of these polynomials define a triangle of numbers found under the EIS number A049323. Their explicit form is, for l ∈ N,

c1_{n}^{(−l)} = \binom{l}{n + 1} l^{n−1} for n = 0, 1, ..., l − 1, and 0 otherwise.  (44)

Eq. 43 now implies, using eqs. 41 and 40, that s1(k; n, m) is indeed an integer for every k ∈ Z \ {1}. An explicit form for the entries in the first column is

s1(k; n, 1) = \{ \begin{matrix}\binom{k−2−n}{k−2} (k − 1)^{n−2} & for k = 2, 3, ..., and n ∈ N \\ \binom{|k|+1}{n} (|k| + 1)^{n−2} & for −k ∈ N_{0} , n = 1, 2, ...|k| + 1 . \end{matrix}  (45)

The e.g.f.s for the m−th column of the signless k−Stirling numbers of the first kind are then, for k = 2, 3, ...,

G1p(k; m; x) := ∑_{n=m}^{∞} S1p(k; n, m) \frac{x^{n}}{n!} ,  (46)
= \frac{1}{m!} [(k − 1) g1(k; \frac{x}{k − 1})]^{m} .  (47)

The case k = 1 corresponds to the ordinary unsigned Stirling numbers S1p(n, m) with e.g.f. for column m given by G1p(1; m; x) = \frac{1}{m!} (−ln(1 − x))^{m}. From eqs. 47, 41 and 42,

G1p(k; 1; x) = (k − 1) g1(k; \frac{x}{1 − x}) = \frac{1}{k − 1} (−1 + \frac{1}{(1 − x)^{k−1}} ) ,  (48)

and we recover the result for k = 1 from l’Hôpital’s rule in the limit k − 1 → 0. Note that G1(k; 1; x) = −G1p(k; 1; −x) = \overline{G2(k; 1; x)} for k ∈ Z. For −k ∈ N_{0} the e.g.f. for the m−th column of the nonnegative triangular matrix S1(−|k|) is, from eqs. 36 and 46, G1(−|k|; m; x) = (−1)^{m} G1p(−|k|; m; −x), hence

G1(k; 1; x) = \frac{1}{1 + |k|} (−1 + (1 + x)^{1+|k|}) for − k ∈ N_{0} .  (49)

For the signed matrix S1(−|k|) with elements defined by S1s(−|k|; n, m) := (−1)^{n−m} S1(−|k|, n, m) the e.g.f. of the m−th column is G1s(−|k|; m; x) = (−1)^{m} G1(−|k|; m; −x), i.e. G1s(−|k|; x) ≡ G1s(−|k|; 1; x) = (1 − (1 − x)^{1+|k|})/(1 + |k|) for k ∈ N_{0}.

Tables 3 and 4 give the EIS A-numbers of some of the number triangles s1(k), S1(k) and S1p(k). The A-numbers of the m = 1 column and of the sequence of row sums for each triangle are also given there.

The o.g.f. of the row sequences of triangle S1(k) are also exponential (or binomial) convolution polynomials. In other words the polynomials

S1_{n}(k; x) := ∑_{m=1}^{n} S1(k; n, m) x^{m} , S1_{0}(k; x) := 1 , k ∈ Z ,  (50)

satisfy eq. 26 with S2 replaced by S1. In the notation of the umbral calculus (cf. [7]) the polynomials S1_{n}(k; x) are a special type of Sheffer polynomials called associated polynomial sequences or “Sheffer for (1, f(t)).” Here f(t) = \overline{G1(k; t)}), where \overline{G1(k; t)} = G2(k; t) is given, for k ≠ 1, in eq. 24. Also \overline{G1(1; t)} = G2(1; t) = exp(t) − 1 is obtained in the limit as 1 − k → 0.

Each sequence of row sums of a triangle of the type considered in this work is generated by a function which depends on the generating function of the triangle’s first (m = 1) column. For the s2(k) and s1(k) triangles, which can be considered as Bell matrices, these o.g.f.s are, for k ∈ Z \ {1},

r2(k; x) = \frac{g2(k; x)}{1 − g2(k; x)} = \frac{−1 + [1 − (1 − k)^{2} x]^{\frac{1}{1−k}}}{k − [1 − (1 − k)^{2} x]^{\frac{1}{1−k}}} ,  (51)

r1(k; x) = \frac{g1(k; x)}{1 − g1(k; x)} = \frac{1 − [1 − (k − 1) x]^{k−1}}{(1 + (1 − k)^{2}) [1 − (k − 1) x]^{k−1} − 1}  (52)

For the S2(k) (k ∈ N_{0}) and S2p(k) (−k ∈ N_{0}) triangles, which can be interpreted as Jabotinsky matrices, the e.g.f.s for the sequences of row sums are

R2(k; x) = e^{G2(k;x)} − 1 = exp [−1 + (1 − (k − 1) x)^{\frac{1}{1−k}}] − 1 ,  (53)
R2p(−|k|; x) = e^{G2p(−|k|;x)} − 1 = exp [1 − (1 − (1 + |k|) x)^{\frac{1}{1+|k|}}] − 1 .  (54)

For the S1p(k) (k ∈ N_{0}) and S1(k) (−k ∈ N_{0}) triangles, which can also be interpreted as Jabotinsky matrices, the e.g.f.s for the sequences of row sums are

R1p(k; x) = e^{G1p(k;x)} − 1 = exp(\frac{1}{k − 1} [−1 + (1 − x)^{\frac{1}{k−1}} ]) − 1 ,  (55)

R1(−|k|; x) = e^{G1(−|k|;x)} − 1 = exp(\frac{1}{1 + |k|}[−1 + (1 + x)^{1+|k|}]) − 1 .  (56)

The special case k = 1 can be obtained for R2(k; x) and R1p(k; x) by taking the limit as k − 1 → 0. In Sections 2 and 3 we will give proofs of the results stated above.

2 k−Stirling numbers of the second kind

Definition 1: S2(k; n, m). The k-Stirling numbers of the second kind, S2(k; n, m), are defined for k ∈ Z by eq. 12.

Lemma 1: The numbers S2(k; n, m) satisfy the recursion relation eq. 13.

Proof: Consider (x^{k} d_{x})^{n} = x^{k} d_{x} (x^{k} d_{x})^{n−1} and use eq. 12 with n → n − 1 together with the lower triangular matrix conditions given after this eq. Then compare coefficients of {x^{m} d_{x}^{m}}_{1}^{n}. □

Note 1: It follows from eq. 13 and the initial conditions that the S2(k; n, m) are always integers.

Definition 2: s2(k; n, m). The associated k-Stirling numbers of the second kind, s2(k; n, m), are defined for k ∈ Z \ {1} by eq. 18. Lemma 2: The numbers s2(k; n, m) satisfy the recursion relation given by eqs. 19 and 20. Proof: Rewrite eq. 13 for s2(k; n, m). □ Note 2: That the s2(k; n, m) are indeed integers will be proved much later in Lemma 19. Note 3: For k = 1 eqs. 19 and 20 give the (infinite-dimensional) unit matrix s2(1) = 1. This will be used as the definition of s2(1). Lemma 3: Nonnegativity of s2(k). The entries of the lower triangular matrix s2(k) are nonnegative for each k ∈ Z. Proof: If k − 1 ≥ 0 this follows from eq. 19. For 1 − k ∈ N the first term in eq. 19 becomes negative if and only if (1 − k) (n − 1) < m and n − 1 ≥ m (otherwise s2(k; n − 1, m) vanishes). But the first condition contradicts the second. □ Lemma 4: The o.g.f. g2(k; m, y) defined in the first of eqs. 21 for the m−th column sequence of the lower triangular matrix s2(k) with k ∈ Z \ {1} satisfies the first order linear differential-difference equation

[1 − (k − 1)^{2} y] g2′(k; m, y) − m (k − 1) g2(k; m, y) − m g2(k; m − 1, y) = 0 ,  (57)
g2(k; m, 0) = 0 , m ∈ N; g2′(k; m, y)|_{y=0} = 0 , m ∈ {2, 3, ...} ; g2′(k; 1, y)|_{y=0} = s2(k; 1, 1) = 1. (58)

The prime denotes differentiation with respect to the variable y. Proof: Compute y \frac{d}{dy} ∑_{n=m}^{∞} n s2(k; n, m) y^{n} with the help of the recurrence relation in eqs. 19 and 20 for y ≠ 0. For y = 0 the conditions given in eq. 58 follow from the definition of g2(k; m, y). □ Lemma 5: Using g2(k; m, y) = (g2(k; 1, y))^{m}, g2(k; y) := g2(k; 1, y) satisfies the first order differential equation

[1 − (k − 1)^{2} y] g2′(k; y) − (k − 1) g2(k; y) − 1 = 0 .  (59)

for k ∈ Z \ {1}. Proof: Immediate from Lemma 4. □ Lemma 6: The solution to the differential eq. 59 with initial condition g2(k; 0) = 0 is, for k ∈ Z \ {1},

g2(k; y) = \frac{1}{[1 − (k − 1)^{2} y]^{\frac{1}{k−1}}} \frac{1 − [1 − (k − 1)^{2} y]^{\frac{1}{k−1}}}{k − 1} =: \frac{y}{[1 − (k − 1)^{2} y]^{\frac{1}{k−1}}} c2(k − 1; y) .  (60)

Proof: Standard integration of a first order inhomogeneous differential equation of the form g′(y)+f(y) g(y) = k(y). □ Note 4: Generalized Catalan numbers. The l-Catalan numbers (for l ∈ Z \ {0}) have

c2(l; x) := \frac{1 − [1 − l^{2} x]^{\frac{1}{l}}}{l x}  (61)

as o.g.f. The case l = 2 corresponds to the ordinary Catalan numbers (EIS A000108). For positive l these numbers have been called Patalan numbers by Gerard in EIS (cf. A025748-A025755 for l = 3..10). That c2(l; y) generates integers will follow later from the fact that s2(k; n, m) is always an integer (see Notes 2 and 11). Because c2(−l; x) = c2(l; x)/(1 − l^{2} x)^{\frac{1}{l}}, one can write g2(k; y) = y c2(1 − k; y), as stated in eq. 22. Consider the expansion 1/(1−l^{2} x)^{1/l} = ∑_{n=0}^{∞} b_{n}^{(l)} x^{n} , where b_{n}^{(l)} = l^{n} (∏_{j=1}^{n} (j l + 1 − l))/n! and b_{0}^{(l)} = 1, n ≥ 1. Therefore the sequence {c2_{n}^{(−l)}}_{n=0}^{∞} generated by c2(−l; x) for l ∈ N is the (ordinary) convolution of the sequence {b_{n}^{(l)}}_{n=0}^{∞} with the sequence {c2_{n}^{(l)}}_{n=0}^{∞}. See e.g. EIS A035323 for l = −10.

Since we have put s2(1) = 1 we take g2(1; y) = y.

Lemma 7: The e.g.f. for the m-th column sequence of the k−Stirling triangle of the second kind S2(k), defined in eq. 14, is G2(k; m; x) = \frac{1}{m!} (G2(k; 1; x))^{m}, m ∈ N, with G2(k; 1; x) ≡ G2(k; x) = (k − 1) g2(k; \frac{x}{k−1}) for k ≠ 1 and G2(1; 1; x) ≡ G2(1; x) = exp(x) − 1.

Proof: For k ≠ 1 substitute S2(k; n, m) from eq. 18 into the definition of G2(k; m; x), and then use eq. 21. For the ordinary Stirling numbers, i.e. for k = 1, the stated result is well-known [1]. □

Lemma 8: For k ∈ Z \ {1},

e^{c x^{k} d_{x}} = ∑_{0}^{∞} \frac{1}{m!} [g2(k; \frac{c}{k − 1} x^{k−1}) (k − 1) x]^{m} d_{x}^{m} = : e^{g(k;c;x) x d_{x}} : ,  (62)

where g(k; c; x) := g2(k; \frac{c}{k−1} x^{k−1}) (k − 1), and the normal order : A : notation has been explained in the paragraph following eq. 4.

Proof: Similar to that for ordinary Stirling numbers of the second kind, as explained in Section 1, eqs. 3 and 4. Expand the exponential and insert the definition of S2(k; n, m) from eq. 12 using the triangle convention stated there. Then exchange the row summation with the column summation (ignoring questions of convergence). After replacing S2(k; n, m) by s2(k; n, m), using eq. 18 (and remembering that k ≠ 1) we find the o.g.f. g2(k; m; \frac{c}{k−1} x^{k−1}) inside the column summation. The convolution property eq. 21 (Lemmas 4,5 and 6) then yields the first eq. of the lemma. The second follows from the definition of normal order, which is applied to each term in the expanded exponential. □

Note 5: For k ≠ 1, if we insert the o.g.f. g2(k; y) given in Lemma 6, or eqs. 22 and 23, we obtain the formula for g(k; c; x) given in eq. 9. For k = 1 we obtain g(1; c; x) = exp(c) − 1 from eq. 5.

Corollary 1: The operator identity in eq. 11, proved in Lemma 8, implies the shift property shown in eq. 10.

Proof: An applicaton of Taylor’s theorem. □

Note 6: A third proof of the shift property in eq. 10 can be given by using the well-known multiple commutator formula for exp (B) x^{l} exp(−B) for l ∈ N_{0}, setting the operator B = c E_{k;x} = c x^{k} d_{x} for k ∈ Z and the commutator [E_{k;x}, x^{l}] = l x^{l+k−1}. For k = 1 we find exp(c x d_{x}) x^{l} 1 = (exp(c) x)^{l} exp(c x d_{x}) 1 = (exp(c) x)^{l}. For k ≠ 1 we first obtain exp(c E_{k;x}) x^{l} exp(−c E_{k;x}) = ∑_{n=0}^{∞} \frac{1}{n!}(l/(k −1))_{n} (c (k −1) x^{k−1})^{n} using the rising factorial (or Pochhammer) symbol (ν)_{n} := ν (ν+1) ⋯ (ν+n−1). This implies exp(c x^{k} d_{x}) x^{l} 1 = [(1+g(k; c; x)) x]^{l} 1 with 1+g(k; c; x) given in eq. 9. The 1 on the right-hand side stands for any x−independent operator or function. Hence the shift property eq. 10 holds for polynomials and (formally) for power series f(x).

Lemma 9: For k ∈ Z the e.g.f. of the row polynomials S2_{n}(k; x) defined in eq. 25, G2(k; z, x) := ∑_{n=0}^{∞} S2_{n}(k; x) z^{n}/n!, is given by

G2(k; z, x) = e^{x G2(k;z)} ,  (63)

where G2(k; z) is the e.g.f. for the first (m = 1) column sequence of the triangular matrix S2(k) given in eq. 24.

Proof: Separate the n = 0 term in the definition of G2(k; z, x) and insert in the remaining expression the definition of the row polynomials eq. 25. Then interchange the row and column summation indices and use the definition of the e.g.f. G2(k; m; z) given in eq. 14. The convolution property Lemma 7, or eq. 15, then leads to the desired result. □

Note 7: Another way to state Lemma 9 is to write

S2(k; n, m) = [\frac{z^{n}}{n!} ] [x^{m}] e^{x G2(k;z)} ,  (64)

where [y^{k}] f(y) denotes the coefficient of y^{k} in the expansion of f(y). For each k ∈ Z a matrix constructed in this way from the entries of its first (m = 1) column (collected in the e.g.f. G2(k; z)) is called a Jabotinsky matrix. (See [4] for references to the original works. Note that we use Knuth’s n! F_{n}(x) as row (or Jabotinsky) polynomials. Knuth’s f(z) corresponds to our e.g.f. for the m = 1 column sequence.)

Another notation is used in the umbral calculus (cf. [7]). The row polynomials E_{n}(x) = ∑_{n=1}^{m} J(n, m) x^{n} built from a lower triangular Jabotinsky matrix J(n, m) are there called associated polynomial sequences. Their defining function is the compositional inverse of the e.g.f. f(t) used by Knuth and in the present work (cf. [7], p. 53). {E_{n}(x)} are special Sheffer polynomials for (1, f̄(t)) in the umbral notation (cf. [7], p. 107).

Yet another description of such convolution polynomials can be found in [9], where Jabotinsky matrices appear as a special case of so-called Riordan matrices (if one uses exponential generating functions). The corresponding matrix product furnishes a so-called Bell subgroup of the Riordan group (cf. [9], p. 238). In the sequel we shall reserve the names Riordan and Bell matrices for the case of ordinary convolutions.

Lemma 10: The exponential (or binomial) convolution property given in eq. 26 for polynomials S2_{n}(k; x), n ∈ N_{0} and fixed k, is equivalent to the functional equation

G2(k; z, x + y) = G2(k; z, x) G2(k; z, y) ,  (65)

which follows from eq. 63 for the e.g.f. G2(k; z, x) defined in Lemma 9.

Proof: Fix k and compare the coefficients of z^{n}/n! on both sides of this equation. □

Proposition 1: Exponential convolution property of the S2_{n}(k; x) polynomials. The row polynomials S2_{n}(k; x) defined in eq. 25 for n ∈ N_{0} satisfy for each k ∈ Z the exponential convolution property shown in eq. 26.

Proof: Lemma 10 with Lemma 9. □

Lemma 11: Row sums of ordinary convolution matrices [6]. The o.g.f. r(x) := ∑_{n=1}^{∞} r_{n} x^{n} of the row sums r_{n} := ∑_{m=1}^{n} s(n, m) of a lower triangular ordinary convolution matrix {s(n, m)}_{n≥m≥1} is given by

r(x) := \frac{g(x)}{1 − g(x)} ,  (66)

where g(x) is the o.g.f. of the first (m = 1) column of the matrix s(n, m).

Proof: Consider a lower triangular convolution matrix. By definition, the o.g.f. g(m; x) for its m−th column sequence is given by g(m; x) = (g(1; x))^{m} = g(x)^{m} for m ∈ N. The result follows by inserting into r(x) the definition of the row sums r_{n}, interchanging row and column summation indices and using the definition and convolution property of g(m; x). □

Lemma 12: Row sums of exponential convolution matrices. The e.g.f. R(x) := ∑_{n=1}^{∞} R_{n} x^{n}/n! of the row sums R_{n} := ∑_{m=1}^{n} S(n, m) of a lower triangular exponential convolution matrix {S(n, m)}_{n≥m≥1} is given by

R(x) := e^{G(x)} − 1 ,  (67)

where G(x) is the e.g.f. of the first (m = 1) column sequence of the matrix {S(n, m)}_{n≥m≥1}.

Proof: Analogous to the proof of Lemma 11. □

Proposition 2: O.g.f. for row sums of the s2(k) triangles. For k ∈ Z \ {1} the o.g.f. of the sequence of row sums of the lower triangular matrix s2(k) is given by eq. 51.

Proof: Lemma 11 and the g2(k; x) result from Lemma 6, eq. 60. □

Proposition 3: E.g.f. for the sequence of row sums of the S2(k) and S2p(k) triangles. For k ∈ N_{0} the e.g.f. of the sequence of row sums of the nonnegative lower triangular matrix S2(k), resp. S2p(k), defined from eq. 13, resp. eq. 27, is given by eq. 53, resp. eq. 54.

Proof: Lemma 12 and G2(k; x), resp. G2p(−k; x), from eq. 24, resp. eq. 29. □

3 k−Stirling numbers of the first kind

k−Stirling numbers of the first kind can be defined as the elements of the (infinite-dimensional, lower triangular) inverse matrix S1(k) to the matrix S2(k) formed from the k−Stirling numbers of the second kind.

Definition 3: k−Stirling numbers of the first kind, S1(k; n, m), are defined by

x^{n} d_{x}^{n} = ∑_{m=1}^{n} S1(k; n, m) x^{−m(k−1)} (x^{k} d_{x})^{m} , for k ∈ Z, n ∈ N .  (68)

Note that this equation is obtained from eq. 34 by multiplication by x^{−n(k−1)} on the left. Therefore the equations are equivalent for every k provided x ≠ 0. We set S1(k; n, m) = 0 if n < m, i.e. S1(k) is a lower triangular matrix.

Lemma 13: S2(k) · S1(k) = 1, or

∑_{m=p}^{n} S2(k; n, m) S1(k; m, p) = δ_{n,p}  (69)

for fixed k ∈ Z, n ∈ N and p ∈ N, where δ_{n,p} is the Kronecker symbol.

Proof: Insert eq. 68 with n → m and m → p into the defining eq. 12 for the S2(k; n, m) numbers, and then extend the p−sum from m to n, using lower triangularity of each matrix S1(k). After interchanging the summations over m and p we find, for all k ∈ Z, n ∈ N and x ≠ 0,

O_{x}(k; n) := x^{−(k−1)n} (x^{k} d_{x})^{n} = ∑_{p=1}^{n} δ(k; n, p) O_{x}(k; p) ,  (70)

with δ(k; n, p) := ∑_{m=p}^{n} S2(k; n, m) S1(k; m, p). Since the operators {O_{x}(k; p)}_{p=1}^{n} acting on functions f ∈ C^{n} are a linearly independent^{4}, eq. 70 implies δ(k; n, p) = δ_{n,p} for each k. □

Similarly, one finds

S1(k) · S2(k) = 1  (71)

after inserting eq. 12 with n → m, m → p into eq. 68. Now we compare coefficients of the operators {x^{p} d_{x}^{p}}_{1}^{n}.

Lemma 14: The k−Stirling numbers of the first kind satisfy the recurrence given in eq. 37.

Proof: Use x^{n} d_{x}^{n} = (x d_{x} − (n − 1)) x^{n−1} d_{x}^{n−1} and insert eq. 68 in both sides of this identity. After differentiation, remembering the triangularity of S1(k), we compare coefficients of the linearly independent operators {O_{x}(k; m)}_{m=1}^{n} defined in eq. 70. □

Note 8: It is obvious from the recurrence 37 together with the initial conditions that all S1(k; n, m) are integers for k ∈ Z.

Definition 4: s1(k; n, m). The associated k−Stirling numbers of the first kind, s1(k; n, m), are defined for k ∈ Z \ {1} by eq. 38.

4This linear independence can be proved by applying the differentiation operators \frac{1}{p!} O_{x}(k; p) for fixed k ∈ Z and p = 1, ..., n to the monomials x^{q}, for q = 1, .., n. The linear independence is then inferred from the non-singularity of the n × n matrix A_{q,p}(k) = \frac{1}{p!} ∏_{j=0}^{p−1}(q + j(k − 1)). In fact, Det A(k) = +1 for each k ∈ Z and n ∈ N.

Lemma 15: The numbers s1(k; n, m) satisfy the recurrence given in eq. 39.

Proof: Rewrite the recurrence relation eq. 37 for S1(k; n, m) with k ≠ 1. The lower triangularity of the matrix s1(k) is inherited from S1(k). □

Note 9: For k = 1 eq. 39 gives the unit matrix s1(1) = 1. This will be used as the definition of s1(1). Lemma 16: Nonnegativity of s1(k). The entries of the lower triangular matrix s1(k) are nonnegative for each k.

Proof: If k − 1 ≥ 0 this follows from eq. 39. For 1 − k ∈ N this follows from the fact that s1(k; n − 1, m) = 0 if n − 1 > (1 − k) m, i.e. if the coefficient of the first term in the recurrence eq. 39 is negative. This will be shown by induction on m. For m = 1 the assertion is true because only the first term in the recurrence is present, and since s1(k, 2 − k, 1) = 0, due to the vanishing coefficient of the first term in its recursion, the recurrence shows that s1(k; n − 1, 1) vanishes for n − 1 = 2 − k, 3 − k, ... (if n − 1 = 2 − k the multiplier in the first recursion term vanishes). Assuming the assertion holds for given m ≥ 1, i.e. s1(k; n − 1, m) = 0 for n − 1 > (1 − k) m, leads to a vanishing second term in the s1(k; n − 1, m + 1) recurrence for all n − 1 > (1 − k) m + 1. Therefore, s1(k; (1 − k) (m + 1) + 1, m + 1) will be zero because the coefficient of the first term of this recurrence vanishes and the second term is absent since (1 − k) (m + 1) > (1 − k) m. Then s1(k; n − 1, m + 1) vanishes recursively for all n − 1 ≥ (1 − k) (m + 1) + 1. □

Lemma 17: The o.g.f. for the m-th column of s1(k) (see eqs. 40, 41 and 42). s1(k) is a Bell matrix (see Note 7 for this name), i.e. the o.g.f. for the sequence {s1(k; n, m)}_{n=1}^{∞} is given by g1(k; m; y) = (g1(k; 1; y))^{m} and

g1(k; y) := g1(k; 1; y) = \frac{−1 + (1 − (k − 1) y)^{−(k−1)}}{(k − 1)^{2}} for k ∈ Z \ \{1\} .  (72)

Since we have set s1(1) = 1 we take g1(1; y) = y.

Proof: From the recurrence relation eq. 39 we find, for k ∈ Z, the first-order linear differential-difference equation

[1 − (k − 1) y] g1′(k; m; y) − m (k − 1)^{2} g1(k; m; y) − m g1(k; m − 1; y) = 0 ,  (73)
g1(k; m; 0) = 0 , m ∈ N; g1′(k; m; y)|_{y=0} = s1(k; 1, 1) δ_{m,1} = δ_{m,1}.  (74)

The prime denotes differentiation with respect to y. The y = 0 conditions follow from the definition of g1(k; m; y) in eq. 40. Eq. 73 is solved using g1(k; m; y) = (g1(k; 1; y))^{m}, which results in a standard linear inhomogeneous differential equation for g1(k; y) := g1(k; 1; y), namely

[1 − (k − 1) y] g1′(k; y) − (k − 1)^{2} g1(k; y) − 1 = 0 ,  (75)

with the initial condition g1(k; 0) = 0. The solution is given by equation eq. 72 (cf. eq. 41, 42). □

Note 10: Generalized EIS A001792 sequences. Analogous to the generalized Catalan numbers generated by c2(l; y) of eq. 23 (see Note 4), we can use c1(l; y) defined in eq. 42 as the o.g.f. for sequences {c1_{n}^{(l)}}_{n=0}^{∞}. We find that c1(1; y) = 1/(1 − y) generates EIS A000012 (powers of 1), c1(2; y) is the o.g.f. for the sequence A001792(n). The EIS A-numbers for the sequences for l = k − 1 are found in the second column of Table 3 for l = 1, ..., 5 and l = −1, ..., −6. See also EIS A053113. In order to have g1(1; y) = y we set c1(0; y) ≡ 1 (see eq. 41). An explicit expression for c1_{n}^{(l)} with l ∈ N is given in eq. 43. Also c1_{n}^{(0)} = δ_{n,0}, and c1(−l; x) is a polynomial in x for l ∈ N. For example, c1(−3; x) = 1 + 3 x + 3 x^{2}. The triangle of coefficients in these polynomials can be found as EIS A049323 (increasing powers of x), or A033842 (decreasing powers of x). The explicit form for these coefficients is given in eq. 44.

Lemma 18: The entries of the matrix s1(k) are integers for all k ∈ Z.

Proof: The first column of s1(k) consists of integers since c1(k − 1; y) generates the integers c1_{n}^{(k−1)} given explicitly in eqs. 43 and 44, and g1(k; y) is given by eq. 41 (see Lemma 17). The case k = 1 is trivial.

Since s1(k) is an ordinary convolution triangle (or Bell matrix) it is sufficient to prove that the first column consists of integers. □

Lemma 19: The entries of the matrix s2(k) are integers for all k ∈ Z.

Proof: Once this has been established, all entries of s2(k; n, m) are nonnegative integers by Lemma 3. For the proof we first substitute eqs. 18 and 38 into eq. 69. Define, for k ∈ Z, the signed matrix s2s(k) by s2s(k; n, m) := (−1)^{n−m} s2(k; n, m). Then eq. 69 implies

s2s(k) · s1(k) = 1 .  (76)

Using the fact that the s1(k; n, m) are integers from the previous lemma (from Lemma 16 they are even known to be nonnegative) this equation allows us to carry out the proof recursively. We omit the details. □

Note 11: Using Lemmas 16 and 19, eqs. 21 and 22 show that c2(l; y) = ∑_{n=0}^{∞} c2_{n}^{(l)} y^{n} defined in eq. 23 generates positive integers for all l ∈ Z \ {0}. Their explicit form is given by

c2_{n}^{(l)} = l^{n} ∏_{j=1}^{n} (j l − 1)/(n + 1)! .  (77)

By definition c2(0; y) := 1.

Lemma 20: The e.g.f. for the m − th column sequence of the unsigned k−Stirling triangle of the first kind, S1p(k), defined in eq. 36 for k ∈ N, is G1p(k; m; x) = \frac{1}{m!} (G1p(k; 1; x))^{m}, m ∈ N, with G1p(k; 1; x) ≡ G1p(k; x) = (k − 1) g1(k; \frac{x}{k−1}) for k = 2, 3, ... and G1p(1; 1; x) ≡ G1p(1; x) = − ln(1 − x).

Proof: For k ≥ 2 substitute S1p(k; n, m) from eqs. 36 and 38 into the definition of G1p(k; m; x) given in eq. 46. In this way the o.g.f. g1(k; m; y) appears in the desired form. The result for the ordinary unsigned Stirling numbers (k = 1) is well-known [1]. □

Note 12: Explicit form for G1p(k; m; x), k > 1: eq. 48 and Lemma 20. Equation 48 follows from the o.g.f. g1(k; m; y) in eqs. 40 and 72. This shows that G1p(k; 1; x) = − \overline{G2(k; −x)}, the negative compositional inverse of G2(k; −x) of eq. 24. Inverse Jabotinsky matrices like S2 and S1 (cf. eqs. 69 and 71) have first column e.g.f.’s which are inverse to each other in the compositional sense [4].

Lemma 21: Row polynomials for S1(k). For k ∈ Z the e.g.f. of the row polynomials S1_{n}(k; x) := ∑_{m=1}^{n} S1(k; n, m) x^{m} , n ∈ N, and S1_{0}(k; x) := 1 is

G1(k; z, x) := ∑_{n=0}^{∞} S1_{n}(k; x) z^{n}/n! = e^{x G1(k;z)} ,  (78)

where G1(k; z) = (−1 + (1 + z)^{1−k})/(1 − k) for k ≠ 1, and G1(1; z) = ln(1 + z) are the e.g.f.s for the first (m = 1) column sequences of the triangular matrices S1(k) .

Proof: Analogous to that of Lemma 9.

Note 13: S1(k; n, m) = [\frac{z^{n}}{n!} ] [x^{m}] e^{x G1(k;z)} (cf. Note 7).

Proposition 5: Exponential convolution property of the S1_{n}(k; x) polynomials. The row polynomials S1_{n}(k; x) defined in Lemma 21 for n ∈ N_{0}, satisfy for each k ∈ Z the exponential (or binomial) convolution property shown in eq. 26 with S2 replaced everywhere by S1.

Proof: For fixed k, compare the coefficients of z^{n}/n! on both sides of the identity G1(k; z, x + y) = G1(k; z, x) G1(k; z, y) . □

Note 14: In the notation of the umbral calculus (cf. [7]) the polynomials S1_{n}(k; x) are called associated polynomial (or Sheffer) sequences for (1, \overline{G1(k; t)} = G2(k; t)). For k ≠ 1 G2(k; t) is given in eq. 24. Also \overline{G1(1; t)} = G2(1; t) = exp(t) − 1.

Proposition 6: O.g.f. for row sums of s1(k) triangles. For k ∈ Z \ {1} the o.g.f. of the sequence of row sums of the lower triangular matrix s1(k) is given by eq. 52.

Proof: Lemma 11 and the g1(k; x) result in Lemma 17. □

Proposition 7: E.g.f. of the sequence of row sums of S1p(k) and S1(−|k|) triangles. For k ∈ N_{0} the e.g.f. of the sequence of row sums of the nonnegative lower triangular matrix S1p(k), resp. S1(−|k|), defined in eq. 36, resp. eq. 37, is given by eq. 55, resp. eq. 56.

Proof: Lemma 12 and G1p(k; x), resp. G1(−|k|; x), from Lemma 20, i.e. eq. 48, resp. eq. 49. □

Note 15: Row-sums of signed S1(k), k ∈ N, resp. S1s(−|k|) triangles. Here Lemma 12 applies with the e.g.f.s G1(k; x), resp. G1s(−|k|; x), given in the first line after eq. 78, resp. in the paragraph after eq. 49.

Acknowledgements

The author would like to thank Stefan Theisen for a conversation at a very early stage of this work (Note 6, case k = 1). Thanks go also to Norbert Dragon who pointed out his web-pages (ref. [2]). This work has its origin in an exercise in the author’s 1998/1999 lectures on conformal field theory (Konforme Feldtheorie, Blatt 1, Aufgabe 2, available as a ps.gz file under http://www-itp.physik.uni-karlsruhe.de/˜ wl/Uebungen.html).

References

[1] M. Abramowitz and I. A. Stegun: Handbook of Mathematical Functions, Dover, 1968.

[2] N. Dragon: Konforme Transformationen, ps.gz file:

http://www.itp.uni-hannover.de/˜ dragon/Group.html, and references given there.

[3] R.L. Graham, D.E. Knuth, and O. Patashnik: Concrete Mathematics, Addison-Wesley, Reading MA, 1989.

[4] D.E. Knuth: Convolution polynomials, The Mathematica J., 2.1 (1992), 67-78.

[5] J. Riordan: An Introduction to Combinatorial Analysis, Wiley, New-York, 1958.

[6] D.G. Rogers: Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301-310.

[7] S. Roman: The Umbral Calculus, Academic Press, New York, 1984

[8] L.W. Shapiro: A Catalan triangle, Discrete Math. 14 (1976), 83-90.

[9] L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson: The Riordan group, Discrete Appl. Math. 34 (1991), 229-239.

[10] N.J.A. Sloane and S. Plouffe: The Encyclopedia of Integer Sequences, Academic Press, San Diego, 1995.

[11] N. J. A. Sloane (2000), The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/˜ njas/sequences/.

Table 1: Associated k-Stirling number triangles of the second kind s2(k), k ≠ 1 s2(1) := 1

k  A-number of  A-number of  A-number of
triangle  sequence of first column sequence of row sums

⋮

-5  A049224  A025751 (Gerard)  A025759 (Gerard)
-4  A049223  A025750 (Gerard)  A025758 (Gerard)
-3  A049213  A025749 (Gerard)  A025757 (Gerard)
-2  A048966  A025748 (Gerard)  A025756 (Gerard)
-1  A033184 (Catalan)  A000108(n − 1)  A000108 (Catalan)
0  A023531 (1 matrix)  A000007(n − 1)  A000012 (powers of 1)
2 A007318(n − 1, m − 1) (Pascal)  A000012  A000079 (powers of 2)
3  A035324  A001700(n − 1)  A049027
4  A035529  A034171(n − 1)  A049028
5  A048882  A034255(n − 1)  A048965
6  A049375  A034687  A039746

⋮

Table 2: k-Stirling number triangles of the second kind

S2(k), k = 0, 1, 2, ...,  S2p(k), k = 0, −1, −2, ...

k  A-number of  A-number of  A-number of
triangle  sequence of first column  sequence of row sums

⋮

-5  A013988  A008543(n − 1) (Keane)  A028844

-4  A011801  A008546(n − 1) (Keane)  A028575

-3  A000369  A008545(n − 1) (Keane)  A016036

-2  A004747  A008544(n − 1) (Keane)  A015735

-1 A001497(n − 1, m − 1) (Bessel) A001147(n − 1) (double factorials) A001515 (Riordan)

0  A023531 (1 matrix)  A000007(n − 1)  A000012 (powers of 1)

1  A008277 (Stirling 2nd kind)  A000012 (powers of 1)  A000110 (Bell)

2  A008297 (unsigned Lah)  A000142 (factorials)  A000262 (Riordan)

3  A035342  A001147 (2-factorials)  A049118

4  A035469  A007559 (3-factorials)  A049119

5  A049029  A007696 (4-factorials)  A049120

6  A049385  A008548 (5-factorials)  A049412

⋮

Table 3: Associated k-Stirling number triangles of the first kind s1(k), k ≠ 1 s1(1) := 1

k  A-number of  A-number of  A-number of
triangle  sequence of first column  sequence of row sums

⋮

-5  A049327  A049323(5,m)  A049351
-4  A049326  A049323(4,m)  A049350
-3  A049325  A049323(3,m)  A049349
-2  A049324  A049323(2,m)  A049348
-1  A030528  A019590=A049323(1, m)  A000045(n + 1) (Fibonacci)
0  A023531 (1 matrix)  A000007(n − 1)=A049323(0,m)  A000012 (powers of 1)
2 A007318(n − 1, m − 1) (Pascal)  A000012 (powers of 1)  A000079 (powers of 2)
3  A030523  A001792  A039717
4  A030524  A036068  A043553
5  A030526  A036070  A045624
6  A030527  A036083  A046088

⋮

Table 4: k-Stirling number triangles of the first kind

S1p(k), k = 0, 1, 2, ...,  S1(k), k = 0, −1, −2, ...

k  A-number of  A-number of  A-number of
triangle  sequence of first column  sequence of row sums

⋮

-5  A049411  A008279(5,n − 1) (numbperm)  A049431

-4  A049424  A008279(4,n − 1) (numbperm)  A049427

-3  A049410  A008279(3,n − 1) (numbperm)  A049426

-2  A049404  A008279(2,n − 1) (numbperm)  A049425

-1  A049403  A008279(1,n − 1) (numbperm)  A000085

0  A023531 (1 matrix)  A000007(n − 1)  A000012 (powers of 1)

1 A008275 (unsigned Stirling 1st kind)  A000142(n − 1)  A000142 (factorials)

2  A008297 (unsigned Lah)  A000142 (factorials)  A000262 (Riordan)

3  A046089  A001710(n + 1) (Mitrinovic^{2})  A049376

4  A035469  A001715(n + 2) (Mitrinovic^{2})  A049377

5  A049353  A001720(n + 3) (Mitrinovic^{2})  A049378

6  A049374  A001725(n + 4) (Mitrinovic^{2})  A049402

⋮

(Concerned with sequences A000007, A000012, A000045, A000079, A000085, A000108, A000110, A000142, A000262, A000369, A001147, A001497, A001515, A001700, A001710, A001715, A001720, A001725, A001792, A004747, A007318, A007559, A007696, A008275, A008277, A008279, A008297, A008543, A008544, A008545, A008546, A008548, A011801, A013988, A015735, A016036, A019590, A023531, A025748, A025748-A025755, A025749, A025750, A025751, A025756, A025757, A025758, A025759, A028575, A028844, A030523, A030524, A030526, A030527, A030528, A033184, A033842, A034171, A034255, A034687, A035323, A035324, A035342, A035469, A035529, A036068, A036070, A036083, A039717, A039746, A043553, A045624, A046088, A046089, A048882, A048965, A048966, A049027, A049028, A049029, A049118, A049119, A049120, A049213, A049223, A049224, A049323, A049324, A049325, A049326, A049327, A049348, A049349, A049350, A049351, A049353, A049374, A049375, A049376, A049377, A049378, A049385, A049402, A049403, A049404, A049410, A049411, A049412, A049424, A049425, A049426, A049427, A049431, A053113.)

Received Feb. 11, 2000; published in Journal of Integer Sequences Sept. 13, 2000; minor editorial changes Nov. 30, 2000.

Return to Journal of Integer Sequences home page.