Generating Functions for Extended Stirling Numbers of the First Kind

Martin Griffiths Department of Mathematics Christ’s College Christchurch 8013 New Zealand

                 mgriffiths@christscollege.com

Abstract

In this paper we extend the definition of Stirling numbers of the first kind by way of a special multiset. This results in a family of number triangles for which we show how to obtain ordinary generating functions for the rows and exponential generating functions for the columns. The latter are derived via a recursive process. We also indicate how to obtain formulas, in terms of factorials, generalized harmonic numbers, and polynomials, for the entries in the columns of these number triangles.

1 Introduction

Stirling numbers of the first kind may most easily be visualized by way of a scenario involving n people sitting at k circular tables, subject to the condition that each table is occupied by at least one person. Assuming the tables to be indistinguishable from one another, we enumerate all possible arrangements of n people at these tables, where, rather than being concerned with the actual seat an individual sits on, we are interested merely in who is sitting with whom on a particular table, and in who is sitting next to who (distinguishing between left and right). The number of such arrangements is given by the Stirling number of the first kind s(n, k). More formally, we have the following:

Definition 1. The Stirling number of the first kind s(n, k) is defined to be the number of permutations of n distinct elements comprising exactly k disjoint cycles. We set s(0, 0) = 1.

From this definition it may be seen that s(n, k) = 0 when k > n and, other than the case k = 0, when n ≤ 0. The Stirling numbers of the first kind thus form a triangle, as illustrated in Table 1 of Section 7. This also appears as sequence \underline{A130534} in the On-line Encyclopedia of Integer Sequences [13]. Note, incidentally, that in the literature there are signed and unsigned versions of these numbers [5, 11]. However, given Definition 1, we will use s(n, k) and subsequent generalizations to denote the unsigned versions of these numbers throughout this paper.

To take an example, we list below, using cycle-structure notation, all the permutations of the elements in {1, 2, 3, 4} having exactly two disjoint cycles:

(1)(234), (1)(243),
(2)(134), (2)(143),
(3)(124), (3)(142),
(4)(123), (4)(132),
(12)(34), (13)(24),
(14)(23).

From this we see that s(4, 2) = 11.

The permutations of the elements in {1, 2, 3, 4} having exactly three disjoint cycles is given by

(1)(2)(34), (1)(3)(24),
(1)(4)(23), (2)(3)(14),
(2)(4)(13), (3)(4)(12),

which tells us that s(4, 3) = 6. There are several well-known results concerning these numbers [4, 6, 7, 11].

Beck [2] introduced the so-called near-Bell numbers. The nth near-Bell number enumerates all possible partitions of the particular multiset {1, 1, 2, 3, …, n − 1}. Multisets may be thought of as generalizations of sets in the sense that it is permissible to have repeated elements in a multiset whereas this is not the case for sets. The number of times a particular element x appears in a multiset M is termed the multiplicity of x in M. Thus, {1, 1, 2, 3, …, n−1} may also be described as an n-multiset with multiplicities 1, 1, 1, …, 1, 2. By extending Beck’s multiset to {1, 1, …, 1, 2, 3, …, n − r + 1}, in which the element 1 has multiplicity r, we obtained results concerning generalizations of Bell numbers and Stirling numbers of the second kind [8, 9].

For example, we defined B_{n,r} [8] to be the total number of partitions of the multiset {1, 1, …, 1, 2, 3, …, n − r + 1}, and subsequently derived the recurrence relation

B_{n,r} = ∑_{k=0}^{n−r−1} \binom{n − r − 1}{k}B_{n−k−1,r} + B_{n−1,r−1}

for n ≥ r + 1. Then, employing exponential generating functions, we obtained Dobiński-like formulas such as

B_{n+3,3} = \frac{1}{6e} ∑_{m=0}^{∞} \frac{(m + 3)^{n} + 6(m + 2)^{n} + 9(m + 1)^{n} + 2m^{n}}{m!} .

Generating function techniques were also used to obtain formulas for generalized Stirling numbers of the second kind S_{r}(n, k) [9], where S_{r}(n, k) is defined to be the number of partitions of {1, 1, …, 1, 2, 3, …, n−r+1} into k non-empty parts. By way of some examples, we showed that

S_{2}(n, 4) = \frac{1}{3} (5 · 4^{n−3} − 3^{n−1} + 3 · 2^{n−2} − 2)

and

S_{3}(n, 4) = \frac{1}{3} (10 · 4^{n−4} − 5 · 3^{n−3} + 9 · 2^{n−4} − 1) .

