On Certain Sums of Stirling Numbers with Binomial Coefficients

H. W. Gould Department of Mathematics West Virginia University Morgantown, WV 26506

USA

henrygou@gmail.com

Harris Kwong

Department of Mathematical Sciences

SUNY Fredonia Fredonia, NY 14063

USA

kwong@fredonia.edu

Jocelyn Quaintance Department of Computer Science

University of Pennsylvania Philadelphia, PA 19104

USA

jocelynq@seas.upenn.edu

Abstract

We study two sums involving the Stirling numbers and binomial coefficients. We find their closed forms, and discuss the connection between these sums.

Dedicated to the memory of our mentors, Professors Leonard Carlitz and Albert Nijenhuis

1 Introduction

Stirling numbers of the first and second kind, denoted by s(n, k) and S(n, k) respectively, in Riordan’s [8] popular notation, have long fascinated mathematicians. They were named for James Stirling [13] who used them in 1730. In 1852 Schläfli [10] studied relations between s(n, k) and S(n, k). Then in 1960 Gould [3] extended Schläfli’s work by discovering the pair of dual relations

(−1)^{n}S(m, m − n) = ∑_{k=0}^{n} \binom{n + m}{n − k}\binom{n − m}{n + k}s(n + k, k),

(−1)^{n}s(m, m − n) = ∑_{k=0}^{n} \binom{n + m}{n − k}\binom{n − m}{n + k}S(n + k, k).

Prompted by a recent problem [7] in the Amer. Math. Monthly that asked the readers to find a closed form expression for ∑_{k=0}^{n}(−1)^{k}\binom{2n}{n+k}s(n + k, k), Gould tried to relate this sum to the first of his dual sums. By choosing m = n + 1 and noting that \binom{−1}{n−k} = (−1)^{n+k}, the first of Gould’s relations yields

∑_{k=0}^{n}(−1)^{k}\binom{2n + 1}{n − k}s(n + k, k) = S(n + 1, 1) = 1,

which is not quite the proposed result but suggested that we study a wider range of sums. Motivated by this and other experiments using Maple, we study the following sums:

f_{m}(n) = ∑_{k=0}^{n+m}(−1)^{k}\binom{2n + m}{n + k}s(n + k, k),

F_{m}(n) = ∑_{k=0}^{n+m}(−1)^{k}\binom{2n + m}{n + k}S(n + k, k),

g_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n + m}{n − k}s(n + k, k),

G_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n + m}{n − k}S(n + k, k).

For m ≥ 0, the closed forms for f_{m}(n) and F_{m}(n) are easy to obtain, but the sums g_{m}(n) and G_{m}(n) are more complicated. We also study the case of m < 0. We shall derive formulas for these sums, and discuss their connections. To simplify the notation, define

f̂_{m}(n) = f_{−m}(n), F̂_{m}(n) = F_{−m}(n), ĝ_{m}(n) = g_{−m}(n), and Ĝ_{m}(n) = G_{−m}(n).

Consequently, throughout this paper, unless otherwise stated, m will denote a nonnegative integer, and n a positive integer.

2 Closed forms for f_{m}(n) and F_{m}(n)

We start with f_{0}(n) and determine its value using a combinatorial argument.

Theorem 1. For any positive integer,

f_{0}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n}{n + k}s(n, k) = (2n − 1)!!,

where (2n − 1)!! denotes the double factorial (2n − 1)(2n − 3) ⋯ 3 · 1.

Proof. Recall that the unsigned Stirling number of the first kind c(n, k) = (−1)^{n−k}s(n, k) counts the number of n-permutations with k disjoint cycles. Then

f_{0}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n}{n + k}s(n + k, k)

= ∑_{k=0}^{n}(−1)^{n−k}\binom{2n}{n − k}c(n + k, k)

= ∑_{j=0}^{n}(−1)^{j}\binom{2n}{j}c(2n − j, n − j).

Let S be the set of 2n-permutations with n cycles, and A_{i} be the subset of permutations of S with i as a fixed point. Then

|A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{j}}| = c(2n − j, n − j).

It follows from the principle of inclusion-exclusion that f_{0}(n) is precisely the number of 2npermutations without fixed points. Notice that if a permutation in S has no fixed point, it must be a permutation with exactly n transpositions (that is, 2-cycles). After lining up 2n objects, we can take the elements two at a time to form n transpositions. Since the order within each transposition does not matter, it is just a matter of calculating the order among the transpositions; hence, there are

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

permutations of 2n with exactly n transpositions. Thus, f_{0}(n) = (2n − 1)!!.

The proof suggests we should examine the combinatorial interpretation of f_{m}(n). Let c^{∗}(n, k) denote the number of n-permutations with k cycles and no fixed points. It is called the unsigned associated Stirling number of the first kind ([2, p. 256] and [8, p. 73]). In a similar fashion, we can define S^{∗}(n, k) as the number of partitions of an n-set into k subsets with no singleton subset as any part. The number S^{∗}(n, k) is the associated Stirling number of the second kind ([2, p. 221] and [8, p. 77]). See [6] for a more thorough discussion of the associated Stirling numbers.

Lemma 2. The identity f_{m}(n) = (−1)^{m}c^{∗}(2n + m, n + m) holds for any integers m and n such that n + m ≥ 1.

Proof. Let S be the set of (2n + m)-permutations with n + m cycles, and A_{i} be the subset of permutations of S with i as a fixed point. Then

