Combinatorial Interpretation of Generalized Stirling Numbers

Wolfdieter Lang Institut für Theoretische Physik Universität Karlsruhe D-76128 Karlsruhe Germany

           wolfdieter.lang@particle.uni-karlsruhe.de

Abstract A combinatorial interpretation of the earlier studied generalized Stirling numbers, emerging in a normal ordering problem and its inversion, is given. It involves unordered forests of certain types of labeled trees. Partition number arrays related to such forests are also presented.

1 Introduction and Summary

The generalized Stirling numbers of the second kind S(k;n,m), k ∈ ℤ, n, m ∈ ℕ_{0}, appear in the normal ordering of powers (x^{k} d_{x})^{n} according to

(x^{k} d_{x})^{n} = ∑_{m=1}^{n} S(k; n, m) x^{m+(k−1) n} d_{x}^{m} .  (1)

In the inverse problem the generalized Stirling numbers of the first kind s(k;n,m) enter as

x^{kn} d_{x}^{n} = ∑_{m=1}^{n} s(k; n, m) x^{(k−1)(n−m)} (x^{k} d_{x})^{m} .  (2)

These numbers coincide for k = 1 with the ordinary Stirling numbers. The author [15] has previously investigated the k−families of number triangles S(k) and s(k).^{1} For given k the recurrence relations are:

1In this reference the notation is different, namely S2 and S1 are used for S and s, respectively. The associated number triangles s2 and s1 will not appear in the present work.

S(k; n, m) = ((k − 1)(n − 1) + m) S(k; n − 1, m) + S(k; n − 1, m − 1)  (3)

and

s(k; n, m) = −[(k − 1) m + n − 1] s(k; n − 1, m) + s(k; n − 1, m − 1) ,  (4)

with the triangle conditions: S(k;n,m) = 0 for n < m, and S(k; n, 0) = δ_{n,0} . δ_{n,m} is the Kronecker symbol. Similarly: s(k; n, m) = 0 for n < m, and s(k; n, 0) = δ_{n,0} . The S(k;n,m) numbers have already been considered by Carlitz [8] as special cases. See eq. 2 there, with μ → 1 and λ → k − 1. They also have been used by Comtet in [10, 4.Example] with P_{n,l}(a) = S(a + 1; n, l), where the recurrence and an explicit form involving a sum has been given. The ordinary Stirling numbers of the second kind have been encountered in the

reordering problem as stated above by Grunert [13, §4 ff.], where Ck_{n} = S(1; k, n) = S(k, n).

A combinatorial interpretation of the S(n, m) numbers is well known: there are S(n, m) ways to partition a set of n elements into m nonempty subsets. Therefore, these numbers are also called subset numbers in Graham et al. [12, p. 244]. See also Stanley [19, p. 33], and Charalambides [9, p. 96 and ch. 8]. As a spin-off we shall find another interpretation as numbers of forests composed of certain increasing trees.

The aim of this paper is to find combinatorial meanings for the k−families |S(k; n, m)| and |s(k; n, m)|. Because all these lower diagonal number triangles are of the Jabotinsky (a special Sheffer) type, i.e., possess the binomial (also called exponential) convolution property, they count unordered m−forests composed of certain vertex labeled trees with n vertices. These trees will be enumerated by |S(k; n, 1)| and |s(k; n, 1)|, respectively, for each k ∈ ℤ. S(k; n, 1), for k ∈ ℕ, will be seen to give the number of plane, k−ary rooted increasing trees with n vertices (including the root vertex). This stems from the fact that the exponential generating functions (e.g.f.) of these numbers are [15]

g2(k; x) = −1 + (1 + (1 − k) x)^{\frac{1}{1−k}} , k = 2, 3, …,  (5)

and g2(1; x) = −1 + e^{x}. Such trees fit into the varieties of trees investigated by Bergeron et al. [3], leading to the stated result. g2(0; x) = x represents the trivial one vertex tree, the root with label 1.

The signless (also called absolute) numbers |S(−k; n, m)| = (−1)^{n−m} S(−k; n, m), k ∈ ℕ_{0}, have for their first column members |S(−k; n, 1)| the e.g.f.

g2p(k; x) = 1 − (1 − (k + 1) x)^{\frac{1}{k+1}} = − g2(−k; −x) , k ∈ ℕ_{0} .  (6)

This also fits into the varieties of increasing trees considered by Bergeron et al. [3] because plane increasing trees with vertices of outdegree r ∈ ℕ_{0} come in (r + k − 1) types. They will be called (incomplete) (r + k − 1)−ary trees. In general an outdegree r = 0 is reserved for the one vertex tree given by the root and for leaves (end vertices) of a tree. The one vertex tree is always considered separately because it always appears just once. Instead of (r + k − 1)-ary vertices one can also use a repertoire of r + k − 1 colors and chose r of them to color the successors of a vertex with outdegree r = 0, 1, . . .. The color for the one vertex tree is taken as white (no color).

The non-negative numbers |s(k; n, m)| = (−1)^{n−m} s(k; n, m), k ∈ ℕ_{0}, with e.g.f. for the first column members |s(k; n, 1)|

g1p(k; x) = \frac{1}{k − 1} (−1 + \frac{1}{(1 − x)^{k−1}} ) , k = 0, 2, 3, …  (7)

and g1p(1; x) = − ln(1 − x), do, for k ≥ 3, not count any of the tree varieties considered by Bergeron et al. [3]. The case k = 0 is trivial, because there is just the trivial tree composed of one vertex, the root. The case k = 1 — the ordinary unsigned Stirling numbers of the first kind — is encompassed by this study [3] in that |s(n, 1)| counts the number of unordered (nonplane) increasing rooted trees with n vertices. This provides another combinatorial meaning besides their usual cycle number characterization. It turns out that these trees are the nonplane analogons of the plane ones counted by |S(−1; n, 1)|. Also the k = 2 instance, |s(2; n, 1)|, fits into the above mentioned study because one finds that these numbers coincide with S(2; n, 1) which counts plane binary increasing trees. These are the unsigned Lah numbers, Sloane’s OEIS [18, |\underline{A008297}| (first column, m = 1)]. It is also possible to give these numbers a meaning in the nonplane increasing tree setup. For all k ≥ 3, however, the [3] varieties are not sufficient. In accordance with the recurrence relation one can give a somewhat trivial tree and forest interpretation for the |s(k; n, m)| numbers. For example, |s(3; n, 1)| counts the number of n vertex (including the root) increasing plane trees with only outdegrees 0 and 1 where every vertex of depth d ∈ ℕ_{0} is of the (d + 3)-ary type. The depth of a vertex is its distance from the root, the number of parents. Another equivalent way to define these numbers uses special depth dependent vertex coloring for trees with outdegrees 0 and 1. This situation pertains to all k ≥ 3, providing thus new classes of increasing trees not covered by the study [3].

The non-negative numbers s(−k; n, m) with k ∈ ℕ, have as e.g.f. for s(−k; n, 1)

g1(−k; x) = \frac{1}{1 + k} (−1 + (1 + x)^{1+k}) = −g1p(−k; −x) , k ∈ ℕ .  (8)

For every k ∈ ℕ it follows that these numbers do also not count trees of the variety considered by Bergeron et al. [3]. Again, the recurrence relation (4) helps to identify trees and forests with only outdegrees 0 and 1 which are counted by these s(−k; n, m) numbers.

Finally, maps from the set of partitions of n with m parts to numbers counting various types of forests considered in this work are presented. These number arrays will be called partition number arrays. The generalized Stirling numbers are sums over these array numbers for fixed part number m.

2 Generalized Stirling numbers of the second kind

As anticipated in the Introduction the generalized Stirling numbers |S(k; n, m)| and |s(k; n, m)| count for many k values (but not for all) certain m-forests of increasing trees, either plane or nonplane, which fall into the varieties of trees studied by Bergeron et al. [3]. Therefore, some results from this study which are important for this work will be recapitulated.

We start with some definitions and refer the reader to Stanley [19, Appendix, pp. 293–5], for general definitions regarding trees and forests. For trees the notions plane and ordered are synonyms. This may seem confusing because, e.g., in Fig. A-2, p. 295 of this reference, the second tree would be equivalent to the last one if in the plane a rotation of subtrees around the root vertex would be allowed.