The purpose of the current paper is to complete this work by considering the corresponding situation for the Stirling numbers of the first kind. When carrying out the enumeration of s(4, 2) and s(4, 3) above, it was tacitly assumed that the n individuals were distinguishable from one another. Here we study a scenario in which this is not necessarily the case. Indeed, we now obtain results for the situation in which r of the n are indistinguishable from one another. In other words, the party of n people now contains a group of identical r-tuplets.

This extension to the Stirling numbers of the first kind results in a family of number triangles. We show how to obtain ordinary generating functions for the rows and exponential generating functions for the columns, the latter of which are derived via a recursive process. We also indicate how to obtain formulas, in terms of factorials, generalized harmonic numbers, and polynomials, for the entries in the columns of these number triangles.

2 Initial definitions and results

For the sake of convenience we restate here a number of definitions given in a related paper on extended Stirling numbers of the second kind [9]. The formal definition of a multiset is as follows [1]:

Definition 2. A multiset is a pair (A, m) where A is some set and m is a function m : A ↦ ℕ. The set A is called the set of underlying elements. For each a ∈ A the multiplicity of a is given by m(a). A multiset is called an n-multiset if ∑_{a∈A} m(a) = n for some n ∈ ℕ.

As alluded to in the Section 1, one of way of representing an n-multiset is as a set with (potentially) repeated elements. To take an example,

{1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6}

is a 14-multiset with elements 1, 2, 3, 4, 5 and 6 having multiplicities 2, 5, 1, 3, 1, and 2, respectively.

We consider here the following family of multisets:

Definition 3. Let M(n, r) denote, for 0 ≤ r ≤ n, the n-multiset

{1, 1, …, 1, 2, 3, …, n − r + 1},

where the element 1 appears with multiplicity r and the remaining n − r elements each appear with multiplicity 1.

There are two points worth highlighting here. First, since M(n, 1) and M(n, 0) both contain precisely n distinguishable elements, it is the case that s_{0}(n, k) = s_{1}(n, k). Second, the multiset M(n, n) consists simply of n copies of the element 1.

The family of multisets given by Definition 3 leads to a particular extension of the Stirling numbers of the first kind, which is defined as follows:

Definition 4. Let n, k and r be non-negative integers. Then s_{r}(n, k) is defined to be the number of ways in which the elements from M(n, r) can be arranged into exactly k disjoint cycles. Note that s_{r}(n, k) = 0 when n < k or n < r.

For example, on using cycle-structure notation once more, the arrangements of the elements from M(4, 2) = {1, 1, 2, 3} into exactly two disjoint cycles are given by

(1)(123), (1)(132),
(2)(113), (3)(112),
(11)(23), (12)(13),

while the arrangements of the elements from M(4, 2) having exactly three disjoint cycles are as follows:

(1)(1)(23), (1)(2)(13),
(1)(3)(12), (2)(3)(11).

From the above we see that s_{2}(4, 2) = 6 and s_{2}(4, 3) = 4. The corresponding entries in the number triangle for s_{2}(n, k) may be seen in Table 2 of Section 7.

Definition 5. Let T_{r} denote the infinite number triangle with entries s_{r}(n, k) for some fixed r ≥ 0.

Note that each of the entries in the first r − 1 rows of T_{r} is equal to 0. This gives the triangles a truncated appearance when r ≥ 2, as may be seen in Section 7. These number triangles do not appear in OEIS [13] for r ≥ 2.

It follows from Definitions 3 and 4 that s_{r}(r, k) enumerates the ways of expressing r ∈ ℕ as a sum of k positive integers (disregarding the order in which these integers are written). We shall use p(r, k) to denote this, which is sometimes known as a restricted partition function. The number triangle for p(r, k) appears as sequence \underline{A008284} in the OEIS [13].

The generating function for the number of partitions of r into at most m parts [10] is given by

F_{m}(x) = \frac{1}{(1 − x) (1 − x^{2}) ⋯ (1 − x^{m})}.

The generating function for p(r, k) is thus given by

F_{k}(x) − F_{k−1}(x) = \frac{x^{k}}{(1 − x) (1 − x^{2}) ⋯ (1 − x^{k})},

and s_{r}(r, k) is equal to the coefficient of x^{r} in the series expansion of this expression. Note also that p(0, k) = 0 for k ∈ ℕ and p(0, 0) = 1 by definition. We show in Theorems 10, 13, and 15 how the remaining entries in T_{r} may be calculated.

Definition 6. Let q_{i} denote the multiset {1, 1, …, 1} containing exactly i 1s.

Definition 7. Let C_{i} be the cycle (11 ⋯ 1) comprising exactly i 1s.

3 Row generating functions

We take two different approaches in this paper to the evaluation of the entries in T_{r}. In the current section we carry this out by obtaining the ordinary generating functions for the rows of T_{r}.