|A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{j}} | = c(2n + m − j, n + m − j).

Therefore, according to the principle of inclusion-exclusion,

c^{∗}(2n + m, n + m) = ∑_{j=0}^{n+m}(−1)^{j}\binom{2n + m}{j}c(2n + m − j, n + m − j)

= ∑_{k=n+m}^{0}(−1)^{n+m−k}\binom{2n + m}{n + m − k}c(n + k, k)

= (−1)^{m} ∑_{k=0}^{n+m}(−1)^{k}\binom{2n + m}{n + k}s(n + k, k).

Therefore, c^{∗}(2n + m, n + m) = (−1)^{m}f_{m}(n).

By using an almost identical argument, we obtain a similar result for the associated Stirling numbers of the second kind.

Lemma 3. The identity F_{m}(n) = (−1)^{n+m}S^{∗}(2n + m, n + m) holds for any integers m and n such that n + m ≥ 1.

These combinatorial interpretations allow us to determine the exact values of f_{m}(n) and F_{m}(n) for m ≥ 0. Again, due to their similarity, we shall only prove the first result.

Theorem 4. For any integer n ≥ 1, f_{0}(n) = (2n − 1)!!, and f_{m}(n) = 0 if m > 0.

Proof. Lemma 2 states that f_{m}(n) = (−1)^{m}c^{∗}(2n + m, n + m). If m > 0, it is clear that 2n + m < 2(n + m), hence c^{∗}(2n + m, n + m) = 0. When m = 0, we have f_{0}(n) = c^{∗}(2n, n), which counts the number of permutations with exactly n transpositions. Hence, f_{0}(n) = (2n − 1)!!.

Theorem 5. For any integer n ≥ 1, F_{0}(n) = (−1)^{n}(2n − 1)!!, and F_{m}(n) = 0 if m > 0.

The same conclusions can be drawn from generating functions.

Lemma 6. Let T be a nonempty set of positive integers. Define c_{T} (n, k) as the number of n-permutations with k disjoint cycles whose lengths belong to T. Then

c_{T} (x, y) := ∑_{n,k≥0} c_{T} (n, k) \frac{x^{n}}{n!} y^{k} = exp (y ∑_{j∈T} \frac{x^{j}}{j} ) .

Proof. The result follows easily from the exponential formula [15]. Alternatively, we can prove it directly as follows. For any n-permutation, let n_{j} denotes the number of j-cycles. It is a routine exercise to show that

c_{T} (n, k) = ∑_{T} \frac{n!}{∏_{j∈T} n_{j}! j^{n_{j}}} ,

where the summation ∑_{T} is taken over all n_{j} ≥ 0, where j ∈ T, such that ∑_{j∈T} n_{j} = k, and ∑_{j∈T} jn_{j} = n. Then

∑_{n,k≥0} c_{T} (n, k) \frac{x^{n}}{n!} y^{k} = ∑_{n,k≥0} ∑_{T} ∏_{j∈T} \frac{x^{jn_{j}}y^{n_{j}}}{n_{j}! j^{n_{j}}}

= ∑_{n,k≥0} ∑_{T} ∏_{j∈T} \frac{1}{n_{j}!} (\frac{x^{j}y}{j} )^{n_{j}} .

Noting that this is in the form of a convolution, we determine that

c_{T} (x, y) = ∏_{j∈T} ∑_{n_{j}≥0} \frac{1}{n_{j}!} (\frac{x^{j}y}{j} )^{n_{j}} = ∏_{j∈T} exp (\frac{x^{j}y}{j} ) = exp (y ∑_{j∈T} \frac{x^{j}}{j} ) .

Lemma 7. Let T be a nonempty set of positive integers. Define S_{T} (n, k) as the number of ways to partition an n-set into k subsets with cardinalities belonging to T. Then

S_{T} (x, y) := ∑_{n,k≥0} S_{T} (n, k) \frac{x^{n}}{n!} y^{k} = exp (y ∑_{j∈T} \frac{x^{j}}{j!} ) .

Proof. The proof is identical to that of Lemma 6, except that

S_{T} (n, k) = ∑_{T} \frac{n!}{∏_{j∈T} n_{j}! (j!)^{n_{j}}} .

For our purpose, we need T = ℕ − {1}. We find

c^{∗}(x, y) := ∑_{n,k≥0} c^{∗}(n, k) \frac{x^{n}}{n!} y^{k} = exp (y ∑_{j≥2} \frac{x^{j}}{j} ) = (1 − x)^{−y}e^{−xy},  (1)

and

S^{∗}(x, y) := ∑_{n,k≥0} S^{∗}(n, k) \frac{x^{n}}{n!} y^{k} = exp (y ∑_{j≥2} \frac{x^{j}}{j!} ) = e^{y(e^{x}−1−x)}.  (2)

From the generating function c^{∗}(x, y), it is clear that the coefficient of x^{r}y^{t} is zero if r < 2t. Hence, f_{m}(n) = (−1)^{m}c^{∗}(2n + m, n + m) = 0 if m > 0. For m = 0, the coefficient of \frac{x^{2n}}{(2n)!} y^{n}

is \frac{(2n)!}{n! 2^{n}} = (2n − 1)!!. The argument for F_{m}(n) is similar.

3 Formulas for f̂_{m}(n) and F̂_{m}(n)