Definition 1. A labeled tree of size n, T_{n}, is a rooted tree with n vertices (nodes), including the root vertex, labeled with distinct elements from the set [n] ≡ I_{n} = {1, 2, …, n}.

Definition 2. An increasing tree of size n is a labeled tree of size n with the sequence of labels from the root to any leaf (end vertex with degree 1, outdegree 0) increasing.

Example 3. Stanley [19, p. 295, Fig. A-2] shows some ordered increasing trees of size 6. There are more than the two types shown, viz., C_{5} = 42 (the fifth Catalan number). Altogether there are 9!! = 945 ordered increasing trees of size 6 (compare with our Figure 4).

For the analysis the most important object is the generating function (g.f.) for the numbers s_{r} of available vertex types with outdegree r. For the root, the outdegree coincides with the degree. The trivial one vertex tree consists of the root with r = 0, and there is always only one vertex type s_{0} = 1. For trees with more than one vertex, the leaves (end vertices) have also r = 0 but degree 1. For ordered (plane) trees the ordinary generating function (o.g.f.) ϕ(y) = 1 + ∑_{r≥1} s_{r} y^{r} enters, and for unordered (nonplane) trees the e.g.f.

φ(y) = 1 + ∑_{r≥1} s_{r} \frac{y^{r}}{r!} is used. For example, for incomplete ternary (3-ary) trees one has

ϕ(y) = 1 + 3 y + 3 y^{2} + y^{3} in the ordered case, and φ(y) = 1 + 3 y + 3 \frac{y^{2}}{2!} + \frac{y^{3}}{3!} in the unordered case. s_{0} = 1, as mentioned above, and a ternary vertex has three possible out legs (usually drawn downwards at equal angles). Therefore s_{1} = 3 because there are three possible legs to choose. s_{2} = 3 because one of the three possible legs is not present. s_{3} = 1 because there is only one type of vertex with all three legs present. The ordered trees shown in Stanley [19, Fig. A-2, p. 295] could belong to ϕ(y) = 1 + 2 y + y^{2} = (1 + y)^{2}, i.e., ordered (incomplete) binary trees.

Proposition 4. [3]

If Y (z) = ∑_{n≥0} Y_{n} \frac{z^{n}}{n!} is the e.g.f. for \{Y_{n}\}, with Y_{n} the number of increasing labeled trees

of size n, and ϕ(y), resp. φ(y), the outdegree g.f.s, then

∫_{0}^{Y (z)} \frac{dy}{Φ(y)} = z, with Φ ∈ \{ϕ, φ\} .  (9)

A differential way of writing this is \frac{dY (z)}{dz} = Φ(Y (z)) together with the initial condition Y (0) = 0 (no tree of size 0). The explicit solution is written in the form of an Abel equation cf. [2, p. 14, (1.17) and footnote 7]).

Y (z) = F^{[−1]} [F (0) + z] , with F [y] := ∫ \frac{dy}{Φ(y)} .  (10)

Here F^{[−1]} denotes the compositional inverse of F, the primitive (anti-derivative) of 1/Φ.

Proof. First one recalls that ∫_{0}^{z} W (t) dt is the e.g.f. for numbers {w_{r−1}} if W (t) is the

e.g.f. for numbers {w_{r}} (index shift by −1 via integration). In the application below this integration will account for the inclusion of the extra root vertex if powers of t correspond to the number of vertices. The proof of the solution of the differential eq. for Y (z), i.e.,

Y (z) = ∫_{0}^{z} Φ(Y (t)) dt, is based on the recursive structure of increasing trees characterized

by the outdegree g.f. Increasing trees T_{n} of size n are composed of ordered, resp. unordered, r−forests (r ≥ 1) of such trees of size n − 1. These r trees are connected to the root of the tree T_{n} by r lines ending at the root labeled 1. The r−forest vertices are labeled

with 2, 3, …, n. These r−forests have e.g.f. Y^{r}(z), resp. \frac{1}{r!} Y^{r}(z). Therefore the sum over

all possible outdegrees r ≥ 0 of the root vertex yields 1 + ∑_{r ≥1} s_{r} Y^{r}(t) = ϕ(Y (t)), resp.

1 + ∑_{r ≥1} s_{r} \frac{Y^{r}(t)}{r!} = φ(Y (t)). Here we use the variable t instead of z. The extra root vertex

with label 1 is then accounted for by the index shift by −1, and, as explained above, this is achieved by integration, resulting in

Y (z) = ∫_{0}^{z} Φ(Y (t)) dt, hence Y (0) = 1 .  (11)

Note 5. Y^{r}(z), and also\frac{1}{r!} Y^{r}(z), are given by the multinomial theorem in terms of the partition number array called M_{3} in Abramowitz and Stegun [1, p. 831]. See also Slone’s OEIS [18, \underline{A036040}]. Within each of the r parts of the partition of n the order is taken w.l.o.g. increasing. We shall expand on this in Section 4.

Note 6. It is easy to see that the number of ordered rooted trees of size n (including the root vertex) is C_{n}, the nth Catalan number. See Slone’s OEIS [18, \underline{A000108}]. The tree number o.g.f. c satisfies c(x) = ∑_{r=0}^{∞} (x c(x))^{r} = \frac{1}{1 − x c(x)}, which is obvious from the recursive structure of these trees. The extra x−factor accounts for the root vertex. See also Conway and Guy [11, p. 99], where these trees are called plane rooted bushes. This coincides with the eq. for the o.g.f. for Catalan numbers.

Note 7. Cayley’s classical result from 1889 [20, pp. 23, 37, 66] and [4, p, 39] on the number t_{n} of unordered trees of size n with any labeling from I_{n} can be obtained in a similar manner. The outdegree e.g.f. is now φ(z) = exp(z) because s_{r} = 1 for all r ≥ 0. The e.g.f. for the numbers {t_{n}} of such trees is, by their recursive definition, Y (z) = z φ(Y (z)) = z exp(Y (z)), because the root can now have any of the labels 1, 2, …, n, and {n f_{n−1}} is exponentially generated by z f(z) if {f_{n}} is exponentially generated by f. This holds for any r-forest. Then the sum over the outdegrees r ≥ 0 of the root vertex is taken. The just found implicit equation for Y (z), can be solved via Lagrange inversion as

Y (z) = ∑_{n=1}^{∞} \frac{x^{n}}{n!} (\frac{d^{n−1}}{da^{n}} φ^{n}(a))|_{a=0} = ∑_{n=1}^{∞} t_{n} \frac{z^{n}}{n!} .  (12)

With φ(a) = exp(a) this becomes the classical result t_{n} = n^{n−1}. This is the sequence [1, 2, 9, 64, 625, …], see Sloane’s OEIS [18, \underline{A000169}].

Example 8. Ordered increasing (incomplete) k−ary trees

For such trees the outdegree e.g.f. is φ_{k}(y) = (1 + y)^{k} because there are s_{k;r} = \binom{k}{r} different types of outdegree r ≥ 1 vertices. E.g. k = 4, r = 2: s_{3;2} = 6 from chosing

two lines out of a 4−ary vertex. F_{k}(y) = ∫ dy \frac{1}{(1 + y)^{k}}, which is (up to a constant)

F_{1}(y) = ln(1 + y) and F_{k}(y) = \frac{1}{1−k} (1 + y)^{1−k}, k ≥ 0, k ≠ 1. F_{1}^{[−1]}(x) = exp(x) − 1, and F_{k}^{[−1]}(x) = −1 + ((1 − k) x)^{\frac{1}{1 − k}}. Therefore, Y_{1}(z) = exp(z) − 1, and Y_{k}(z) =

−1 + ((1 − k) (\frac{1}{1 − k} + z))^{\frac{1}{1−k}} = −1 + ( 1 + (1 − k) z)^{\frac{1}{1−k}}. for k ≥ 0, k ≠ 1. k = 1

applies for unary trees, and for k = 0 one has Y_{0}(z) = z corresponding to the trivial tree with just one vertex, the root with label 1. For binary trees Y_{2}(z) = \frac{z}{1 − z}, producing the sequence \{n!\}_{1}^{∞}, Sloane’s OEIS [18, \underline{A000142}].