Definition 8. The ordinary generating function G_{n,r}(x) for the nth row of T_{r} is given by

G_{n,r}(x) = ∑_{k=1}^{n} s_{r}(n, k)x^{k}.

Definition 9. The Pochhammer symbol (x)_{n}, also known as the rising factorial, is defined by

(x)_{n} = x(x + 1)(x + 2) ⋯ (x + n − 1).

We note here the well-known result [11]

(x)_{n} = ∑_{k=0}^{n} s_{1}(n, k)x^{k}.

Theorem 10. We have

G_{n,r}(x) = (x)_{n−r} ∑_{i=0}^{r} x^{r−i} ∑_{j=0}^{i} \binom{n − r + j − 1}{j}p(r − j, r − i).  (1)

Proof. Suppose that we wish to evaluate s_{r}(n, k) for some n, k, r ∈ ℕ such that n ≥ k and n ≥ r. Here is one way in which this may be done. First, let j ≥ 0 and m ≥ 0 satisfy r − j ≥ k − m ≥ 0 and n − r ≥ m. Then consider any permutation P of the elements in {2, 3, 4, …, n − r + 1} comprising exactly m disjoint cycles, noting that the number of such permutations is given by s_{0}(n − r, m) = s_{1}(n − r, m). We now insert a total of j 1s into the cycles of P to give some arrangement P′ of the elements of q_{j} ∪ {2, 3, 4, …, n − r + 1} into m disjoint cycles such that each cycle contains at least one element from {2, 3, 4, …, n−r +1}. The number of distinct ways in which this can be done is

\binom{n − r + j − 1}{j}

since this process is, in terms of enumeration, equivalent to the number of ways of selecting j objects from a set of n−r objects such that repetitions are allowed and order is not significant [5]. A key point is that this result is true for every permutation P on {2, 3, 4, …, n − r + 1}. It is the case, therefore, that

s_{1}(n − r, m)\binom{n − r + j − 1}{j}

enumerates the ways in which the elements of q_{j} ∪ {2, 3, 4, …, n − r + 1} may be written as a product of exactly m disjoint cycles such that each cycle contains at least one element from {2, 3, 4, …, n − r + 1}.

Next, consider S = (1)(1) ⋯ (1), consisting of the product of k − m singleton cycles each containing a 1. The number of distinct cycle structures that can be obtained by inserting r − j − k + m 1s into the cycles of S is given by p(r − j, k − m). Let S′ be one such cycle structure. On appending S′ to P′ we obtain an arrangement of the elements of M(n, r) into k disjoint cycles such that exactly m of these cycles contain at least one element from {2, 3, 4, …, n − r + 1}, and a total of exactly j 1s appear amongst them. It follows from this that

s_{1}(n − r, m)\binom{n − r + j − 1}{j}p(r − j, k − m)  (2)

enumerates the ways in which the elements of M(n, r) can be arranged into exactly k disjoint cycles such that precisely m contain at least one element each from {2, 3, 4, …, n − r + 1} and a total of j 1s between them. We now sum (2) over j to give

s_{1}(n − r, m) ∑_{j=0}^{r−k+m} \binom{n − r + j − 1}{j}p(r − j, k − m),  (3)

which counts the number of ways in which the elements of M(n, r) can be arranged into exactly k disjoint cycles such that precisely m of them contain at least one element from {2, 3, 4, …, n − r + 1}.

In order to evaluate s_{r}(n, k), it remains to sum (3) over m to obtain the result

s_{r}(n, k) = ∑_{m=0}^{k} s_{1}(n − r, m) ∑_{j=0}^{r−k+m} \binom{n − r + j − 1}{j}p(r − j, k − m).

On setting i = r − k + m, this can be rewritten as

s_{r}(n, k) = ∑_{i=r−k}^{r} s_{1}(n − r, k − r + i) ∑_{j=0}^{i} \binom{n − r + j − 1}{j}p(r − j, r − i),  (4)

noting in fact that the lower limit of summation on the outer sum may be given as i = 0 since if r − k ≥ 0 then k − r + i < 0 when i < r − k, in which case s_{1}(n − r, k − r + i) = 0, while the inner sum is defined to be zero for negative values of i. Then, noting that

(x)_{n−r} = ∑_{l=0}^{n−r} s_{1}(n − r, l)x^{l}

is the generating function for the (n − r)th row of T_{1}, we see that the coefficient of x^{k} in (1) is indeed equal to (4), thereby showing that (1) is the ordinary generating function for the nth row of T_{r}.