Lemma 2 shows that f_{m}(n) = (−1)^{m}c^{∗}(2n + m, n + m). Its combinatorial interpretation implies that f_{m}(n) is nonzero if 1 − n ≤ m ≤ 0. We obtain the following result.

Theorem 8. For any integer m that satisfies 0 < m ≤ n − 1,

f̂_{m}(n) = ∑ \frac{(−1)^{m}(2n − m)!}{∏_{i≥2} n_{i}! i^{n_{i}}},

where the summation is taken over all integers n_{2}, n_{3}, n_{4}, … ≥ 0 such that ∑_{i≥2} n_{i} = n − m, and ∑_{i≥2} in_{i} = 2n − m.

We shall present an analytic proof as well as a combinatorial proof.

Proof. Since f_{m}(n) = (−1)^{m}c^{∗}(2n + m, n + m), we gather from the generating function c^{∗}(x, y) that f_{m}(n) is (−1)^{m}(2n + m)! times the coefficient of x^{2n+m}y^{n+m} in the power series expansion of

exp [y (\frac{x^{2}}{2} + \frac{x^{3}}{3} + \frac{x^{4}}{4} + ⋯)] = ∑_{k=0}^{∞} \frac{y^{k}}{k!} (\frac{x^{2}}{2} + \frac{x^{3}}{3} + \frac{x^{4}}{4} + ⋯)^{k} .

We conclude that f_{m}(n) is (−1)^{m}(2n + m)!/(n + m)! times the coefficient of x^{2n+m} in the power series expansion of

(\frac{x^{2}}{2} + \frac{x^{3}}{3} + \frac{x^{4}}{4} + ⋯)^{n+m} .

For m < 0, replace m with −m. Then f̂_{m}(n) is (−1)^{m}(2n−m)!/(n−m)! times the coefficient of x^{2n−m} in the expansion of the polynomial

(\frac{x^{2}}{2} + \frac{x^{3}}{3} + \frac{x^{2}}{4} + ⋯)^{n−m} .

Applying the multinomial theorem yields the result immediately.

Here is an alternate proof.

Proof. Since f̂_{m}(n) = f_{−m}(n) = (−1)^{m}c^{∗}(2n − m, n − m), it suffices to find a formula for the number of permutations of 2n − m with exactly n − m cycles none of which is a 1-cycle. Assume there are n_{i} cycles of length i, then n_{2}, n_{3}, n_{4}, … ≥ 0, and

n_{2} + n_{3} + n_{4} + ⋯ = n − m,
2n_{2} + 3n_{3} + 4n_{4} + ⋯ = 2n − m,

and there are

\frac{(2n − m)!}{∏_{i≥2} n_{i}! i^{n_{i}}}

such permutations. This, when combined with the addition principle, completes the proof.

An almost identical argument leads to the next result. Theorem 9. For any integer m that satisfies 0 < m ≤ n − 1,

F̂_{m}(n) = ∑ \frac{(−1)^{n+m}(2n − m)!}{∏_{i≥2} n_{i}! (i!)^{n_{i}}},

where the summation is taken over all integers n_{2}, n_{3}, n_{4}, … ≥ 0 such that ∑_{i≥2} n_{i} = n − m, and ∑_{i≥2} in_{i} = 2n − m.

In order to use these two results effectively, take note that the two conditions on the n_{i}’s imply that

n_{3} + 2n_{4} + 3n_{5} + 4n_{6} + ⋯ = m.

The possible solutions for 0 ≤ m ≤ 4 are summarized below.

m 2n − m n_{2} n_{3} n_{4} n_{5} n_{6}  \frac{(2n−m)!}{∏_{i≥2} n_{i}! i^{n_{i}}}  \frac{(2n−m)!}{∏_{i≥2} n_{i}! (i!)^{n_{i}}}
0  2n  n 0 0 0 0  \frac{(2n)!}{n! 2^{n}}  \frac{(2n)!}{n! 2^{n}}
1 2n − 1 n − 2 1 0 0 0 \frac{(2n−1)!}{3(n−2)! 2^{n−2}}  \frac{(2n−1)!}{6(n−2)! 2^{n−2}}
2 2n − 2 n − 3 0 1 0 0 \frac{(2n−2)!}{4(n−3)! 2^{n−3}}  \frac{(2n−2)!}{24(n−3)! 2^{n−3}}
n − 4 2 0 0 0 \frac{(2n−2)!}{18(n−4)! 2^{n−4}}  \frac{(2n−2)!}{72(n−4)! 2^{n−4}}
3 2n − 3 n − 4 0 0 1 0 \frac{(2n−3)!}{5(n−4)! 2^{n−4}}  \frac{(2n−3)!}{120(n−4)! 2^{n−4}}
n − 5 1 1 0 0 \frac{(2n−3)!}{12(n−5)! 2^{n−5}}  \frac{(2n−3)!}{144(n−5)! 2^{n−5}}
n − 6 3 0 0 0 \frac{(2n−3)!}{162(n−6)! 2^{n−6}}  \frac{(2n−3)!}{1296(n−6)! 2^{n−6}}
4 2n − 4 n − 5 0 0 0 1 \frac{(2n−4)!}{6(n−5)! 2^{n−5}}  \frac{(2n−4)!}{720(n−5)! 2^{n−5}}
n − 6 1 0 1 0 \frac{(2n−4)!}{15(n−6)! 2^{n−6}}  \frac{(2n−4)!}{720(n−6)! 2^{n−6}}
n − 6 0 2 0 0 \frac{(2n−4)!}{32(n−6)! 2^{n−6}}  \frac{(2n−4)!}{1152(n−6)! 2^{n−6}}
n − 7 2 1 0 0 \frac{(2n−4)!}{72(n−7)! 2^{n−7}}  \frac{(2n−4)!}{1728(n−7)! 2^{n−7}}
n − 8 4 0 0 0 \frac{(2n−4)!}{1944(n−8)! 2^{n−8}}  \frac{(2n−4)!}{31104(n−8)! 2^{n−8}}