Proposition 9. |S(k; n, m)|, resp. |s(k; n, m)|, with k ∈ ℤ, is the number of unordered m−forests composed of m trees with altogether n vertices (including the m roots). The number of such trees is exponentially generated by the g2 and g1 functions given in the Introduction.

Proof. This follows immediately from the Jabotinsky (a special Sheffer) structure of the lower diagonal number triangles S(k), resp. s(k). See Knuth [14] for a general discussion of Jabotinsky triangles. In other words, they are exponential convolution triangles. This means that the e.g.f. for the m−th column numbers (n ≥ m) is for k ∈ ℕ given by

g2_{m}(k; x) := ∑_{n=0 (m)} S(k; n, m) \frac{x^{n}}{n!} = \frac{1}{m!} (g2(k; x))^{m}, resp.  (13)

g1p_{m}(k; x) := ∑_{n=0 (m)} |s(k; n, m)| \frac{x^{n}}{n!} = \frac{1}{m!} (g1p(k; x))^{m} .  (14)

Similar eqs. hold with −k ∈ ℕ for g2p_{m}(k; x) and g1_{m}(k; x). The forests are unordered due to the e.g.f. Jabotinsky structure with the factor 1/m!.

Thus one only has to find a combinatorial interpretation for the m = 1 column numbers of such lower triangular Jabotinsky matrices. The column m = 0 is not relevant, it is always [1, 0, 0, …]^{⊤}.

Proposition 10. S(k; n, 1), k ≥ 0

S(k; n, 1), k ≥ 1, is the number of ordered rooted k−ary trees of size n (including the root vertex) increasingly labeled with distinct elements from I_{n} = {1, 2, …, n}. For k = 0 there is only one vertex (n = 1), the root, and S(0; n, 1) = δ_{n,1}.

Proof. From Proposition 4, the Example 8, and the e.g.f.s g2(k; x) given in (5).

Example 11. S(3; n, 1), n = 1, 2, 3, 4.

In Figure 1 the ordered ternary (3-ary) trees with sizes n = 1, 2, 3 and 4 are shown without vertex labeling. The (hidden) root label is used there to numerate the different trees.

The number of such trees of size n is [1, 3, 12, 55, …], i.e., \binom{3n}{n}/(2n+1) = \binom{3 n}{n − 1}/n. See

Sloane’s OEIS [18, \underline{A001764}]. This formula follows from the general one for k−ary trees, see Note 12 below. If now increasing trees are considered, one finds for the 12 trees with size n = 4, in the order given in Figure 1, the number of different labelings [2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1], altogether 15, and indeed S(3; 3, 1) = 15 = 5!! := 1·3·5. For the triangle S(3) see Sloane’s OEIS [18, \underline{A035342}]. For n = 4 the 55 unlabeled trees shown in Figure 1 can be labeled increasingly in [3!, 2, 1, 18 · 3, 4 · 2, 6 · 1, 2 · 2, 12 · 1, 2 · 2, 8 · 1] ways. Altogether this is 105, and indeed S(3; 4, 1) = 105 = 7!!.

Note 12. The number t_{k}(n) of ordered rooted k−ary trees of size n is obtained from the equation for the o.g.f. T_{k}(x) = ∑_{n=1}^{∞} t_{k}(n) x^{n}, viz., T_{k}(x) = 1 + x (T_{k}(x))^{k} =

\frac{1}{1 − x (T_{k}(x))^{k−1}} , via Lagrange inversion. This yields the Pfaff-Fuss-Catalan- or k−Raney

sequences [12, p. 347, (7.66)] and Sloane’s OEIS [18, \underline{A000108}, \underline{A001764}, \underline{A002293}, \underline{A002294}, \underline{A002295}, \underline{A002296}, \underline{A007556}, \underline{A062994}] for k = 2, 3, …, 9. The formula is

t_{k}(n) = \binom{k n}{n} \frac{1}{(k − 1) n + 1} = \binom{k n + 1}{n} \frac{1}{k n + 1}.

Proposition 13. Organic growth of ordered k-ary increasing trees

All rooted ordered increasing k−ary trees of size n are obtained from all such trees of size n − 1 by adding in all possible ways, respecting the k−arity, the branch with leaf labeled n to every vertex of each tree of size n − 1.

Proof. It is clear that by this growth prescription the increasing labeling is respected. It is also clear that it leads only to size n trees of the k−ary type, because the new branch can only be appended in free k−ary directions from each vertex. Given any such size n tree, an amputation of the branch with leaf labeled n will produce a tree of size n − 1 of the considered type. In fact, no different size n − 1 trees of this type can grow to the same size n tree. This shows that all such size n trees are grown.

Proposition 14. Recurrence for S(k; n, 1), k ∈ ℕ, recovered a_{n}^{(k)}, the number of size n rooted ordered k−ary increasing trees satisfies the recurrence

a_{n}^{(k)} = (k (n − 1) − (n − 2)) a_{n−1}^{(k)} , a_{1}^{(k)} = 1, n = 2, 3, 4, …  (15)

Proof. Consider any size (n − 1) tree. The number of lines E of such a tree is n − 2. Clearly, ∑_{i=1}^{n−1} r_{i} = E = n − 2 with the outdegree r_{i} of the vertex with label i. Now attach the branch with leaf labeled n to the vertex with label i . This can be done in k − r_{i} ways (using one of the free k−ary line places). Summing over all n − 1 vertices thus yields ∑_{i=1}^{n−1} (k − r_{i}) = k (n − 1) − (n − 2). Therefore, any of the a_{n−1}^{(k)} trees of size n − 1 grows to k (n−1)−(n−2) = (k−1) (n−1) + 1 different new trees of size n. This recurrence coincides with the one for S(k; n, 1), k ∈ ℕ, obtained from (3) as it should due to Proposition 10. For the solution of this recurrence see [15].

The non-negative numbers |S(−k; n, 1)| = (−1)^{n−1} S(−k; n, 1), k ∈ ℕ_{0}, also fit into the varieties of increasing trees studied by Bergeron et al. [3].

Proposition 15. |S(−k; n, 1)|, k ≥ 0 |S(−k; n, 1)|, k ∈ ℕ_{0}, is the number of ordered rooted increasing trees of size n with

outdegree o.g.f. Φ_{k}(y) = \frac{1}{(1 − y)^{k}}, i.e., s_{k;r} = \binom{r + k − 1}{k − 1} = \binom{r + k − 1}{r}. For k = 0

one has s_{0;r} = δ_{r,0}.

Proof. Proposition 4, (10) , leads to F_{k}(y) = ∫ dy (1 − y)^{k} = −\frac{1}{k + 1} (1 − y)^{k+1} with

F_{k}(0) = −1/(k +1). F_{k}^{[−1]}(x) = 1 − (−(k +1) x)^{1/(k+1)}. Y_{k}(z) = 1 − (1 − (k +1) z)^{\frac{1}{k+1}} = g2p(k; z), with the e.g.f. of the numbers {|S(−k; n, 1)|} given in (6).

The numbers s_{k;r} defined above show that for given k ≥ 1 one has to consider ordered rooted trees with (r + k − 1)−ary vertices if their outdegree is r ≥ 1. If r = 0 (for the single root vertex or the leaves) there is only one vertex type. This leads to the following corollary.

Corollary 16. |S(−k; n, 1)|, k ∈ ℕ_{0}, is the number of ordered rooted increasing trees of size n with outdegree r ≥ 0 vertices of the (r + k − 1)−ary type.

Trees of this type, with outdegree r dependent arity, will be called rooted ordered (r + k − 1)−ary increasing trees in the sequel.

Example 17. |S(−3; n, 1)|

The triangle |S(−3)| (meaning the signless triangle S(−3)) is given in Sloane’s OEIS [18, \underline{A000369}]. For the sequence |S(−3; n, 1)|, the m = 1 column of this triangle, see \underline{A008545}. From s_{3;r} = \binom{r+2}{r} one has (r + 2)−ary vertices for outdegree r. First one considers the ordered rooted trees of size n without vertex labels. For n = 1, 2, 3, 4, 5 see e.g., Conway and Guy [11, p. 99, Fig. 4.7] (called rooted plane bushes, with missing leave vertices, and depicted upside-down). Then the multiplicity for increasing labelings is determined. See our Figure 2 for n = 1, 2, 3, 4, Figure 3 for n = 5 and Figure 4 for n = 6.