We illustrate the key ideas in the proof of Theorem 10 by way of a concrete example. Suppose that n = 16, r = 9, k = 5, j = 4, and m = 3. Let us consider the permutation P = (2784)(6)(35), which is an arrangement of the elements of {2, 3, 4, …, n − r + 1} = {2, 3, 4, 5, 6, 7, 8} into m = 3 disjoint cycles. The number of such permutations is given by s_{1}(n − r, m) = s_{1}(7, 3). We now insert a total of j = 4 1s into the cycles of P to give some arrangement P′ of the elements of q_{4} ∪ {2, 3, 4, …, 8} = {1, 1, 1, 1, 2, …, 8} into m = 3 disjoint cycles such that each cycle contains at least one element from {2, 3, 4, …, 8}. One way of doing this is by choosing four elements from {2, 3, 4, …, 8} in such a way that repetitions are allowed and order is not significant; 4, 6, 4, and 7 say. We then place as many 1s as are necessary to the left of each of the corresponding numbers in P. This gives rise to P′ = (2178114)(16)(35), noting that there were two 4s in our choice of elements from {2, 3, 4, …, 8}. The number of ways of selecting 4 objects from a set of 7 objects such that repetitions are allowed and order is not significant [5] is given by

\binom{7 + 4 − 1}{4} = \binom{10}{4}.

This is true for all permutations P on {2, 3, 4, …, 8}. It is the case, therefore, that

s_{1}(7, 3)\binom{10}{4}

enumerates the ways in which the elements of {1, 1, 1, 1, 2, …, 8} may be written as a product of exactly 3 disjoint cycles such that each cycle contains at least one element from {2, 3, 4, …, 8}.

Since k − m = 2, we have S = (1)(1). The number of distinct cycle structures that can be obtained by inserting r −j −k +m = 3 1s into the cycles of S is equal to p(r −j, k −m) = p(5, 2) = 2. One of these cycle structures is given by S′ = (111)(11). On appending S′ to P′ we obtain (111)(11)(2178114)(16)(35), which is an arrangement of the elements of M(16, 9) into 5 disjoint cycles such that exactly 3 of these cycles contain at least one element from {2, 3, 4, …, 8}, and a total of exactly 4 1s appear amongst them. It follows from this that

s_{1}(7, 3)\binom{10}{4}p(5, 2)

enumerates the ways in which the elements of M(16, 9) can be arranged into exactly 5 disjoint cycles such that precisely 3 contain at least one element each from {2, 3, 4, …, 8} and a total of 4 1s between them. There then follows the reasonably straightforward task of summing over j and then m.

It is of course the case that G_{n,1}(x) generates the rows of the number triangle of the Stirling numbers of the first kind. However, the generating functions also take particular simple forms for the cases r = 2 and r = 3 by using [11]

∑_{b=0}^{c} \binom{a + b}{b} = \binom{a + c + 1}{c}

together with the fact that the non-zero entries of the first three rows of the number triangle for p(n, k) are each equal to 1. We have, bearing in mind once more that p(0, k) = 0 for k ∈ ℕ and p(0, 0) = 1 by definition,

G_{n,2}(x) = (x)_{n−2} (x^{2} + \binom{n − 1}{1}x + \binom{n − 1}{2}) ,
G_{n,3}(x) = (x)_{n−3} (x^{3} + \binom{n − 2}{1}x^{2} + \binom{n − 1}{2}x + \binom{n − 1}{3}) .

Next,

G_{n,4}(x) = (x)_{n−4} (x^{4} + \binom{n − 3}{1}x^{3} + (\binom{n − 2}{2} + 1) x^{2} + \binom{n − 1}{3}x + \binom{n − 1}{4}) ,

and the generating functions for r > 4 become increasingly complicated as more of the restricted partition numbers take on values exceeding 1.

Definition 11. The generalized harmonic number H_{n}^{(m)} [11] is given by

H_{n}^{(m)} = ∑_{k=1}^{n} \frac{1}{k^{m}} .

Stirling numbers of the first kind may be given as expressions involving factorials and generalized harmonic numbers [3, 11]. For example,

s_{1}(n, 2) = (n − 1)!H_{n−1}^{(1)},
s_{1}(n, 3) = \frac{(n − 1)!}{2!} ((H_{n−1}^{(1)})^{2} − H_{n−1}^{(2)}) ,
s_{1}(n, 4) = \frac{(n − 1)!}{3!} ((H_{n−1}^{(1)})^{3} − 3H_{n−1}^{(1)}H_{n−1}^{(2)} + 2H_{n−1}^{(3)}) .

We may use (4), in conjunction with these results, to obtain formulas involving factorials, generalized harmonic numbers, and polynomials for the entries in the columns of T_{r} for r ≥ 2. For example, we have, for n ≥ 3,