Theorem 8 asserts that

f̂_{1}(n) = −\frac{(2n − 1)!}{3(n − 2)! 2^{n−2}} ,
f̂_{2}(n) = \frac{(2n − 2)!}{4(n − 3)! 2^{n−3}} + \frac{(2n − 2)!}{18(n − 4)! 2^{n−4}} ,
f̂_{3}(n) = −\frac{(2n − 3)!}{5(n − 4)! 2^{n−4}} − \frac{(2n − 3)!}{12(n − 5)! 2^{n−5}} − \frac{(2n − 3)!}{162(n − 6)! 2^{n−6}} ,
f̂_{4}(n) = \frac{(2n − 4)!}{6(n − 5)! 2^{n−5}} + \frac{47(2n − 4)!}{480(n − 6)! 2^{n−6}} + \frac{(2n − 4)!}{72(n − 7)! 2^{n−7}} + \frac{(2n − 4)!}{1944(n − 8)! 2^{n−8}} .

The first few absolute values of each of these four sequences are tabulated in Table 1. All of them appear in the OEIS [12]. More information about these sequences, including their combinatorial meanings, can be found in OEIS.

n  1 2 3 4  5  6  7  8  OEIS #
|f̂_{1}(n)| 0 2 20 210 2520 34650 540540 9459450 A000906
|f̂_{2}(n)| 0 0 6 130 2380 44100 866250 18288270 A000907
|f̂_{3}(n)| 0 0 0 24 924 26432 705320 18858840 A001784
|f̂_{4}(n)| 0 0 0 0 120 7308 303660 11098780 A001785

Table 1: The first eight values of f̂_{m}(n) for m = 1, 2, 3, 4.

Likewise, Theorem 9 yields

F̂_{1}(n) = \frac{(−1)^{n+1}(2n − 1)!}{6(n − 2)! 2^{n−2}},
F̂_{2}(n) = \frac{(−1)^{n}(2n − 2)!}{24(n − 3)! 2^{n−3}} + \frac{(−1)^{n}(2n − 2)!}{72(n − 4)! 2^{n−4}},
F̂_{3}(n) = \frac{(−1)^{n+1}(2n − 3)!}{120(n − 4)! 2^{n−4}} + \frac{(−1)^{n+1}(2n − 3)!}{144(n − 5)! 2^{n−5}} + \frac{(−1)^{n+1}(2n − 3)!}{1296(n − 6)! 2^{n−6}} ,
F̂_{4}(n) = \frac{(−1)^{n}(2n − 4)!}{720(n − 5)! 2^{n−5}} + \frac{(−1)^{n}13(2n − 4)!}{5760(n − 6)! 2^{n−6}} + \frac{(−1)^{n}(2n − 4)!}{1728(n − 7)! 2^{n−7}} + \frac{(−1)^{n}(2n − 4)!}{31104(n − 8)! 2^{n−8}} .

See Table 2. The last sequence does not appear in the OEIS. Note that |f̂_{1}(n)| = 2|F̂_{1}(n)|. We leave it as an exercise to the readers to find a combinatorial explanation.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & OEIS # \\ |F̂_{1}(n)| & 0 & 1 & 10 & 105 & 1260 & 17325 & 270270 & 4729725 & A000457 \\ |F̂_{2}(n)| & 0 & 0 & 1 & 25 & 490 & 9450 & 190575 & 4099095 & A000497 \\ |F̂_{3}(n)| & 0 & 0 & 0 & 1 & 56 & 1918 & 56980 & 1636635 & A000504 \\ |F̂_{4}(n)| & 0 & 0 & 0 & 0 & 1 & 119 & 6825 & 302995 & — \end{matrix}

Table 2: The first eight values of F̂_{m}(n) for m = 1, 2, 3, 4.

4 Formulas for ĝ_{m}(n) and Ĝ_{m}(n)

Next, we study the combinatorial significance of the two sums

ĝ_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n − k}s(n + k, k),

Ĝ_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n − k}S(n + k, k),

where m is a nonnegative integer, an n a positive integer such that 2n ≥ m.

Recall that the unsigned Stirling number of the first kind c(n, k) = (−1)^{n−k}s(n, k) counts the number of n-permutations with k disjoint cycles. We find

ĝ_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n − k}s(n + k, k)

= ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n + k − m}s(n + k, k)

= ∑_{k=0}^{n}(−1)^{n−k}\binom{2n − m}{2n − k − m}s(2n − k, n − k)

= ∑_{k=0}^{n}(−1)^{n−k}\binom{2n − m}{k}s(2n − k, n − k)

= ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{k}c(2n − k, n − k).

Similarly, we have

Ĝ_{m}(n) = (−1)^{n} ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{k}S(2n − k, n − k),

where the Stirling number of the second kind S(n, k) counts the number of ways to partition an n-set into k nonempty subsets.