Instead of using (r + k − 1)−ary vertices of outdegree r ≥ 0 which can become cumbersome to draw, it is simpler to color the r successor vertices of an outdegree r vertex from a repertoire of pairwise different colors C_{i}, i = 1, 2, …, (r + k − 1). (These colors C_{i} will not be confused with Catalan numbers.) The color indices are taken as C_{i_{1}}, C_{i_{2}}, …, C_{i_{r}}, 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ (r + k − 1) if the vertices are considered from the left to the right. The root vertex can have any color, say C_{0}. This coloring is done independently for each non-root vertex. In this way the different colors mimic the different possible leg positions for an (r + k − 1)−ary vertex. This is the content of the next corollary.

Corollary 18. Rooted ordered vertex colored increasingly labeled trees

|S(−3; n, 1)|, k ∈ ℕ_{0}, is the number of rooted ordered increasing trees of size n and the r successor vertices of a predecessor vertex with outdegree r have colors C_{i_{1}}, C_{i_{2}}, …, C_{i_{r}}, 1 ≤ i_{1} < i_{2} < … < i_{r} ≤ (r + k − 1) when read from the left to the right. The root vertex carries a color C_{0}.

Example 19. For k = 3 the tree with n = 4 vertices and outdegree r = 3 of the root vertex can have for its leaves \binom{5}{3} = 10 color configurations C_{1} C_{2} C_{3}, C_{1} C_{2} C_{4}, C_{1} C_{2} C_{5}, C_{1} C_{3} C_{4}, …, C_{3} C_{4} C_{5}. The root has color C_{0}. Each of these 10 colored trees is then labeled increasingly, producing altogether 10 · 3! = 60 such trees with r_{1} = 3. The root has, of course, label 1. Cf. Figure 2, n = 4, first row.

Also the specific trees of size n counted by |S2(−3; n, 1)|, k ∈ ℕ, can be obtained from those of size n−1 by adding a branch with a leaf labeled n. In the drawing of these trees one uses s branches of two kinds for an s−ary vertex with outdegree r ≤ s; a solid line for each of the r outgoing lines and s − r dashed lines for the remaining ones. These s lines of two types are usually drawn downwards form the vertex in a symmetric way, i.e.. the relevant angle is π/(s + 1). The first and the last line have this angle with the imagined horizontal reference axis through the vertex. Neighbouring lines also span this angle.

Proposition 20. Organic growth of ordered (r + k − 1)-ary increasing trees

All rooted ordered (r + k − 1)−ary trees of size n are obtained from all such trees of size n − 1 by adding in the following way a branch with leaf labeled n to every vertex of each tree of size n − 1. A vertex with outdegree r in the size n − 1 tree has (r − 1 + k) − r = k − 1 dashed lines. The solid line with leaf labeled n is now put at any of the new r + k places available for an (r + k)−ary vertex. The type (solid or dashed) of the remaining lines are carried over from the vertex of the tree of size n − 1 to the remaining r + k − 1 line places. In this n − 1 → n growing process the angle between the lines is diminished, of course.

Proof. It is clear that by this growth prescription the increasing labeling is respected. By construction only trees of the considered (r − 1 + k)−ary type are grown. In fact, all rooted ordered (r − 1 + k)−ary increasing trees of size n are grown this way. Just amputate the (solid) leg with label n and enlarge the angles between the remaining lines of both types, appropriate for the arity of the vertex in the size n − 1 tree. No different size n − 1 trees of the considered type can grow to the same size n tree.

Proposition 21. |S(−k; n, 1)| recurrence recovered

b_{n}^{(k)}, the number of size n rooted ordered (r − 1 + k)−ary increasing trees satisfies the recurrence

b_{n}^{(k)} = (k (n − 1) + (n − 2)) b_{n−1}^{(k)} , b_{1}^{(k)} = 1, n = 2, 3, 4, …  (16)

Proof. Consider any size (n−1) tree of the relevant type. See the proof of Proposition 14 for ∑_{i=1}^{n−1} r_{i} = n−2 with the outdegree r_{i} of the vertex with label i. The growing prescription of Proposition 20 shows that for each vertex v_{i} with label i and outdegree r ≥ 0 there are k + r possible places for the line with label n, because the new vertex v_{i} has become (k + r)−ary in the size n tree. The other (k + r − 1) lines of both types are carried over (with diminished angle between the lines) from the vertex v_{i} of the size n − 1 tree. For every vertex v_{i} there are thus (k + r) new configurations for this vertex labeled i in the size n tree. Summing over all vertices of the size n − 1 tree yields ∑_{i=1}^{n−1} (k + r_{i}) = k (n − 1) + (n − 2). Therefore, any of the b_{n−1}^{(k)} trees of size n − 1 grows to k (n − 1) + (n − 2) = (k + 1) (n − 1) − 1 different new trees of size n. The shown recurrence coincides with the one for |S(−k; n, 1)|, k ∈ ℕ, obtained from (3) as it should due to Corollary 16. For the solution of this recurrence see [15].

Note 22. Coloured increasing trees

Also the colored version of the increasing trees described in Corollary 18 can be grown by appending a new line with label n and a certain color to every vertex i with outdegree r_{i}, i.e., r_{i} colored successors. The growth prescription can be immediately read off from the corresponding (r_{i} + k − 1)−ary vertex labeled i. One just observes the pattern of dashed (unused) and solid lines from this vertex in the size n − 1 tree. It shows which colors from the repertoire {C_{1}, C_{2}, …, C_{r_{i} + k − 1}} are used (correspond to solid lines) in this order. Each such vertex labeled i with colored successors is then grown to precisely r_{i} + k new vertices with label i by appending the line with label n in all possible r_{i} + k colors available for an outdegree r_{i} + 1 vertex. The remaining r_{i} successor lines carry the labels in the same order like in the original size n − 1 tree and the colors follow the pattern of the original size n − 1 tree (corresponding to the pattern of dashed and solid lines in the (r_{i} + k − 1)−ary version), This means that in general the color of a successor vertex with a given label will be different in the original and the grown tree. An example will make this clear. Take k = 2, r_{i} = 3, n = 7. In the size n − 1 = 6 tree r_{i} + k − 1 = 4 different colors are available for the three successor vertices which have one from \binom{6}{3} = 20 possible labelings, say 3, 2, 6, in

this order. Consider the vertex coloring C_{1}, C_{2}, C_{4}. This can be encoded as 3 2 6 1 2 4 where

the upper row stands for the labels and the lower one for the color indices. The grown tree of size 7 will now have attached to this vertex i a leg with the vertex labeled 7 and e.g.,

color C_{4}. This will correspond to the new vertex i with successor vertices 3 2 7 6 1 2 4 5 .

C_{3} is missing because in the original color pattern the third color was missing and in the grown case the available colors are C_{1}, C_{2}, C_{3}, C_{5} because the label 7 vertex has color C_{4}. The third color, here C_{3}, has to be skipped, thus producing the color sequence C_{1}, C_{2}, C_{4}, C_{5}

for the successor vertices. The other four grown successor vertices are then 7 3 2 6 1 2 3 5 ,

3 7 2 6 1 2 3 5 , 3 2 7 6 1 2 3 5 and 3 2 6 7 1 2 4 5 .

3 Generalized Stirling numbers of the first kind

The generalized non-negative Stirling numbers of the first kind |s(k; n, m)| = (−1)^{n−m} s(k; n, m), k ∈ ℕ, which arise from the (infinite) matrix inversion s(k) S(k) = 1_{∞} = S(k) s(k) (considered for N × N matrices with N arbitrary large) are also of the Jabotinsky type, and therefore these numbers will also count unordered m−forests of trees of size n provided one can define them such that there are |s(k; n, 1)| such trees. From the e.g.f. of the numbers |s(k; n, 1)|, given in (7), one derives the outdegree function Φ_{k}(y) by putting