s_{2}(n, 2) = s_{1}(n − 2, 0) + \binom{n − 1}{1}s_{1}(n − 2, 1) + \binom{n − 1}{2}s_{1}(n − 2, 2)

= (n − 1)(n − 3)! + \frac{(n − 1)(n − 2)}{2}(n − 3)!H_{n−3}

= \frac{(n − 1)(n − 3)!}{2} (2 + (n − 2)H_{n−3})

and, for n ≥ 4,

s_{2}(n, 3) = s_{1}(n − 2, 1) + \binom{n − 1}{1}s_{1}(n − 2, 2) + \binom{n − 1}{2}s_{1}(n − 2, 3)

= (n − 3)! + (n − 1)(n − 3)!H_{n−3} + \frac{(n − 1)(n − 2)}{2} · \frac{(n − 3)!}{2} ((H_{n−3})^{2} − H_{n−3}^{(2)})

= \frac{(n − 3)!}{4} (4 + 4(n − 1)H_{n−3} + (n − 1)(n − 2) ((H_{n−3})^{2} − H_{n−3}^{(2)})) .

4 A recurrence relation

In Section 5 we show how to obtain, in a recursive manner, exponential generating functions for the columns of T_{r}. This is achieved by way of a recurrence relation that is derived in the current section. Use will be made of the following well-known lemma [4, 5].

Lemma 12.

s_{1}(n, k) = (n − 1)s_{1}(n − 1, k) + s_{1}(n − 1, k − 1).

Proof. First, if we append the singleton cycle (n) to any permutation of the elements of {1, 2, …, n − 1} comprising exactly k − 1 disjoint cycles, we obtain a permutation of the elements of {1, 2, …, n} consisting of exactly k disjoint cycles. This process contributes to s_{1}(n − 1, k − 1) of the permutations enumerated by s_{1}(n, k).

Next, suppose we are given some permutation P of the elements of {1, 2, …, n − 1} comprising exactly k disjoint cycles. Let X be one of these cycles. If X is composed of m elements from {1, 2, …, n − 1}, there are m possible positions in which the element n could be inserted into X to form a cycle, each of which gives rise to a permutation of the elements of {1, 2, …, n} consisting of exactly k disjoint cycles. Summing over all possible cycles of P results in the generation of a total of n − 1 permutations of the elements of {1, 2, …, n} consisting of exactly k disjoint cycles. We then sum over all possible permutations of {1, 2, …, n − 1} comprising exactly k cycles, a process which contributes to (n − 1)s_{1}(n − 1, k) of the permutations enumerated by s_{1}(n, k).

This completes the proof of the Lemma, bearing in mind that each of the permutations of the elements of {1, 2, …, n} comprising exactly k disjoint cycles will eventually arise by way of the above processes, and the resultant permutations will in fact all be distinct.

The result given by Lemma 12 does not apply when calculating s_{r}(n, k) for r ≥ 2, and requires considerable modification in order to cover the more general case we are considering here. The extended Stirling numbers of the first kind satisfy the recurrence relation as given in Theorem 13:

Theorem 13. For n > r,

s_{r}(n, k) = (n − 1)s_{r}(n − 1, k) + s_{r}(n − 1, k − 1)− ∑_{i=2}^{r}(i − 1) \begin{matrix}⌊ & \frac{r}{i} & ⌋ \\ ∑ \\ j=1 \end{matrix} s_{r−ji}(n − 1 − ji, k − j)

− \begin{matrix}⌊ & \frac{r}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} \begin{matrix}⌊ & \frac{r}{i} & ⌋ \\ ∑ \\ j=2 \end{matrix} s_{r−ji}(n − 1 − ji, k − j).

Proof. If the 1s in M(n, r) were distinguishable from one another, we could use the argument as given in Lemma 12 to establish that s_{r}(n, k) = (n − 1)s_{r}(n − 1, k) + s_{r}(n − 1, k − 1). The fact that the 1s are indistinguishable from one another, however, does in fact mean there are two potential sources of overcounting that arise when using (n−1)s_{r}(n−1, k)+s_{r}(n−1, k−1) in an attempt to evaluate s_{r}(n, k), both of which will be considered in due course. This is in contrast to the corresponding situation for the extended Stirling numbers of the second kind [9], for which there was only one source.

Note first that the term s_{r}(n − 1, k − 1) does not contribute to any overcounting. This is because, on appending the singleton cycle (n − r + 1) to any arrangement of the elements of M(n − 1, r) into exactly k − 1 disjoint cycles, we obtain an arrangement of the elements of M(n, r) into exactly k disjoint cycles that is distinct from any other arrangement formed in this manner. The overcounting arises solely from the term (n − 1)s_{r}(n − 1, k), and occurs when attempting to obtain new arrangements by inserting the element n − r + 1 into cycles of the form C_{i} present in arrangements of the elements of M(n − 1, r) into exactly k disjoint cycles.