For any positive integer m, define [m] = {1, 2, …, m}. Let n be a fixed positive integer. For any nonnegative integer m, define S_{m} as the set of permutations of [2n] with n cycles and no fixed points among [2n − m]. Recall that if a permutation in S_{m} has no fixed point, it must be a permutation with exactly n transpositions (that is, 2-cycles). In addition, the fixed points in any permutation from S_{m} must belong to [2n] \ [2n − m]; this implies that the permutations in S_{m} has at most m fixed points.

In an analogous manner, define S̃_{m} as the set of partitions of [2n] into n nonempty subsets none of which is a singleton subset of [2n − m]. If a partition in S̃_{m} has no singleton subset, it must have n parts, each of which a 2-subset. If a partition in S̃_{m} has a singleton subset, its element must be among [2n] \ [2n − m], hence it has at most m singleton subsets as its parts.

We first us the same argument in Theorem 1 to derive two preliminary results about |S_{m}| and |S̃_{m}|.

Lemma 10. For positive integers m and n that satisfy 2n ≥ m,

ĝ_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n − k}s(n + k, k) = |S_{m}|.

Proof. In light of our earlier discussion, it suffices to show that

|S_{m}| = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{k}c(2n − k, n − k).

Let S be the set of all permutations of [2n] with n cycles, without any restriction. For each j ∈ [2n − m], define A_{j} to be the set of permutations of [2n] with j as a fixed point. If a permutation belongs to A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{k}}, it still has n − k cycles whose elements come from [2n] \ {i_{1}, i_{2}, …, i_{k}}. Thus,

|A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{k}} | = c(2n − k, n − k),

and there are \binom{2n−m}{k} choices for \{i_{1}, i_{2}, …, i_{k}\}. Since the permutations in S comprise of n cycles, we obviously need 0 ≤ k ≤ n. The result now follows from the principle of inclusionexclusion.

It is clear that a similar result for |S̃_{m}| also holds.

Lemma 11. For positive integers m and n that satisfy 2n ≥ m,

Ĝ_{m}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n − m}{n − k}S(n + k, k) = (−1)^{n}|S̃_{m}|.

Theorem 12. For positive integers m and n that satisfy 2n ≥ m,

ĝ_{m}(n) = ∑_{j=0}^{m} \binom{m}{j}c^{∗}(2n − j, n − j) = ∑_{j=0}^{m} \binom{m}{j} ∑ \frac{(2n − j)!}{∏_{i≥2} n_{i}! i^{n_{i}}} ,

where the inner sum ∑ is taken over all integers n_{2}, n_{3}, n_{4}, … ≥ 0 such that ∑_{i≥2} n_{i} = n−j, and ∑_{i≥2} in_{i} = 2n − j.

Proof. We need to determine |S_{m}|. Let j be the number of fixed points in a permutation from S_{m}. Since the fixed points come from [2n] \ [2n − m], there are \binom{m}{j} ways to choose these fixed points. The other 2n − j elements form n − j cycles, all with length at least 2. Assume there are n_{i} cycles of length i, then n_{2}, n_{3}, … ≥ 0, and

n_{2} + n_{3} + n_{4} + ⋯ = n − j,
2n_{2} + 3n_{3} + 4n_{4} + ⋯ = 2n − j,

and there are

\frac{(2n − j)!}{∏_{i≥2} n_{i}! i^{n_{i}}}

such permutations. The proof is completed by applying the addition principle, and recalling that 0 ≤ j ≤ m.

Notice that the sum ∑(2n − j)!/ ∏_{i≥2} n_{i}! i^{n_{i}} also appeared in the last section. It is equal to c^{∗}(2n − j, n − j). Then, according to Theorem 12,

ĝ_{1}(n) = \frac{(2n)!}{n! 2^{n}} + \frac{(2n − 1)!}{3(n − 2)! 2^{n−2}} ,
ĝ_{2}(n) = \frac{(2n)!}{n! 2^{n}} + \frac{2(2n − 1)!}{3(n − 2)! 2^{n−2}} + \frac{(2n − 2)!}{4(n − 3)! 2^{n−3}} + \frac{(2n − 2)!}{18(n − 4)! 2^{n−4}} ,
ĝ_{3}(n) = \frac{(2n)!}{n! 2^{n}} + \frac{(2n − 1)!}{(n − 2)! 2^{n−2}} + \frac{3(2n − 2)!}{4(n − 3)! 2^{n−3}} + \frac{(2n − 2)!}{6(n − 4)! 2^{n−4}}

+ \frac{(2n − 3)!}{5(n − 4)! 2^{n−4}} + \frac{(2n − 3)!}{12(n − 5)! 2^{n−5}} + \frac{(2n − 3)!}{162(n − 6)! 2^{n−6}} ,

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

+ \frac{4(2n − 3)!}{5(n − 4)! 2^{n−4}} + \frac{(2n − 3)!}{3(n − 5)! 2^{n−5}} + \frac{2(2n − 3)!}{81(n − 6)! 2^{n−6}}

+ \frac{(2n − 4)!}{6(n − 5)! 2^{n−5}} + \frac{47(2n − 4)!}{480(n − 6)! 2^{n−6}} + \frac{(2n − 4)!}{72(n − 7)! 2^{n−7}}

+ \frac{(2n − 4)!}{1944(n − 8)! 2^{n−8}} .

It is easy to verify that

ĝ_{1}(n) = \frac{(2n + 1)!!}{3}.