Y_{k}(z) = g1p(k; z) in Proposition 1, computing \frac{d Y_{k}(z)}{dz} = (1 − z)^{−k} and rewriting this for

k ≥ 2 as (1 + (k − 1) Y_{k}(z))^{\frac{k}{k−1}} . Therefore

Φ_{k}(y) = (1 + (k − 1) y)^{\frac{k}{k−1}} , k ≥ 2,  (17)

and from Y_{1}(z) = − ln(1 − z) one finds Φ_{1}(y) = exp(y) .

Because for every outdegree r the vertex type number s_{r} has to be a non-negative integer one needs for k = 1 the e.g.f. φ(y) = exp(y). Therefore |s(1; n, 1)| = |s(n, 1)| counts unordered (nonplane) increasing trees of size n. This provides another combinatorial meaning of these numbers besides the number of permutations of n elements which in their cycle decomposition consist of just one cycle. This number is, of course, (n − 1)!.

Example 23. The number of unordered increasing trees of size 4 with one type of vertex for all outdegrees r ≥ 0 is |s(1; 4, 1)| = 3! because there are four types of trees, viz., the ones with r_{1} = 3; r_{1} = 2; r_{1} = 1, r_{2} = 2 and r_{i} = 1, i = 1, 2, 3, which come respectively in 1, 3, 1 and 1 increasing labelings. Remember that r_{i} is the outdegree of the vertex with label i. Hence 1 + 3 + 1 + 1 = 6 = 3!.

For k = 2 one can take the outdegree o.g.f. ϕ_{2}(y) = (1 + y)^{2} or the e.g.f. φ_{2}(y) =

1 + 2 y + 2 \frac{y^{2}}{2!} . In the first case one has to consider ordered increasing (incomplete) binary trees. Such trees have already been encountered in the last section, where they were shown to be counted by S(2; n, 1), the unsigned Lah numbers, Sloane’s OEIS [18, |\underline{A008287}| ]. Therefore |s(2; n, 1)| = S(2; n, 1), which is also clear from their recurrence relations with inputs. In the outdegree e.g.f. case |s(2; n, 1)| counts unordered (nonplane) increasing trees with two types of vertices for both outdegrees 1 and 2 because s_{1} = 2 = s_{2}. We shall use two-colored vertices in both outdegree cases. No other outdegree besides r = 0, coming only in one vertex type (s_{0} = 1), is allowed. The single root vertex in the size 1 tree and the leaves (r = 0) are left uncolored (color C_{0}). This gives another interpretation of the unsigned Lah numbers. See 5 for these trees of size n = 4. Only three types of trees are relevant here. The tree with r_{1} = 3 is not allowed.

While |s(k; n, m)| for k = 1 and k = 2 counts trees of varieties considered by Bergeron et al. [3] this remains no longer true for k ≥ 3 as is obvious from the expansion of Φ_{k} from (17). In these cases the vertex multiplicities s_{k;r} for outdegree r are no longer non-negative integers. This applies to the o.g.f. ϕ as well as to the e.g.f. φ. E.g., ϕ_{3}(y) = (1 + 2 y)^{\frac{3}{2}} ,

s_{3;r} = 2^{r} \binom{\frac{3}{2}}{r}, which is \frac{3}{2} for r = 2 and −1 for r = 3. Similarly, φ_{3}(y) = (1 + 2 y)^{\frac{3}{2}} ,

s_{3;r} = 2^{r} r! \binom{\frac{3}{2}}{r} which is −3 for r = 3. This fact is summarized in the following proposition.

Proposition 24. For k ≥ 3 values |s(k; n, 1)| does not count increasing trees of some variety studied by Bergeron et al. [3], i.e., there exists no outdegree function Φ_{k} which generates nonnegative integers s_{k;r} for all r ≥ 0.

In order to find a tree counting interpretation also for these numbers |s(k; n, 1)| =: c_{n}^{k} with k ≥ 3 one can resort to the recurrence relation obtained from (4)

c_{n}^{(k)} = (k + n − 2) c_{n−1}^{(k)} , c_{1}^{(k)} = 1 , n ≥ 2 .  (18)

For the solution of these recurrences see [15]. For k = 3 this is Sloane’s OEIS [18, \underline{A001710}] = [1, 3, 12, 60, 360, …]. One can consider trees with outdegree r = 0 and r = 1 vertices only but take (d + 3)−ary vertices if the depth of the vertex (the distance from the root) is d ≥ 0. For size n = 1 there is only the root vertex with r = 0. For n = 2 the root vertex with r = 1 has depth d = 0 and is now taken 3−ary. The second vertex has r = 0, depth d = 1, but its 4−arity does not matter. This leads to three trees like for the 3−ary trees considered in the last section for k = 3 and n = 2. For size n = 3 one has the root with r = 1, d = 0 as a 3−ary vertex, the d = 1 vertex with r = 1 is now 4−ary. Again the arity of the leave with d = 2 does not matter. Thus one finds for each of the three n = 2 trees four new ones; altogether there are 12 = c_{3}^{(3)} trees. If only trees but not forests are considered the increasing labeling from I_{n} coincides for each vertex with d + 1.

Instead of employing in the k = 3 case (d + 3)−ary vertices, if their depth is d, one may again use colors for their next successor vertices. The vertex of depth d ∈ {0, 1, …, n−1} in a size n tree comes thus in d + 2 colors {C_{1}, C_{2}, …, C_{d+2}} for d ≥ 1 and if d = 0 one takes color C_{0}. It is clear that such type of trees with label depending arity and outdegree only 0 and 1 is not covered in the study [3], because for all vertices with given outdegree r the same number s_{r} of vertex types (arity) is prescribed. In the trees considered here, an outdegree 1 vertex can have depth depending vertex type numbers s_{3;1,d}. Therefore one would need a two variable degree-depth polynomial to treat such trees.

The generalization to any k ≥ 3 is obvious and is the content of the next proposition where instead of different arities, colors are used. It is also possible to apply this for the cases k = 1 and k = 2.

Proposition 25. Vertex colored trees counted by |s(k; n, 1)| , k ≥ 1

|s(k; n, 1)| , k ≥ 1, is the number of rooted size n trees with vertices of outdegree r = 0 and 1 only, increasingly labeled from I_{n} and colors chosen from the color repertoire

{C_{1}, C_{2}, …, C_{d+k−1}}

if the vertex has depth d ∈ {0, 1, …, n − 1}. The root vertex with label 1 and depth 0 carries color C_{0}.

For k = 1 the usual Stirling numbers |s(n, 1)| = (n−1)! arise here from the independent color choices of the depth d vertices. For k = 2 one has d + 1 colors to choose from for vertices of depth d ∈ {1, 2, …, n − 1} which produces 2 · 3 ⋯ n = n! possibilities. This is appropriate for the unsigned Lah numbers |s(2; n, 1)|.

Note 26. |s(k; n, 1)| as an answer to an urn problem

It is clear from Proposition 25 that |s(k; n, 1)|, k ∈ ℕ, counts the number of ways to put one colored ball into each of n distinguished urns U_{1}, U_{2}, …, U_{n} with the color repertoire {C_{1}, C_{2}, …, C_{i+k−2}} for urn U_{i}, i ∈ {2, 3, …, n}, and {C_{0}} for urn U_{1}.

As mentioned above, in the context of the Jabotinsky structure, |s(k; n, m)| counts unordered m−forests of size n with the m increasingly vertex labeled and also vertex colored trees following the rules of Proposition 25.

Example 27. |s(3; 5, 2)| = 660 from forest counting

The unordered 2−forest with n = 5 vertices comes from the m = 2 part partitions (1, 4) and (2, 3) of 5. The first one gives rise to (1 · |s(3; 4, 1)|) · 5 = (1 · (1 · 3 · 4 · 5)) · 5 = 300 such forests where the last factor 5 comes from the number of increasing labelings. The second partition leads to (|s(3; 2, 1| · |s(3; 3, 1|) · \binom{5}{2} = ((1 · 3) (1 · 3 · 4)) 10 = 360 forests. The last factor comes again from the increasing labelings. Thus |s(3; 5, 2)| = 660. See Sloane’s OEIS [18, \underline{A046089}(2, 5) = 660] and the illustration in Figure 6a). In Figure 6b) the forests counted by |s(4; 5, 3)| = \underline{A049352}(5, 3) = 440 are shown.