One source of overcounting comes about when an arrangement Q of M(n − 1, r) into k disjoint cycles contains multiple copies of C_{i} (see Definition 7) for some i ≥ 1. If Q has j copies of C_{i} for some j ≥ 2, then, on inserting the element n − r + 1 to each of these cycles in turn, we will obtain j − 1 redundant arrangements. Let N(|C_{i}| = j) and N(|C_{i}| ≥ j) denote the number of the arrangements enumerated by s_{r}(n − 1, k) possessing exactly j copies of C_{i} and at least j copies of C_{i}, respectively. Note here that

N(|C_{i}| ≥ j) = s_{r−ji}(n − 1 − ji, k − j).

This is because each of the arrangements enumerated by the expression on the left-hand side possesses j copies of C_{i}, and the removal of these, therefore, will not affect the enumeration. When these cycles have been removed, we are left with all those arrangements possessing k − j disjoint cycles, r − ji 1s, and a total of n − 1 − ji elements, which are precisely those arrangements enumerated by s_{r−ji}(n − 1 − ji, k − j).

We first consider the situation for some fixed i ∈ ℕ. With a = ⌊\frac{r}{i}⌋, we sum over all such redundant arrangements to obtain

∑_{j=2}^{a}(j − 1)N (|C_{i}| = j) = ∑_{j=2}^{a−1}(j − 1) (N (|C_{i}| ≥ j) − N (|C_{i}| ≥ j + 1)) + (a − 1)N (|C_{i}| = a)

= ∑_{j=2}^{a} s_{r−ji}(n − 1 − ji, k − j).

This is then summed over all possible values of i to give the second double sum in the statement of the theorem. Note that the upper limit on the outer sum is equal to ⌊\frac{r}{2}⌋ since, for any given i, we would require at least two copies of C_{i} for redundant arrangements to occur in this way.

The second source of overcounting arises when inserting the element n−r +1 into a cycle C_{i} for some i ≥ 2. This results in just one possible cycle. The insertion of n − r + 1 into a cycle of length i comprising at least a pair of distinct elements, on the other hand, gives rise to i possible cycles. Thus, whenever n − r + 1 is inserted into a cycle of length i, there is a discrepancy of i − 1 in the enumeration if, and only if, this cycle is C_{i}. As in the previous case, we first fix i ∈ ℕ, let a = ⌊\frac{r}{i}⌋ and sum over all such redundant arrangements to give

(i − 1) ∑_{j=1}^{a} jN (|C_{i}| = j) = (i − 1) ∑_{j=1}^{a−1} j (N (|C_{i}| ≥ j) − N (|C_{i}| ≥ j + 1)) + aN (|C_{i}| = a)

= (i − 1) ∑_{j=1}^{a} s_{r−ji}(n − 1 − ji, k − j).

We then sum over all possible values of i once more to give the first double sum in the statement of the theorem, noting that the upper limit of the outer sum in this case is r rather than ⌊\frac{r}{2}⌋ since a single copy of C_{i} will give rise to redundant arrangements in the manner described above.

5 Exponential generating functions

Definition 14. The shifted exponential generating function H_{r,k}(x) for the sequence of column k of the number triangle T_{r} is defined by

H_{r,k}(x) = ∑_{n=0}^{∞} \frac{s_{r}(n + b, k)}{n!}x^{n},

where b is a function of both r and k given by b(r, k) = max{r, k}.

It is well-known [4, 5] that the exponential generating function for the kth column of T_{1} is given by

\frac{( − log(1 − x))^{k}}{k!} .

From this and Definition 14 it follows that

H_{1,k}(x) = \frac{d^{k}}{dx^{k}} (\frac{(− log(1 − x))^{k}}{k!} )

= \frac{1}{(1 − x)^{k}} ∑_{j=0}^{k−1} \frac{c_{1}(k, k − j)}{j!} (− log(1 − x))^{j} .

We show here how to calculate recursively the exponential generating function for the kth column of T_{r} for r ≥ 2. We shall find it expedient to obtain, in the order given, the sequence of generating functions H_{2,1}(x), H_{2,2}(x), H_{2,3}(x), H_{2,4}(x), … followed by the sequence H_{3,1}(x), H_{3,2}(x), H_{3,3}(x), H_{3,4}(x), …, and so on. Theorem 13 will be used in order to carry out these calculations.