Since ĝ_{0}(n) = (2n − 1)!!, we find

3ĝ_{1}(n) = ĝ_{0}(n + 1).

We invite the readers to find a combinatorial proof of this simple identity. We also find

ĝ_{2}(n) = \frac{1}{9} (4n^{3} + 9n^{2} − n − 3)(2n − 3)!!
= \frac{1}{18} (2n + 3)!! + \frac{1}{12} (2n + 1)!! − \frac{1}{12} (2n − 3)!!.

It becomes clear that ĝ_{m}(n) can be written as a linear combination of the double falling factorials of the form m!! for some odd integers m. We invite the readers to devise a combinatorial argument to find its coefficients.

The sequence {ĝ_{1}(n)}_{n≥1} appears in the OEIS [12] as Sequence A051577, but the other sequences {ĝ_{2}(n)}_{n≥1}, {ĝ_{3}(n)}_{n≥1}, and {ĝ_{4}(n)}_{n≥1} do not appear in the OEIS. Their numeric values for n ≤ 8 are listed in Table 3.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & OEIS # \\ ĝ_{1}(n) & 1 & 5 & 35 & 315 & 3465 & 45045 & 675675 & 11486475 & A051577 \\ ĝ_{2}(n) & 1 & 7 & 61 & 655 & 8365 & 123795 & 2082465 & 39234195 & — \\ ĝ_{3}(n) & 1 & 9 & 93 & 1149 & 16569 & 273077 & 5060825 & 104129025 & — \\ ĝ_{4}(n) & 1 & 11 & 131 & 1821 & 29121 & 526631 & 10619735 & 236128585 & — \end{matrix}

Table 3: The first eight values of ĝ_{m}(n) for m = 1, 2, 3, 4.

A similar argument yields the next result.

Theorem 13. For positive integers m and n that satisfy 2n ≥ m,

Ĝ_{m}(n) = ∑_{j=0}^{m}(−1)^{n}\binom{m}{j}S^{∗}(2n − j, n − j) = ∑_{j=0}^{m} \binom{m}{j} ∑ \frac{(−1)^{n}(2n − j)!}{∏_{i≥2} n_{i}! (i!)^{n_{i}}},

where the inner sum ∑ is taken over all integers n_{2}, n_{3}, n_{4}, … ≥ 0 such that ∑_{i≥2} n_{i} = n−j, and ∑_{i≥2} in_{i} = 2n − j.

Theorem 13 yields the following:

Ĝ_{1}(n) = \frac{(−1)^{n}(2n)!}{n! 2^{n}} + \frac{(−1)^{n}(2n − 1)!}{6(n − 2)! 2^{n−2}},
Ĝ_{2}(n) = \frac{(−1)^{n}(2n)!}{n! 2^{n}} + \frac{(−1)^{n}(2n − 1)!}{3(n − 2)! 2^{n−2}} + \frac{(−1)^{n}(2n − 2)!}{24(n − 3)! 2^{n−3}} + \frac{(−1)^{n}(2n − 2)!}{72(n − 4)! 2^{n−4}},
Ĝ_{3}(n) = \frac{(−1)^{n}(2n)!}{n! 2^{n}} + \frac{(−1)^{n}(2n − 1)!}{2(n − 2)! 2^{n−2}} + \frac{(−1)^{n}(2n − 2)!}{8(n − 3)! 2^{n−3}} + \frac{(−1)^{n}(2n − 2)!}{24(n − 4)! 2^{n−4}}

+ \frac{(−1)^{n}(2n − 3)!}{120(n − 4)! 2^{n−4}} + \frac{(−1)^{n}(2n − 3)!}{144(n − 5)! 2^{n−5}} + \frac{(−1)^{n}(2n − 3)!}{1296(n − 6)! 2^{n−6}} ,

Ĝ_{4}(n) = \frac{(−1)^{n}(2n)!}{n! 2^{n}} + \frac{(−1)^{n}2(2n − 1)!}{3(n − 2)! 2^{n−2}} + \frac{(−1)^{n}(2n − 2)!}{4(n − 3)! 2^{n−3}} + \frac{(−1)^{n}(2n − 2)!}{12(n − 4)! 2^{n−4}}

+ \frac{(−1)^{n}(2n − 3)!}{30(n − 4)! 2^{n−4}} + \frac{(−1)^{n}(2n − 3)!}{36(n − 5)! 2^{n−5}} + \frac{(−1)^{n}(2n − 3)!}{324(n − 6)! 2^{n−6}}

+ \frac{(−1)^{n}(2n − 4)!}{720(n − 5)! 2^{n−5}} + \frac{(−1)^{n}13(2n − 4)!}{5760(n − 6)! 2^{n−6}} + \frac{(−1)^{n}(2n − 4)!}{1728(n − 7)! 2^{n−7}}

+ \frac{(−1)^{n}(2n − 4)!}{31104(n − 8)! 2^{n−8}} .

The first eight absolute values of each sequence are tabulated in Table 4. None of these sequences appear in the OEIS.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & OEIS # \\ |Ĝ_{1}(n)| & 1 & 4 & 25 & 210 & 2205 & 27720 & 405405 & 6756750 & — \\ |Ĝ_{2}(n)| & 1 & 5 & 36 & 340 & 3955 & 54495 & 866250 & 15585570 & — \\ |Ĝ_{3}(n)| & 1 & 6 & 48 & 496 & 6251 & 92638 & 1574650 & 30150120 & — \\ |Ĝ_{4}(n)| & 1 & 7 & 61 & 679 & 9150 & 144186 & 2594410 & 52390030 & — \end{matrix}