Note 28. The definition of these rooted increasingly labeled trees with outdegree 0 and 1 only and the mentioned vertex coloring is somewhat artificial, as the equivalent urn problem counting shows. One can, in fact, also give such an interpretation to the S(k; n, m) and |S(−k; n, m)| numbers for k ∈ ℕ. The prefactor in the corresponding recurrences, (15) and (16), are positive integers which will give the number of colors for the vertices of depth d = n − 1.

Finally the non-negative numbers s(−k; n, 1), k ∈ ℕ, with e.g.f. Y_{k}(z) = g1(−k; z) given

in (8) are considered. From \frac{d Y_{k}(z)}{dz} = (1 + x)^{k}, rewritten as (1 + (1 + k) Y_{k}(z))^{\frac{k}{k+1}} , one finds the would be outdegree function

Φ_{k}(y) = (1 + (1 + k) y)^{\frac{k}{k+1}} , k ∈ ℕ .  (19)

The case k = 0 with s(0; n, 1) = δ_{n,1} and g1(0; z) = 1 is also covered. It is clear from the binomial expansion that for k ∈ ℕ neither the o.g.f. ϕ_{k} nor the e.g.f. φ_{k} will generate non-negative integers s_{k;r}. This is the content of the next proposition.

Proposition 29. s(−k; n, 1), k ∈ ℕ

s(−k; n, 1) does for k ∈ ℕ not count rooted increasing trees of some variety studied Bergeron et al. [3], i.e., there exists no outdegree function Φ_{k} which generates non-negative integers s_{k;r} for all r ≥ 0.

The recurrence relation for s(−k; n, 1) =: d_{n}^{(k)}, k ≥ 0, is

d_{n}^{(k)} = (k − (n − 2)) d_{n−1}^{(k)} , d_{1}^{(k)} = 1 , n ≥ 2.  (20)

For given k ∈ ℕ one has d_{n}^{(k)} = 0 for all n ≥ k + 2.Therefore one only has to interpret the positive numbers d_{1}^{(k)}, …, d_{k+1}^{(k)}, with d_{j}^{(k)} = k\underline{j−1} (falling factorials). If one considers, like above, trees with only vertex outdegrees 0 or 1 and depth dependent vertex coloring one is lead to the following proposition.

Proposition 30. s(−k; n, 1), k ∈ ℕ_{0}

s(−k; n, 1) counts for k ∈ ℕ_{0} rooted increasing trees of sizes n ∈ {1, 2, …, k + 1} with outdegree r ∈ {0, 1} and vertex coloring from the repertoire {C_{1}, C_{2}, …, C_{k+1−d}} if the depth is d ∈ {0, 1, …, n − 1}. The vertex with d = 0, the root labeled 1, carries a fixed color, say C_{0}.

Example 31. s(−5; n, 1) colored trees with outdegree 0 or 1

Only unary trees (no branching) of sizes n = 1, 2, …, 6 are present. For n = 1 one has the root vertex labeled 1 with color C_{0}. All other 5 trees have k = 5 colors C_{1}, …, C_{5} for the vertex of depth 1 (labeled 2). Then the number of available colors decreases by one with each depth increase by one. In the sixth tree, having size 6, the leave (d = 5) has the color C_{1}. The counting is therefore 1, 1·5 = 5, 1·5·4 = 20, 1·5·4·3 = 60, 1·5·4·3·2 = 120, 1·5! = 120, in agreement with the sequence s(−5; n, 1) = \underline{A008279}(5, n − 1) = [1, 5, 20, 60, 120, 120, ¯0], where ¯0 stands for the periodic sequence with 0 entries only.

The numbers s(−k; n, m), k ∈ ℕ_{0}, count then unordered m−forests composed of trees described in Proposition 30.

4 Generalized partition number arrays

It is well know, see e.g., Charalambides [9, p. 292, eq.(8.25)], that the ordinary Stirling numbers S(n, m) appear as sum over the multinomial numbers M3 with fixed number of parts m of the underlying partitions of n. See Sloane’s OEIS [18, \underline{A036040}], also Abramowitz and Stegun [1, p. 831–2 ] for the array M3.

S(n, m) = ∑_{a⃗∈P(n,m)} M3(n, a⃗) ,  (21)

with P(n, m) the set of partitions of n with m parts written in the exponent version (1^{a_{1}} , 2^{a_{2}} , …, n^{a_{n}}), a_{j} ∈ ℕ_{0}, j = 1, …, n, a⃗ := (a_{1}, a_{2}, …, a_{n}), m = ∑_{j=1}^{n} a_{j}, n = ∑_{j=1}^{n} j a_{j} and

M3(n, a⃗) = \frac{n!}{∏_{j=1}^{n} a_{j}! j!^{a_{j}}} .  (22)

It is therefore tempting to define generalized M32(k), k ∈ ℕ, partition number arrays such that

S(k; n, m) = ∑_{a⃗∈P(n,m)} M32(k; n, a⃗) , k ∈ ℕ .  (23)

We write M32(k) to indicate the M3 generalization related to the S(k; n, m) numbers of the second kind. The term ‘partition numbers’ is used because every partition defines such a number, not because they count the number of some specific partitions. Remember that S(1; n, m) = S(n, m) and S(0; n, m) = δ_{n,m}. This generalization is an easy task knowing the combinatorial interpretation of S(k; n, m) in terms of rooted increasing k−ary trees from Proposition 10. The partition (1^{a_{1}} , 2^{a_{2}} , …, n^{a_{n}}) corresponds to the m−forest built from a_{1} trees of size 1, a_{2} trees of size 2, etc. These trees of size j ∈ I_{n} are counted by S(k; j, 1).

Definition 32. a⃗−forest

For n ∈ ℕ let a⃗ := (a_{1}, a_{2}, …, a_{n}) with a_{j} ∈ ℕ_{0}, m := ∑_{j=1}^{n} a_{j} and n = ∑_{j=1}^{n} j a_{j}. An a⃗−forest of size n is an m−forest of size n with specified component trees T_{1}^{a_{1}}, T_{2}^{a_{2}}, …, T_{n}^{a_{n}} where the exponents a_{j} from ℕ_{0} indicate that a tree T_{j} of size j is present a_{j} times if a_{j} ≥ 1, and such a tree is absent if a_{j} = 0.

Definition 33. M32(k), k ∈ ℕ, partition number arrays

M32(k; n, a⃗), k ∈ ℕ, is the number of unordered a⃗−forests of size n with component trees T_{j}, j ∈ I_{n}, described in Proposition 3 and counted by S(k; j, 1).

With this definition and from Proposition 9 it is clear that (23) holds.

Example 34. M32(2) partition number array

This array can be viewed online in Sloane’s OEIS [18, \underline{A130561}]. It begins like 1; 2|1; 6|6|1; 24|24, 12|12|1; 120|120, 120|60|60|20|1; … where semi-colons separate different n values and | separates different part numbers m. For example, n = 5, m = 4 has only one partition (1^{3}, 2^{1}, 3^{0}, 4^{0}, 5^{0}) ≡ (1^{3}, 2), and the counting is 10 · 2 = 20 for this unordered (3, 1, 0, 0, 0)-forest because there are \binom{5}{3} = 10 increasing vertex labelings and the size 2 tree comes for k = 2 in two versions. Thus M32(2; 5, (3, 1, 0, 0, 0)) = 20. This appears in array \underline{A130561} in row 5, column 6 because the partitions are ordered by increasing parts number m and within equal parts numbers the ordering is like Abramowitz-Stegun [1, pp. 831–2]. Therefore we call this the A-St ordering of partitions.

Proposition 35. M32(k), k ∈ ℕ, formula

M32(k; n, a⃗) = M3(n, a⃗) ∏_{j=1}^{n} (S(k; j, 1))^{a_{j}} , k ∈ ℕ.  (24)