As will be seen, each of the generating functions is obtained by solving a differential equation. The reason for using the shifted exponential generating functions in the manner described above is to keep the solutions of these equations relatively straightforward. The shifts ensure that the first non-zero coefficient of each generating function appears at position zero (i.e. the constant term in each of these shifted power series is non-zero), as becomes clear on examining the tables in Section 7.

Theorem 15.

H_{2,1}(x) = \frac{2 − 2x + x^{2}}{2(1 − x)^{2}} .

Proof. First, we utilise Theorem 13 to obtain the recurrence relation

s_{2}(n, k) = (n − 1)s_{2}(n − 1, k) + s_{2}(n − 1, k − 1) − s_{0}(n − 3, k − 1) − s_{0}(n − 3, k − 2). (5)

On setting k = 1, replacing n with n + 3, and noting that s_{0}(n, k) = s_{1}(n, k), we have

s_{2}(n + 3, 1) = (n + 2)s_{2}(n + 2, 1) + s_{2}(n + 2, 0) − s_{1}(n, 0) − s_{1}(n, −1),

Then, since s_{2}(n + 2, 0) = s_{1}(n, −1) = 0 for all n ≥ 0, and s_{1}(n, 0) = 1 if n = 0 but 0 otherwise, it follows that

∑_{n=0}^{∞} \frac{s_{2}(n + 3, 1)}{n!}x^{n} = ∑_{n=0}^{∞} \frac{(n + 2)s_{2}(n + 2, 1)}{n!}x^{n} − ∑_{n=0}^{∞} \frac{s_{1}(n, 0)}{n!}x^{n}

= ∑_{n=0}^{∞} \frac{ns_{2}(n + 2, 1)}{n!}x^{n} + 2 ∑_{n=0}^{∞} \frac{s_{2}(n + 2, 1)}{n!}x^{n} − 1

= ∑_{n=1}^{∞} \frac{s_{2}(n + 2, 1)}{(n − 1)!}x^{n} + 2 ∑_{n=0}^{∞} \frac{s_{2}(n + 2, 1)}{n!}x^{n} − 1

= x ∑_{n=0}^{∞} \frac{s_{2}(n + 3, 1)}{n!}x^{n} + 2 ∑_{n=0}^{∞} \frac{s_{2}(n + 2, 1)}{n!}x^{n} − 1,

from which we obtain

(1 − x)H′_{2,1}(x) − 2H_{2,1}(x) = −1.

Solving this first-order linear differential equation [12], with the boundary condition H_{2,1}(0) = 1, gives

H_{2,1}(x) = \frac{2 − 2x + x^{2}}{2(1 − x)^{2}} .

In order to obtain the shifted exponential generating function H_{2,2}(x), we may, in a similar manner to that given in Theorem 15, use (5) to give

(1 − x)H′_{2,2}(x) − 2H_{2,2}(x) = ∑_{n=0}^{∞} \frac{s_{2}(n + 2, 1)}{n!}x^{n} − ∑_{n=0}^{∞} \frac{s_{1}(n, 1)}{n!}x^{n} − 1.

The first and second sums on the right are equal to H_{2,1}(x) and − log(1 − x), respectively, so that we are left to solve

(1 − x)H′_{2,2}(x) − 2H_{2,2}(x) = H_{2,1}(x) + log(1 − x) − 1.

With H_{2,2}(0) = 1, this has the solution

H_{2,2}(x) = \frac{(2 − 2x + x^{2}) (1 − log(1 − x))}{2(1 − x)^{2}}.

For the case k = 3 we have the differential equation

(1 − x)H′_{2,3}(x) − 3H_{2,3}(x) = H′_{2,2}(x) − ∫_{0}^{x} H_{1,2}(t) dt − H_{1,1}(x),

from which it follows that

H_{2,3}(x) = \frac{(2 − 2x + x^{2}) + (4 − 2x + x^{2}) L + L^{2}}{2(1 − x)^{3}} ,

where L = − log(1 − x). In fact, for k ≥ 3, we have the general differential equation

(1 − x)H′_{2,k}(x) − kH_{2,k}(x) = H′_{2,k−1}(x) − ∫_{0}^{x} H_{1,k−1}(t) dt − H_{1,k−2}(x),

which gives

H_{2,4}(x) = \frac{(4 − 4x + 2x^{2}) + (16 − 8x + 4x^{2}) L + (12 − 2x + x^{2}) L^{2} + 2L^{3}}{4(1 − x)^{4}} ,

and so on.

In order to calculate the shifted exponential generating functions G_{3,k}(x) we use the recurrence

s_{3}(n, k) = (n − 1)s_{3}(n − 1, k) + s_{3}(n − 1, k − 1)
− s_{1}(n − 3, k − 1) − 2s_{0}(n − 4, k − 1) − s_{1}(n − 3, k − 2) − s_{0}(n − 4, k − 3),