Table 4: The first eight values of Ĝ_{m}(n) for m = 1, 2, 3, 4.

5 Connections between the sums

Theorem 12 states that ĝ_{m}(n) = ∑_{j=0}^{m} \binom{m}{j}c^{∗}(2n − j, n − j). Together with Lemma 2 which implies c^{∗}(2n − j, n − j) = (−1)^{j}f̂_{j}(n), we immediately obtain the identity

ĝ_{m}(n) = ∑_{j=0}^{m}(−1)^{j}\binom{m}{j}f̂_{j}(n).

Likewise, we also have

Ĝ_{m}(n) = ∑_{j=0}^{m}(−1)^{j}\binom{m}{j}F̂_{j}(n).

Using the binomial inversion formula (see, for example, [1]), we also obtain

f̂_{m}(n) = ∑_{j=0}^{m}(−1)^{j}\binom{m}{j}ĝ_{j}(n),

F̂_{m}(n) = ∑_{j=0}^{m}(−1)^{j}\binom{m}{j}Ĝ_{j}(n).

Symbolically, we can apply the idea from umbral calculus [9] to abbreviate these results as

ĝ_{m}(n) = L((1 − f̂(n))^{m}),
Ĝ_{m}(n) = L((1 − F̂(n))^{m}),
f̂_{m}(n) = L((1 − ĝ(n))^{m}),
F̂_{m}(n) = L((1 − Ĝ(n))^{m}).

where L is the linear operator that maps t(n)^{j} to t_{j}(n).

6 Formulas for g_{m}(n) and G_{m}(n)

Let S_{1}(n, k) denote the sum of the \binom{n}{k} products composed of k distinct factors from [n], and S_{2}(n, k) the sum of the \binom{n−k+1}{k} possible products (repetition allowed) of k factors from [n]. It is obvious that

∑_{k=0}^{∞} S_{1}(n, k) x^{k} = ∏_{j=1}^{n}(1 + jx),  and  ∑_{k=0}^{∞} S_{2}(n, k) x^{k} = ∏_{j=1}^{n} \frac{1}{1 − jx}.

Comparing them to the well-known identities

∑_{k=0}^{∞} s(n, k) x^{k} = ∏_{j=0}^{n−1}(x − j),  and  ∑_{n=k}^{∞} S(n, k) x^{n} = ∏_{j=1}^{k} \frac{x}{1 − jx},

it is not difficult to see that

S_{1}(n, k) = (−1)^{k}s(n + 1, n + 1 − k),  (3)

and

S_{2}(n, k) = S(n + k, n).  (4)

Their equivalent forms also appear on [4, pages 71 and 72].

Gould obtained [3, Equation 1.9]

∑_{k=0}^{n} \binom{n − ℓ}{n + k}\binom{n + ℓ}{n − k}S_{1}(n + k − 1, n) = S_{2}(ℓ − n, n),

and proved the following identity [3, Equation 1.4] from [10]:

∑_{k=0}^{n} \binom{n − ℓ}{n + k}\binom{n + ℓ}{n − k}S_{2}(k, n) = S_{1}(ℓ − 1, n).

Applying (3) and (4) to them yields the identities

∑_{k=0}^{n} \binom{n − ℓ}{n + k}\binom{n + ℓ}{n − k}s(n + k, k) = (−1)^{n}S(ℓ, ℓ − n),

and

∑_{k=0}^{n} \binom{n − ℓ}{n + k}\binom{n + ℓ}{n − k}S(n + k, k) = (−1)^{n}s(ℓ, ℓ − n).

These are the two identities mentioned in the Introduction. Sun recently derived similar results [14, Theorem 2.3] that relate the Stirling numbers of the same kind. We note that his results are implied by those found in [3].

Setting ℓ = n + m leads to the next key result.

Lemma 14. The following identities

∑_{k=0}^{n} \binom{−m}{n + k}\binom{2n + m}{n − k}s(n + k, k) = (−1)^{n}S(n + m, m),  (5)

∑_{k=0}^{n} \binom{−m}{n + k}\binom{2n + m}{n − k}S(n + k, k) = (−1)^{n}s(n + m, m),  (6)

hold for all positive integers m.

Since \binom{−1}{n+k} = (−1)^{n+k}, S(n+1, 1) = 1, and s(n+1, 1) = (−1)^{n}n!, Lemma 14 immediately yields the formulas for g_{1}(n) and G_{1}(n).

Theorem 15. For all positive integers n,

g_{1}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n + 1}{n − k}s(n + k, k) = 1,

and

G_{1}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n + 1}{n − k}S(n + k, k) = (−1)^{n}n!.

For m > 1, the simplification becomes more complicated.

Theorem 16. For all positive integers n,

g_{2}(n) = ∑_{k=0}^{n}(−1)^{k}\binom{2n + 2}{n − k}s(n + k, k) = 2n + 3 − 2^{n+1}.

Proof. Since \binom{−2}{n+k} = (−1)^{n+k}(n + k + 1), and S(n + 2, 2) = 2^{n+1} − 1, we deduce from (5) that

∑_{k=0}^{n}(−1)^{k}(n + k + 1)\binom{2n + 2}{n − k}s(n + k, k) = 2^{k+1} − 1.