Proof. M3(n; a⃗) of (22) counts the number of ways to partition a set of n objects, taken as I_{n}, into blocks of type (1^{a_{1}} , 2^{a_{2}} , …, n^{a_{n}}), i.e., a block of size j appears a_{j} times and is absent if a_{j} = 0. The order of the block elements is irrelevant, so w.l.o.g. they are taken increasing. The blocks are therefore disjoint and exhaustive subsets of I_{n}. Also the a_{j} blocks of size j are not ordered. E.g., n = 5, a⃗ = (1, 2, 0, 0, 0) and there are three (not six) set partitions for each j ∈ I_{5} taken as element of the size 1 set. Altogether there are 15 such set partitions. Therefore M3(n, a⃗) is exactly the number of unordered a⃗−forests of size n with increasing trees, depending on the partition a⃗ ∈ P(n, m). What is left is to multiply each increasing a⃗−forest with the number of possible k−ary trees. This number is S(k; j, 1) for every tree of size j and it therefore comes a_{j} times. This explains the second part on the r.h.s. of the proposition. In the given example the extra factor is 1 · 3^{2} for k = 3 from the j = 1 tree (a root) and the two size j = 2 ternary trees.

Note 36. The first rows of number arrays M32(k) are shown under Sloane’s OEIS [18, \underline{A036040}, \underline{A130561}, \underline{A134144}, \underline{A134149}, \underline{A134273}, \underline{A134278}] for k = 1, 2, …, 6, respectively, where they are called M_{3}(k).

Definition 37. { \atop M32}(k) ≡ ′M32(k)/M3′ partition number array

{ \atop M32}(k; n, a⃗) := ∏_{j=1}^{n} (S(k; j, 1))^{a_{j}} , k ∈ ℕ.  (25)

Some of these arrays are shown under Sloane’s OEIS [18, \underline{A134286}, \underline{A134133}, \underline{A134145}, \underline{A134150}, \underline{A134274}, \underline{A134279} ] for k = 1, 2, …, 6, respectively, where they are called symbolically M_{3}(k)/M_{3}. Division of arrays of the same shape here means division of corresponding entries.

Definition 38. Ŝ(k) triangle of numbers

Ŝ(k; n, m) := ∑_{a⃗∈P(n,m)} { \atop M32}(k; n, a⃗) , k ∈ ℕ.  (26)

Ŝ(k; n, m) = 0 if n < m (lower triangular matrix). One may add colum m = 0 and row n = 0 putting Ŝ(k; n, 0) = δ_{n,0}. Some of these triangles are shown under Sloane’s OEIS [18, \underline{A023531} (unit matrix), \underline{A134134}, \underline{A134146}, \underline{A134151}, \underline{A134275}, \underline{A134280}], for k = 1, 2, …, 6, respectively, where they are called S2(k)′.

It is clear that one can also define partition number arrays M32(−k), k ∈ ℕ, related to the unordered a⃗−forests composed of rooted increasing trees T_{j}, j ∈ ℕ, defined in Proposition 15 and counted by |S(−k; j, 1)|. The definition is analogous to Definition 33. This will lead to

|S(−k; n, m)| = ∑_{a⃗∈P(n,m)} M32(−k; n, a⃗) , k ∈ ℕ ,  (27)

and the formula for M32(−k; n, a⃗) = M3(n, a⃗) { \atop M32}(−k; n, a⃗) with

{ \atop M32}(−k; n, a⃗) = ∏_{j=1}^{n} (|S(−k; j, 1)|)^{a_{j}} , k ∈ ℕ.  (28)

Some of these M32(−k) arrays are shown in Sloane’s OEIS [18, \underline{A143171}, \underline{A143172}, \underline{A143173}, \underline{A144267}, \underline{A144268} ], for k = 1, 2, …, 5. Some of the { \atop M32}(−k) arrays are shown there under \underline{A144269}, \underline{A144274}, \underline{A144279}, \underline{A144284}, \underline{A144341}, for k = 1, 2, …, 5. The corresponding triangle of numbers Ŝ(−k), defined analogous to Definition 38, are shown there under \underline{A144270}, \underline{A144275}, \underline{A144280}, \underline{A144285}, \underline{A144342}, for k = 1, 2, …, 5.

It is also well known, see e.g., Charalambides [9, p. 292, eq.(8.24) ], that the unsigned (also called absolute) Stirling numbers of the first kind |s(n, m)| satisfy

|s(n, m)| = ∑_{a⃗∈P(n,m)} M3(n, a⃗) ∏_{j=1}^{n} ((j − 1)!)^{a_{j}} .  (29)

The a⃗−forest discussion in the proof of Proposition 35 explains this because |s(n, m)| = (j − 1)! counts the trees of these forests. See the k = 1 remark following Proposition 25. The straightforward generalization is then given by the following definition.

Definition 39. M31(k) partition number array

M31(k; n, a⃗), k ∈ ℕ, is the number of unordered a⃗−forests of size n with component trees T_{j}, j ∈ I_{n}, described in Proposition 25 and counted by |s(k; j, 1)|.

Similarly one has Proposition 40. M31(k), k ∈ ℕ, formula

M31(k; n, a⃗) = M3(n, a⃗) ∏_{j=1}^{n} (|s(k; j, 1)|)^{a_{j}} , k ∈ ℕ,  (30)

with |s(k; n, 1)| = (n + k − 2)!/(k − 1)!, k ∈ ℕ^{2}.

Some of these arrays are shown in Sloane’s OEIS [18, \underline{A036039}, \underline{A130561}, \underline{A144353}, \underline{A144354}, \underline{A144355}, \underline{A144356}] for k = 1, .., 6, respectively.

Proposition 41. M31(−k), k ∈ ℕ, formula

M31(−k; n, a⃗) = M3(n, a⃗) ∏_{j=1}^{n} (s(−k; j, 1))^{a_{j}} , k ∈ ℕ,  (31)

with s(−k; n, 1) = k\underline{n−1}, k ∈ ℕ.

The first of these triangles are shown in Sloane’s OEIS [18, \underline{A144357}, \underline{A144358}, \underline{A144877}, \underline{A144878}, \underline{A144879}] for k = 1, 2, …, 5.

The corresponding partition arrays which are obtained by factoring out the M3 array are then { \atop M31}(k) and { \atop M31}(−k), for k ∈ ℕ. From these partition arrays one obtains triangles by summing over like part numbers in each row. These triangles are called ŝ(k) for k ∈ ℤ, ŝ(0) is the infinite unit matrix 1_{∞}. We list the A−numbers in Sloane’s OEIS [18] for the first of these arrays and triangles:

{ \atop M31}(k), k = 1, 2, …, 6: \underline{A107106}, \underline{A134133}, \underline{A144880}, \underline{A144885}, \underline{A144890}, \underline{A145356}.

ŝ(k), k = 1, 2, …, 6: \underline{A144351}, \underline{A134134}, \underline{A144881}, \underline{A144886}, \underline{A144891}, \underline{A145357}.

{ \atop M31}(−k), k = 1, 2, …, 5: \underline{A145361}, \underline{A145363}, \underline{A145366}, \underline{A145369}, \underline{A145372}.

ŝ(−k), k = 1, 2, …, 5: \underline{A145362}, \underline{A145364}, \underline{A145367}, \underline{A145370}, \underline{A145373}.

Note 42. Generalizations of S(k), k ∈ ℕ

Blasiak et al. [5], [6] have generalized S(k; n, m) to S(k, l; n, m) with l ∈ ℕ by considering also powers d_{x}^{l} in eq. 1 with special emphasis on the row sums, the Bell numbers B_{k,l}(n)^{3}. Blasiak et al. [7] noticed via Sloane’s OEIS that the Bell numbers B_{r,1}(n) enumerate r−ary forests. Méndez et al. [16] gave a combinatorial approach to further generalized Stirling numbers of the second kind (see Schork [17]), called S_{r,s}(k) with r and s standing for n−tuples of positive integers and k taking certain values^{4}. This approach, specialized to the S(r; n, m) numbers for r ∈ ℕ, differs from the interpretation given in this paper^{5}.

2There is a typo in Lang [15], (45) upper alternative: it should read \binom{k−2+n}{k−2} (k − 1)^{n−2} for k = 2, 3, … and n ∈ ℕ.

3The labels in these references are r, s instead of k, l.