which may be obtained via Theorem 13. The first two such functions are given by

H_{3,1}(x) = \frac{3 − 6x + 6x^{2} − 2x^{3}}{3(1 − x)^{3}} and H_{3,2}(x) = \frac{6 − 6x + 3x^{2} + (−6 + 12x − 12x^{2} + 4x^{3}) L}{6(1 − x)^{3}}.

Although the manipulations do become a little more complicated for larger values of r, the underlying method is the same, with the generating functions being obtained recursively.

6 Acknowledgement

I would like to thank an anonymous referee for making a number of suggestions that have helped improve the clarity of this paper.

7 Tables

n s_{1}(n, 1) s_{1}(n, 2) s_{1}(n, 3) s_{1}(n, 4) s_{1}(n, 5) s_{1}(n, 6) s_{1}(n, 7) s_{1}(n, 8)
1  1
2  1  1
3  2  3  1
4  6  11  6  1
5  24  50  35  10  1
6 120  274  225  85  15  1
7 720  1764  1624  735  175  21  1
8 5040 13068 13132 6769  1960  322  28  1

Table 1: Unsigned Stirling numbers of the first kind, s_{1}(n, k).

n s_{2}(n, 1) s_{2}(n, 2) s_{2}(n, 3) s_{2}(n, 4) s_{2}(n, 5) s_{2}(n, 6) s_{2}(n, 7) s_{2}(n, 8)

1

2  1  1
3  1  2  1
4  3  6  4  1
5  12  26  20  7  1
6  60  140  121  51  11  1
7 360  894  849  410  110  16  1
8 2520  6594  6763  3634  1135  211  22  1

Table 2: The number of arrangements of the elements from the multiset M(n, 2) into exactly k disjoint cycles, s_{2}(n, k).

n s_{3}(n, 1) s_{3}(n, 2) s_{3}(n, 3) s_{3}(n, 4) s_{3}(n, 5) s_{3}(n, 6) s_{3}(n, 7) s_{3}(n, 8)

1 2

3  1  1  1
4  1  3  2  1
5  4  10  9  4  1
6  20  50  48  24  7  1
7 120  310  315  171  56  11  1
8 840  2254  2419  1409  505  116  16  1

Table 3: The number of arrangements of the elements from the multiset M(n, 3) into exactly k disjoint cycles, s_{3}(n, k).

n s_{4}(n, 1) s_{4}(n, 2) s_{4}(n, 3) s_{4}(n, 4) s_{4}(n, 5) s_{4}(n, 6) s_{4}(n, 7) s_{4}(n, 8)

1 2 3

4  1  2  1  1
5  1  4  4  2  1
6  5  15  17  10  4  1
7  30  85  97  61  25  7  1
8 210  595  691  451  192  57  11  1

Table 4: The number of arrangement of the elements from the multiset M(n, 4) into exactly k disjoint cycles, s_{4}(n, k).

References

[1] M. Aigner, Combinatorial Theory, Springer, 1979.

[2] G. Beck, Sequence \underline{A035098} in N. J. A. Sloane, ed., The On-Line Encyclopedia of Integer

    Sequences, http://oeis.org/

[3] A. T. Benjamin, G. O. Preston, and J. J. Quinn, A Stirling encounter with harmonic numbers, Math. Mag. 75 (2002), 95–103.

[4] D. Branson, Stirling numbers and Bell numbers: their role in combinatorics and probability, Math. Sci. 25 (2000), 1–31.

[5] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[6] C. A. Charalambides, Enumerative Combinatorics, Chapman & Hall, 2002.

[7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1998.

[8] M. Griffiths, Generalized near-Bell numbers, J. Integer Seq. 12 (2009), Article 09.5.7.

[9] M. Griffiths and I. Mező, A generalization of Stirling numbers of the second kind via a special multiset, J. Integer Seq. 13 (2010), Article 10.2.5.

[10] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 2008.

[11] D. E. Knuth, The Art of Computer Programming, Volume 1, Addison-Wesley, 1968.

[12] H. Neill and D. Quadling, Further Pure 2 & 3, Cambridge University Press, 2005.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/

2010 Mathematics Subject Classification: Primary 11B73; Secondary 05A05, 05A10, 05A15, 11B37. Keywords: Stirling number of the first kind, multiset, permutation, cycle, recurrence relation, generating function.

(Concerned with sequence \underline{A008284}, \underline{A035098}, and \underline{A130534}.)

Received January 3 2014; revised version received April 27 2014. Published in Journal of Integer Sequences, May 11 2014.

Return to Journal of Integer Sequences home page.