From (n + k + 2)\binom{2n+2}{n−k} = (2n + 2)\binom{2n+1}{n−k}, we obtain

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

Thus, we can further reduce the previous identity to

(2n + 2)g_{1}(n) − g_{2}(n) = 2^{n+1} − 1,

which completes the proof because g_{1}(n) = 1.

Encouraged by what we found, we used a computer algebra system to compute the value of g_{m}(n) for m = 1, 2, 3, 4, 5. This led us to the following conclusion:

Theorem 17. For any positive integer m,

g_{m}(n) = ∑_{j=1}^{m}(−1)^{j−1}\binom{2n + m}{m − j}S(n + j, j).

Proof. It follows from (5) that, for j ≥ 1,

S(n + j, j) = (−1)^{n} ∑_{k=0}^{n} \binom{−j}{n + k}\binom{2n + j}{n − k}s(n + k, k)

= ∑_{k=0}^{n}(−1)^{k}\binom{n + k + j − 1}{n + k}\binom{2n + j}{n − k}s(n + k, k).

Therefore,

∑_{j=1}^{m}(−1)^{j−1}\binom{2n + m}{m − j}S(n + j, j)

= ∑_{j=1}^{m}(−1)^{j−1}\binom{2n + m}{m − j} ∑_{k=0}^{n}(−1)^{k}\binom{n + k + j − 1}{n + k}\binom{2n + j}{n − k}s(n + k, k)

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

Using Vandermonde convolution (see, for example, [5, Equation 3.1]), the inner sum simplifies to

∑_{j=1}^{m}(−1)^{j−1}\binom{n + m + k}{m − j}\binom{n + k + j − 1}{n + k} = ∑_{j=1}^{m}(−1)^{j−1}\binom{n + m + k}{m − j}\binom{n + k + j − 1}{j − 1}

= ∑_{j=1}^{m} \binom{n + m + k}{m − j}\binom{−n − k − 1}{j − 1}

= \binom{m − 1}{m − 1},

from which the desired result follows.

When m = 1, 2, the formulas reduce to those in Theorems 15 and 16. We also find

g_{3}(n) = \binom{2n + 3}{2}S(n + 1, 1) − (2n + 3) S(n + 2, 2) + S(n + 3, 3).

Using an analogous argument, we obtain the following result.

Theorem 18. For any positive integer m,

G_{m}(n) = ∑_{j=1}^{m}(−1)^{j−1}\binom{2n + m}{m − j}s(n + j, j).

Accordingly,

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

While the similarity between the formulas for g_{m}(n) and G_{m}(n) is striking, there is an important difference between them. It is well-known (see, for example, [4, Equation 77]) that

S(n, k) = \frac{1}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}j^{n}.

This suggests that it is possible to find a closed form for g_{m}(n) without any reference to S(n, k). For example, after simplification,

g_{3}(n) = 2n^{2} + 7n + 4 − 2^{n+1}(2n − 5) − \frac{3^{n}}{2} .

The same cannot be said of G_{m}(n), because there does not exist a simple summation formula for s(n, k).

We invite interested readers to find alternative combinatorial and/or generating function proofs which provide closed forms for g_{m}(n) and G_{m}(n) for m > 0.

7 Acknowledgments

We would like to express our appreciation to the anonymous referee for his/her helpful comments and suggestions.

References

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

[2] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[3] H. W. Gould, Stirling number representation problems, Proc. Amer. Math. Soc. 11 (1960), 447–451.

[4] H. W. Gould, Topics in Combinatorics, Second Edition, Morgantown, WV, 2000.

[5] H. W. Gould, Combinatorial Identities, A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, Revised Edition, published by the author, Morgantown, WV, 1972.

[6] F. T. Howard, Associated Stirling numbers, Fibonacci Quart. 18 (1980), 303–315.

[7] M. Kauers and S.-L. Ko, Problem 11545, Amer. Math. Monthly 118 (2011), 84.

[8] J. Riordan, An Introduction to Combinatorial Analysis, John Wiley, 1958.

[9] S. M. Roman and G. C. Rota, The umbral calculus, Advances in Math. 27 (1978), 95–188.

[10] L. Schläfli, Sur les coefficients du développement du produit 1(1 + x)(1 + 2x) ⋯ (1 + (n − 1)x) suivant les puissance ascendantes de x, J. Reine Angew. Math. 43 (1852), 1–22.

[11] J. Simons and K. McInturff, Solutions to Problem 11545, Amer. Math. Monthly 119 (2012), 885–886.

[12] N. A. J. Sloane, The Online Encyclopedia of Integer Sequences, https://oeis.org.

[13] J. Stirling, Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum, 1730.

[14] Z.-H. Sun, Some inversion formulas and formulas for Stirling numbers, Graphs Combin. 29 (2013), 1087–1100.

[15] H. S. Wilf, generatingfunctionology, Academic Press, 1990.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 11B65, 05A10. Keywords: Stirling number of first kind, Stirling number of second kind, binomial coefficient.

(Concerned with sequences \underline{A000457}, \underline{A000497}, \underline{A000504}, \underline{A000906}, \underline{A000907}, \underline{A001784}, \underline{A001785}, and \underline{A051577}.)

Received June 25 2015; revised versions received August 14 2015; August 19 2015. Published in Journal of Integer Sequences, August 20 2015.

Return to Journal of Integer Sequences home page.