4S_{r,s}(k) ≡ S_{r,s}(n, k) appears in the normal ordering of the ordered product ∏ ← _{i=1}^{n} x^{r_{i}} (d_{x})^{s_{i}} and k = s_{1}, …, ∑_{i=1}^{n} s_{i}.

5E.g., the Lah number S(2; 3, 2) is according to the approach of [16] 4 + 2 = 6, using n = 3, r_{i} = 2, s_{i} = 1, i = 1, 2, 3, but in the interpretation as unordered 2−forest of binary increasing trees with 4 leaves it is 3 · 2 = 6.

5 Acknowledgements

The author would like to thank Simon Plätzer for pointing out the program Graphviz.

Figure 1: Ternary (3-ary) ordered trees with n = 1, 2, 3 and 4 vertices. There are 1, 3, 12, 55 such trees for n = 1, 2, 3, 4, respectively. See [18], \underline{A001764}. The trees of all figures have been produced with the help of Graphviz.

Figure 2: Rooted ordered trees with n = 1, 2, 3, 4 vertices. There are 1, 1, 2, 5, (Calalan numbers) such trees without vertex labels. The trees are arranged according to the 1, 1, 2, 4 types of unordered rooted trees for n = 1, 2, 3, 4, respectively. The number of increasing labelings is the same for every tree in given row. It . The outdegree values r appearing in a tree with the corresponding k + r − 1-ary vertices, here with k = 3, are given. The box gives the multiplicity. The first factor is the number of diagrams in the row. The second factor comes from the various vertex types (due to the arity) and the last factor gives the number of increasing labelings. The multiplicities for n = 1, 2, 3, 4 add up to 1, 3, 21, 231, respectively, corresponding to the |S(−3, n, 1)| = \underline{A008545}(n − 1) numbers.

Figure 3: Rooted ordered trees with n = 5 vertices. There are C_{4} = 14 such trees without vertex labels. The trees are arranged according to the 9 types of unordered rooted trees. The number of increasing labelings is the same for every tree in a given row. The outdegree values r appearing in the tree with the corresponding k + r − 1-ary vertices, here with k = 3, are given. The box gives the multiplicity. The first factor is the number of diagrams in the row. The second factor comes from the various vertex types (due to the arity) and the last factor gives the number of increasing labelings. The multiplicities add up to 3465 = |S(−3, 5, 1)| = \underline{A008545}(4).

Figure 4: Rooted ordered trees with n = 6 vertices. There are C_{5} = 42 such trees without vertex labels. The trees are arranged according to the 20 types of unordered rooted trees. The number of increasing labelings is the same for each tree in any row. It is given in the upper box on the right of each row. These numbers add up to 945 = 9!!. The number in the lower box in each row is the multiplicity for each tree when outdegree r ≥ 1 vertices are taken (r + 2)-ary. This applies for the case k = 3. The total sum (upperbox · lower box numbers) is 65835 = |S(−3; 6, 1)|. The 20 unordered rooted trees come in altogether 426 increasing labelings.

22 Figure 5: Rooted unordered trees of size n = 4 with vertex types s_{0} = 1, s_{1} = 2 = s_{2}. In the first row the three types of size n = 4 trees which are present are shown together with their multiplicities when coloring (first factor) and increasing labeling (second factor) are considered. These trees are shown in the subsequent rows.

Figure 6: Nonordered forest counting for |s(k; n, m)| In Figure 6a) the 2−forests counted by |s(3; 5, 2)| = 300 + 360 = 660 are illustrated. The vertex colors are here called C0, C1, …, C5. The number of possible increasing labelings is given by the last factors 5 and 10. In Figure 6b) the 3−forests counted by |s(4; 5, 3)| = 200 + 240 = 440 are illustrated. The possible colors are indicated, giving rise to the first factor and the increasing labelings account for the second one.

References

[1] M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, reprinted as Dover publication, New York, 1972.

[2] D. S. Alexander, A History of Complex Dynamics: from Schröder to Fatou and Julia, Vieweg, Braunschweig, 1994.

[3] F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, in J.-C. Raoult, ed., Springer, 1992, CAAP ’92, Lecture Notes in Computer Science, vol. 581, pp. 24–48.

[4] N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory: 1736–1936, Clarendon Pr., 1986, Oxford.

[5] P. Blasiak, K. A. Penson and A. I. Solomon, The Boson normal ordering problem and generalized Bell numbers, Ann. Comb. 7 (2003) 127–139.

[6] P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, Phys. Lett. A 309 (2003), 198–205.

[7] P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. H. E. Duchamp, Some useful combinatorial formulae for bosonic operators, J. Math. Phys. 46 (2005) 052110 and arXiv:quant-ph/0405103.

[8] L. Carlitz, On arrays of numbers, Amer. J. Math. 54 (1932) 739–752.

[9] Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, 2002.

[10] L. Comtet, Une formule explicite pour les puissances successives de l’opirateur de dérivation de Lie, Comptes Rendus Acad. Sc. Paris, 276 A (1973) 165–168.

[11] J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus, (Springer) New York, 1996.

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

[13] J. A. Grunert, Ueber die Summirung der Reihen von der Form A φ(0), A_{1} φ(1) x, A_{2} φ(2) x^{2}, … A_{n} φ(n) x^{n}, …, wo A eine beliebige constante Größe, A_{n} eine beliebige und φ(n) eine ganze rationale algebraische Function der positiven ganzen Zahl n bezeichnet, J. Reine Angew. Math. 25 (1843), 240–279.

[14] Knuth, D. E., Convolution polynomials, Mathematica J., 2 (1992), 67–78.

[15] W. Lang, On generalizations of the Stirling number triangles, J. Integer Sequences, 3 (2000) Article 00.2.4 [16] M. A. Méndez, P. Blasiak and K. A. Penson, Combinatorial approach to generalized

Bell and Stirling numbers and boson normal ordering problem, arXiv:quant-ph/0505180, 24 May 2005.

[17] M. Schork, On the combinatorics of normal ordering boson operators and deformations of it, J. Phys. A: Math. Gen., 36 (2003) 4651–4665.

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2008.

[19] R. P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 1997.

[20] R. P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge University Press, 1999.

2000 Mathematics Subject Classification: Primary 05A15, Secondary 05A17, 05C05. Keywords: Increasing trees, enumeration, partition number arrays.

(Concerned with sequences \underline{A000108}, \underline{A000142}, \underline{A000169}, \underline{A000369}, \underline{A001710}, \underline{A001764}, \underline{A002293}, \underline{A002294}, \underline{A002295}, \underline{A002296}, \underline{A007556}, \underline{A008287}, \underline{A008297}, \underline{A008545}, \underline{A023531}, \underline{A035342}, \underline{A036039}, \underline{A036040}, \underline{A046089}, \underline{A049352}, \underline{A062994}, \underline{A107106}, \underline{A130561}, \underline{A134133}, \underline{A134134}, \underline{A134144}, \underline{A134145}, \underline{A134146}, \underline{A134149}, \underline{A134150}, \underline{A134151}, \underline{A134273}, \underline{A134274}, \underline{A134275}, \underline{A134278}, \underline{A134279}, \underline{A134280}, \underline{A134286}, \underline{A143171}, \underline{A143172}, \underline{A143173}, \underline{A144267}, \underline{A144268}, \underline{A144269}, \underline{A144270}, \underline{A144274}, \underline{A144275}, \underline{A144279}, \underline{A144280}, \underline{A144284}, \underline{A144285}, \underline{A144341}, \underline{A144342}, \underline{A144351}, \underline{A144353}, \underline{A144354}, \underline{A144355}, \underline{A144356}, \underline{A144357}, \underline{A144358}, \underline{A144877}, \underline{A144878}, \underline{A144879}, \underline{A144880}, \underline{A144881}, \underline{A144885}, \underline{A144886}, \underline{A144890}, \underline{A144891}, \underline{A145356}, \underline{A145357}, \underline{A145361}, \underline{A145362}, \underline{A145363}, \underline{A145364}, \underline{A145366}, \underline{A145367}, \underline{A145369}, \underline{A145370}, \underline{A145372} and \underline{A145373}. )

Received October 16 2008; revised version received March 6 2009. Published in Journal of Integer Sequences, March 14 2009.

Return to Journal of Integer Sequences home page.