ON THE PROBLEM OF UNIQUENESS FOR THE MAXIMUM STIRLING NUMBER(S) OF THE SECOND KIND

E. Rodney Canfield

Department of Computer Science, University of Georgia Athens, GA 30602 USA

                                erc@cs.uga.edu

Carl Pomerance

Fundamental Mathematics Department, Bell Laboratories/Lucent Technologies Murray Hill, NJ 07974-0636

                         carlp@research.bell-labs.com

Received: 9/10/01, Accepted: 1/15/02, Published: 1/16/02

Abstract

Say that an integer n is exceptional if the maximum Stirling number of the second kind S(n, k) occurs for two (of necessity consecutive) values of k. We prove that the number of exceptional integers less than or equal to x is O(x^{3/5+ϵ}), for any ϵ > 0.

1. Introduction

Let S(n, k) be the Stirling number of the second kind, that is, the number of partitions of an n-set into k non empty, pairwise disjoint blocks. (Detailed definitions appear in the next section.) Using the initial value S(0, k) = δ_{0 k} and the recursion

S(n + 1, k) = kS(n, k) + S(n, k − 1)  (1)

one may show by induction on n that

S(n, k)^{2} ≥ (1 + \frac{3}{k}) S(n, k − 1) S(n, k + 1), 1 ≤ k ≤ n.  (2)

It follows that the ratio S(n, k +1)/S(n, k) is strictly decreasing, and so there is either a unique maximum Stirling number

S(n, k) < S(n, K_{n}), for all k ≠ K_{n}

or else there are two consecutive peaks

S(n, k) < S(n, K_{n}) = S(n, K_{n} + 1), for all k ∉ {K_{n}, K_{n} + 1}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002), #A01 2

Define the exceptional set E to be those n for which the second alternative holds. Based on computation through n = 10^{6} reported in the final section, it is possible that E = {2}. Let E(x) denote the associated counting function

E(x) = #{n : n ≤ x and n ∈ E}.

The purpose of this paper is to prove

Theorem 1. For any ϵ > 0,

E(x) = O(x^{3/5+ϵ}).

Our proof of this theorem depends on the fact that, when n ∈ E, the quantity e^{r}, where r is the unique real solution of the equation re^{r} = n, must be unusually close to an integer plus 1/2. (See equation (5) in Section 3.) Starting from (5) and using only elementary arguments, we will prove in Section 4 a result slightly weaker than Theorem 1, namely with the exponent 3/5 replaced by 2/3. Then, in Section 5, we will prove Theorem 1 by invoking recent work of Huxley [9] on counting integer points near curves. In Section 6, we give a heuristic argument for why E should be a finite set. Finally, in Section 7, we report on the computation and supporting lemma that proves E ∩ (1, 10^{6}] = ∅.

2. Definitions and Background

A partition of the set [n] = {1, 2, …, n} is a collection of non empty pairwise disjoint subsets of [n], called blocks, whose union equals [n]. For example, {{1, 4}, {2, 3, 5, 7}, {6}} is a partition of [7] into 3 blocks. The Stirling number of the second kind, S(n, k), is the number of partitions of [n] into k blocks. Every partition of [n + 1] into k blocks can be obtained either by adjoining {n + 1} as a singleton block to an existing partition of [n] into k − 1 blocks, or by adding the element n+1 to one of the blocks of an existing partition of [n] into k blocks. This construction proves the recursion (1). Here is a table of the first few rows of the Stirling numbers of the second kind:

n\k  1 2 3 4 5
1  1
2  1 1
3  1 3 1
4  1 7 6 1
5  1 15 25 10 1

As explained in the Introduction, for each n ≥ 1 there is a unique integer K_{n} satisfying

S(n, 1) < ⋯ < S(n, K_{n}) ≥ S(n, K_{n} + 1).

In words, K_{n} is the location of the maximum Stirling number of the second kind, with the proviso that should there be two consecutive maxima, K_{n} is the location of the “leftmore.” The exceptional set E consists of n such that S(n, K_{n}) = S(n, K_{n} + 1), and E(x) is the number of n ≤ x belonging to E.

There is a vast literature on the Stirling numbers to which many people have contributed, and many properties have been independently rediscovered. Harper’s [6] contributions are particulary noteworthy. He shows that the polynomials ∑_{k} S(n, k)x^{k} have only real roots, a property called total positivity, which is stronger than log concavity. He articulates the uniqueor-double peak property (3), and proves the asymptotic relation K_{n} ∼ n/ log n, (His formula contains a superflous factor e which was later corrected.) The asymptotic formula was obtained by others, for example [18]. Citing Harper’s work, Lieb [13] derives an inequality similar to (2), based on the general Newton Inequality for coefficients of polynomials whose roots are all real and negative. The very nice fact that K_{n+1} equals either K_{n} or K_{n} + 1 appears in [4] and [16]. Using (1) and (2), it can be shown that a necessary condition for n ∈ E is K_{n+1} = K_{n} + 1. Thus, the growth condition K_{n+1} − K_{n} ∈ {0, 1} plus the asymptotic relation K_{n} ∼ n/ log n together imply that E(x) = O(x/ log x), as first pointed out by Wegner [19]. The latter paper of Wegner makes the explicit conjecture that E = {2}. Prior to the general adoption of more powerful analytic tools, in a series of papers [1, 8, 10, 11, 12] the authors Bach, Harborth, and Kanold employ clever elementary arguments to prove many interesting, sharp inequalities about K_{n}.

The fact that the signless Stirling numbers of the first kind do indeed have always a unique maximum is due to Erdős [5].

The status of the “duplicate maximum” problem has been misstated in the literature more than once. A source of misunderstanding might be the one line abstract, perpetuated in the Mathematical Reviews, of [4] which states, “For fixed n, Stirling numbers of the second kind, S(n, r), have a single maximum.” Reading the paper, one sees clearly that the intended meaning is precisely (3); but certainly the statement can be easily misconstrued when read in isolation.

Canfield [2] and Menon [14] independently showed that K_{n} is always equal to ⌊κ(n)⌋ or ⌈κ(n)⌉, where κ(n) is a certain transcendentally defined function. It will follow from what we say in Section 3 that for sufficiently large n a simpler definition of κ(n) also satisfies the latter theorem, namely κ(n) = e^{r} − 1, where re^{r} = n. Throughout the paper, we shall always use r(x) for the implicitly defined function

r(x)e^{r(x)} = x,

and the symbol r, with no argument, denotes r(n). For 1 ≤ n ≤ 1200 there is no exception to the relation

K_{n} ∈ {⌊e^{r} − 1⌋, ⌈e^{r} − 1⌉},  (4)

although it has been proven true only for n sufficiently large.

3. Asymptotics of the Stirling Numbers S(n, k)

We will neglect polylog factors in our estimates, and so it is convenient to define

F_{1}(x) = O_{∗}(F_{2}(x))

to mean that for a sufficiently large constant C we have

|F_{1}(x)| ≤ C(log x)^{C}F_{2}(x), for x ≥ C.

This given, we may state the lemma that will be of central importance.

Lemma 1. For all sufficiently large n ∈ E we have

e^{r} = ⌊e^{r}⌋ + \frac{1}{2} + \frac{1/2}{1 + r}

where as usual re^{r} = n.

Proof. The exponential generating function in the letter n for S(n, k) is [3]

∑_{n=k}^{∞} S(n, k)\frac{x^{n}}{n!} = \frac{(e^{x} − 1)^{k}}{k!} .

The Cauchy integral formula thus asserts

\frac{S(n, k)}{n!} = \frac{1}{2πik!} ∮_{|z|=R} \frac{(e^{z} − 1)^{k}}{z^{n+1}} dz,

for any R > 0. If we take the radius R of the circle of integration to be the quantity r, and restrict attention to integers k which satisfy the relations

e^{r} − 1 = k + θ, θ = O(1),

while making estimates such as those found in [15], we arrive at

S(n, k) = \frac{(e^{r} − 1)^{k}}{k!} \frac{n!}{r^{n}} (2πkB)^{−1/2}(1 − \frac{6r^{2}θ^{2} + 6rθ + 1}{12re^{r}})

where

B = B(r) = \frac{re^{2r} − (r^{2} + r)e^{r}}{(e^{r} − 1)^{2}}

depends on r only.

This is very similar to the formula (1) in [2], although the latter was unnecessarily conservative in the error estimate. Now, with k and θ as above, we find

\frac{S(n, k + 1)}{S(n, k)} = 1 + \frac{(r + 1)θ − \frac{1}{2}r − 1}{e^{r}} + O_{∗}(n^{−2}).

It is this equation which gives us the assertion (4), for all n large, mentioned earlier, and by setting the right side equal to 1, we obtain the lemma.

Remark. The asymptotic formula for S(n, k), and the more detailed one appearing in the proof of Lemma 2 in Section 6, are obtained by using the circle method. We do not include any details about how to use this method, which is a very standard and widely used technique for obtaining asymptotic estimates of the coefficients of analytic functions. The reader for whom this is a new topic should study [20, Section 4.5] before moving on to other papers. A very good account of the circle method particularly useful for asymptotic enumeration is [7]. The paper of Moser and Wyman [15] contains a lot of useful information about the particular case of the Stirling numbers. Another good source for this topic is [17].

4. The Elementary Proof

Our goal in this section is to prove that for any ϵ > 0

E(x) = O(x^{2/3+ϵ}).

Let ϵ > 0 be given. It suffices to show that for all sufficiently large X

|[X, X + X^{1/3−ϵ}] ∩ E| ≤ 2.  (6)

If (6) fails, then we have infinitely many n such that n, n + ℓ_{1}, n + ℓ_{2} ∈ E with 0 < ℓ_{1} < ℓ_{2} ≤ n^{1/3−ϵ}. For each such n, we have r with re^{r} = n, and also r_{i} with r_{i}e^{r_{i}} = n + ℓ_{i}. Note that

log x − log log x ≤ r(x) ≤ log x,

whence

r_{i} ∼ r.

Since r(x)e^{r(x)} = x, it follows that

e^{r_{i}} ∼ e^{r}.

By Taylor’s theorem and the facts that

\frac{d}{dx}e^{r(x)} = \frac{1}{r(x) + 1}, \frac{d^{2}}{dx^{2}} e^{r(x)} = \frac{−1}{(r(x) + 1)^{3}e^{r(x)}} , \frac{d^{3}}{dx^{3}} e^{r(x)} = \frac{r(x) + 4}{(r(x) + 1)^{5}e^{2r(x)}} ,

we have

\begin{aligned}e^{r_{i}} & = e^{r} + \frac{ℓ_{i}}{r + 1} \frac{1}{r_{i} + 1} \\ & = \frac{1}{r + 1} − \frac{ℓ_{i}}{(r + 1)^{3}e^{r}} \end{aligned}

Thus,

(ℓ_{1} − ℓ_{2})e^{r} + ℓ_{2}e^{r_{1}} − ℓ_{1}e^{r_{2}} = −\frac{ℓ_{2}ℓ_{1}^{2} − ℓ_{1}ℓ_{2}^{2}}{2(r + 1)^{3}e^{r}} + O_{∗}(\frac{ℓ_{2}ℓ_{1}^{3} + ℓ_{1}ℓ_{2}^{3}}{n^{2}} ).

Similarly,

\frac{ℓ_{1} − ℓ_{2}}{1 + r} + \frac{ℓ_{2}}{1 + r_{1}} − \frac{ℓ_{1}}{1 + r_{2}} = O_{∗}(\frac{ℓ_{2}ℓ_{1}^{2} + ℓ_{1}ℓ_{2}^{2}}{n^{2}} ).

Let us refer to the assertions of Lemma 1, namely,

e^{r_{i}} = m_{i} + 1/2 + \frac{1/2}{r_{i} + 1}

as equation i, with 0 ≤ i ≤ 2, taking r_{0} = r. If we form (ℓ_{1} − ℓ_{2}) times equation 0 plus ℓ_{2} times equation 1 minus ℓ_{1} times equation 2, and substitute the above expansions, we find

−\frac{ℓ_{2}ℓ_{1}^{2} − ℓ_{1}ℓ_{2}^{2}}{2(r + 1)^{3}e^{r}} + O_{∗}(\frac{ℓ_{2}ℓ_{1}^{3} + ℓ_{1}ℓ_{2}^{3}}{n^{2}} ) = INTEGER + O_{∗}(\frac{ℓ_{2}ℓ_{1}^{2} + ℓ_{1}ℓ_{2}^{2}}{n^{2}} ).

In the previous equation, every term except the one labeled “INTEGER” goes to 0 as n → ∞; thus, for all sufficiently large n that term itself must be 0. Dividing through by ℓ_{1}ℓ_{2} and collecting big-oh’s,

\frac{ℓ_{2} − ℓ_{1}}{2(r + 1)^{3}e^{r}} = O_{∗}(\frac{ℓ_{1}^{2} + ℓ_{2}^{2}}{n^{2}} ).

Since, however, ℓ_{2} − ℓ_{1} ≥ 1, this last equality is impossible. Our initial assumption that (6) does not hold is contradicted, and the proof is complete.

5. The Proof of Theorem 1

The theorem due to Huxley which we shall apply, [9, (1.7)], bounds the number of integer pairs (n, m) which satisfy |m − f(n)| ≤ δ for n ∈ [X, 2X]. We shall apply this result to the function

f(x) = e^{r(x)} − 1/2 − \frac{1/2}{1 + r(x)},

with δ = X^{ϵ−1}. With these choices, by Lemma 1, for X sufficiently large, we include all members of E ∩ [X, 2X] in the count.

The hypotheses required of f(x) are that there be numbers C ≥ 1, Δ < 1 such that

CΔ ≤ 1

\frac{Δ}{C} ≤ |f′′(x)| ≤ CΔ, x ∈ [X, 2X]

and

|f^{(3)}(x)| ≤ \frac{CΔ}{X}, x ∈ [X, 2X].

The conclusion of Huxley’s theorem is that the number of integer pairs (n, m) is no greater than an unspecified constant times

1 + \frac{1}{b}\sqrt{\frac{Cδ}{Δ}} + C^{2}δX(log X − log 2C)^{c_{i}}δ^{d_{i}},

where b is the least positive integer such that for some x ∈ [X, 2X] we have bf′(x) within distance δ of an integer, and the exponents (a_{i}, b_{i}, c_{i}, d_{i}) in the sum assume the four values (\frac{2}{5}, 1, \frac{1}{10}, 0), (\frac{1}{5}, \frac{4}{5}, \frac{1}{10}, 0), (\frac{2}{7}, 1, \frac{1}{7}, \frac{1}{7}), and (\frac{1}{7}, \frac{6}{7}, \frac{1}{7}, \frac{1}{7}).

If we take Δ = X^{−1}, then the quantity C satisfying the hypotheses of Huxley’s Theorem may be taken as O(X^{ϵ}), and we obtain the result that between X and 2X there are O(X^{3/5+ϵ}) elements of E. This estimate suffices to prove the Theorem. (By being a bit more careful, one may use Huxley’s Theorem to show that the number of members of E up to X is at most X^{3/5}(log X)^{O(1)}.)

6. A Heuristic

In this section we give a strengthening of Lemma 1 that leads to a heuristic argument that the set E is finite. Note that already the estimate of Lemma 1 heuristically supports the conclusion that E(x) = O(x^{ϵ}), and with more care, E(x) ≤ (log x)^{O(1)}. To push this heuristic further we need a more precise version of Lemma 1.

Lemma 2. For n ∈ E and re^{r} = n, we have

e^{r} = ⌊e^{r}⌋ + \frac{1}{2} + \frac{1/2}{1 + r} + \frac{A_{r}}{e^{r}} + O_{∗} (n^{−2}) ,

where A_{r} is a rational function in r with rational coefficients.

Proof. With the same meaning for k, θ, B as in the proof of Lemma 1, it is possible to show that uniformly for |θ| = O(1), we have

S(n, k) = \frac{(e^{r} − 1)^{k}}{k!} \frac{n!}{r^{n}} (2πkB)^{−1/2} (1 − \frac{F_{1}}{e^{r}} + \frac{F_{2}}{e^{2r}} + O(\frac{r^{3}}{e^{3r}} )),

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002), #A01 8

where

F_{1}(θ) = \frac{1 + 6rθ + 6r^{2}θ^{2}}{12r} ,
F_{2}(θ) = \frac{1}{288r^{2}} (r^{4}(−36 − 144θ − 144θ^{2} + 36θ^{4})
+ r^{3}(96 + 144θ − 288θ^{2} − 24θ^{3}) + r^{2}(−144θ − 24θ^{2})

Returning to the proof, it follows from the above formula that

\frac{S(n, k + 1)}{S(n, k)} = \frac{e^{r} − 1}{k + 1}(\frac{k}{k + 1})^{1/2}(\frac{1 − F_{1}(θ − 1)e^{−r} + F_{2}(θ − 1)e^{−2r}}{1 − F_{1}(θ)e^{−r} + F_{2}(θ)e^{−2r}} + O_{∗} (n^{−3})). (7)

Suppose now that n ∈ E, so that S(n, k + 1)/S(n, k) = 1. Write

θ = u + \frac{1}{2} + \frac{1/2}{r + 1},

so that Lemma 1 implies that u = O_{∗}(n^{−1}). Hence, if g(x, y) ∈ Q[x, y], then

g(r, θ) = g(r, \frac{1}{2} + \frac{1/2}{r + 1}) + O_{∗} (n^{−1}) .

Thus,

\frac{e^{r} − 1}{k + 1} = \frac{e^{r} − 1}{e^{r} − θ} = 1 + \frac{θ − 1}{e^{r}} + \frac{θ^{2} − θ}{e^{2r}} + O_{∗} (n^{−3}) = 1 + \frac{θ − 1}{e^{r}} + \frac{a_{r}}{e^{2r}} + O_{∗} (n^{−3}) ,

where a_{r} is a rational function of r with rational coefficients. Also

(\frac{k}{k + 1})^{1/2} = 1 − \frac{1/2}{e^{r}} + \frac{1/8 − θ/2}{e^{2r}} + O_{∗} (n^{−3}) = 1 − \frac{1/2}{e^{r}} + \frac{b_{r}}{e^{2r}} + O_{∗} (n^{−3}) ,

where again, b_{r} is in Q(r). And

\frac{1 − F_{1}(θ − 1)e^{−r} + F_{2}(θ − 1)e^{−2r}}{1 − F_{1}(θ)e^{−r} + F_{2}(θ)e^{−2r}} =

1 − \frac{F_{1}(θ − 1) − F_{1}(θ)}{e^{r}} + \frac{F_{2}(θ − 1) − F_{2}(θ) + (F_{1}(θ − 1) − F_{1}(θ))F_{1}(θ)}{e^{2r}} + O_{∗} (n^{−3})

= 1 + \frac{1/2 − r/2 + rθ}{e^{r}} + \frac{c_{r}}{e^{2r}} + O_{∗} (n^{−3}) ,

where c_{r} ∈ Q(r).

Thus (7) and the above estimates imply that

1 = (1 + \frac{θ − 1}{e^{r}} + \frac{a_{r}}{e^{2r}} )(1 − \frac{1/2}{e^{r}} + \frac{b_{r}}{e^{2r}} )(1 + \frac{1/2 − r/2 + rθ}{e^{r}} + \frac{c_{r}}{e^{2r}} ) + O_{∗} (n^{−3}) .

Subtracting 1 from both sides and multiplying by e^{r}, we get

(r + 1)θ − \frac{1}{2} − \frac{1}{2}(r + 1)
= − e^{−r} (a_{r} + b_{r} + c_{r} − \frac{1}{2}(θ − 1) + (θ − \frac{3}{2})(\frac{1}{2} − \frac{1}{2}r + rθ))
= d_{r}e^{−r} + O_{∗} (n^{−2}) ,

where d_{r} ∈ Q(r). Thus, we have Lemma 2.

We now give a heuristic argument, based on Lemma 2, that the set E is finite. With re^{r} = x, let

g(x) = e^{r} − \frac{1}{2} − \frac{1/2}{r + 1} − \frac{A_{r}}{e^{r}} = \frac{x}{r} − \frac{1}{2} − \frac{1/2}{r + 1} − \frac{rA_{r}}{x} .

The function g(x) is smooth with

g′(x) ∼ \frac{1}{log x}, g′′(x) ∼ \frac{−1}{x log^{2} x}, g^{(3)}(x) ∼ \frac{1}{x^{2} log^{2} x}.

There is no reason to believe that g(n) has a prediliction to be close to an integer over any other transcendental number. But Lemma 2 implies that for n ∈ E, we have ∥g(n)∥ = O_{∗}(n^{−2}), where ∥ ∥ denotes the distance to the nearest integer. Heuristically, the number of such integers n is ∑ O_{∗}(n^{−2}) = O(1). (One might view the expression O_{∗}(n^{−2}) as an upper bound for the “probability” that n ∈ E, and the sum of these probabilities is O(1).)

7. Numerics

To verify that E ∩ (1, 10^{6}] = ∅, we wrote a program to compute S(n, k) mod 2^{31} − 1. We computed all such residues for 2 ≤ n ≤ 10^{6} and 2 ≤ k ≤ min{87890, n}, finding 33 pairs (n, k) satisfying the conditions:

2 ≤ n ≤ 10^{6}
2 ≤ k < min{87890, 2n/ log(n), n}
S(n, k) = S(n, k + 1) mod 2^{31} − 1.

We may impose the stated bounds on k for these reasons: (1) by Lemma 3, stated and proven below, K_{n} < 2n/ log(n) for n ≥ 151; (2) an independent computation of exact values of S(n, k), using maple, had already shown E ∩ (1, 1200] = ∅; (3) S(10^{6}, 87848) > S(10^{6}, 87890).

The third of these facts was established by making rigorous numerical estimates, with considerable help from maple. The basis for these estimates is the pair of inequalities

\frac{k^{n}}{k!} ∑_{j=0}^{O} \binom{k}{j}(−1)^{j}(1 − j/k)^{n} ≤ S(n, k) ≤ \frac{k^{n}}{k!} ∑_{j=0}^{E} \binom{k}{j}(−1)^{j}(1 − j/k)^{n}  (8)

for any positive odd integer O and nonnegative even integer E. These are the Bonferroni inequalities ([3], Section 4.7 ). We used O = 5 and E = 4 to prove

\begin{aligned}log S(10^{6}, 87848) & > 10 471 198 \\ log S(10^{6}, 87890) & < 10 471 197.992 \end{aligned}

Later, by taking E = 10 and O = 11 we were able to show conclusively that

K_{10^{6}} = 87846.

For anyone wishing to duplicate the computation, we provide these checkpoints:

• the first of the 33 pairs is (n, k) = (124322, 16581)

• the last of the 33 pairs is (n, k) = (965756, 12911)

• S(10^{6}, 87890) = 1111899618 mod 2^{31} − 1

• S(124322, 16581) = 1636672468 mod 2^{31} − 1

• S(965756, 12911) = 897942184 mod 2^{31} − 1

The program was modified to compute S(n, k) mod 2^{19} − 1, and run a second time. This second modulus was able to distinguish 31 of the pairs found in the first run; for example,

S(124322, 16581) = 31493 mod 2^{19} − 1 and S(124322, 16582) = 504717 mod 2^{19} − 1.

However, all four of the numbers S(n, k) for n = 526314, k = 51889, 51890 and n = 559358, k = 52358, 52359 are 0 mod 2^{19} − 1. To distinguish among these a further calculation was needed. Note that the bounds given in equation (8) are in fact equalities if E, or as appropriate O, is equal to k. For a prime p > k this provides a way to compute S(n, k) mod p directly, without computing any other Stirling numbers in the process. This identity shows, as shown in [19, (4.1)], that S(n, k) ≡ S(A, k) mod p for prime p > k and n ≡ A ≢ 0 mod (p − 1). For the first few primes p larger than k, we have 0 < A < k, so for these primes S(n, k) is congruent to 0. The first prime larger than 51889 for which S(526314, 51889) is not congruent to 0 is p = 52639. We have

S(526314, 51889) = 4890 mod 52639, and S(526314, 51890) = 43718 mod 52639.

In a similar manner, the pair for n = 559358 is distinguished by the prime p = 55949. In this way, then, we prove there are no duplicate maxima for 1 < n ≤ 10^{6}.

We now conclude with the above referenced lemma.

Lemma 3. For all integers n ≥ 151 we have K_{n} < 2n/ log n.

Proof. For any positive integer k with 1 ≤ k ≤ n, we have

\frac{k^{n}}{k!} − \frac{(k − 1)^{n}}{(k − 1)!} ≤ S(n, k) ≤ \frac{k^{n}}{k!} .  (9)

These inequalities are the case E = 0 and O = 1 of equation (8). We include a from-scratch proof since it is not difficult. Indeed, the number of assignments of the integers 1, …, n into k labeled boxes with no box remaining empty is at most k^{n}, and each set partition of [n] corresponds to k! such assignments. Thus, we have the upper bound in (9). Further, the number of assignments without the restriction that no box remain empty is exactly k^{n}, and the number of assignments where box i remains empty is exactly (k − 1)^{n}. Thus, the number of assignments with no box remaining empty is at least k^{n} − k(k − 1)^{n}. From this, the lower bound in (9) follows easily.

We now let k = ⌊n/ log n⌋. We will show that for n ≥ 151,

\frac{(2k)^{n}}{(2k)!} < \frac{k^{n}}{k!} − \frac{(k − 1)^{n}}{(k − 1)!} .  (10)

Note that (9) and (10) show that S(n, k) > S(n, 2k), and so from (3), we must have K_{n} < 2k. To see (10), let

α = \frac{(2k)^{n}/(2k)!}{k^{n}/k!}, β = \frac{(k − 1)^{n}/(k − 1)!}{k^{n}/k!}.

We will show that for n ≥ 151 we have α, β < 1/2, so that (10) follows for these values of n.

We have

β = k(1 − 1/k)^{n} ≤ ke^{−n/k} = ⌊n/ log n⌋e^{−n/⌊n/ log n⌋}
≤ (n/ log n)e^{− log n} = 1/ log n.

Thus, for n ≥ 151, we have β ≤ 1/ log 151 < 1/5. The estimation for α is a little more difficult. We have

α^{−1} = \frac{(2k)!}{k!}2^{−n} = k!\binom{2k}{k}2^{−n}.

Using the inequalities k! > (k/e)^{k}, \binom{2k}{k} ≥ 2^{2k}/(2k), which are both easy to see, we have

α^{−1} > k^{k−1}e^{−k}2^{2k−1−n},

so that

log(α^{−1}) > (k − 1)(log k + log 4 − 1) − ((n − 1) log 2 + 1).

An elementary check shows that this last expression exceeds 1 for all integers n ≥ 151, so that α < 1/e in this range. This completes the proof of (10) and the lemma.

References

1. Bach, Günter, Über eine Verallgemeinerung der Differenzengleichung der Stirlingschen Zahlen 2 Art und Einige damit zusammenhngende Fragen, J. Reine Angew. Math. 233 (1968) 213–220.

2. Canfield, E. R., Location of the maximum Stirling number(s) of the second kind, Studies in Appl. Math. 59 (1978) 83–93.

3. Comtet, Louis, Advanced Combinatorics; The art of finite and infinite expansions, Reidel, Boston, 1974.

4. Dobson, A. J., A note on Stirling numbers of the second kind, J. Combinatorial Theory 5 (1968) 212–214.

5. Erdős, Paul, On a conjecture of Hammersley, Journal of the London Mathematical Society 28 (1953) 232–236.

8. Harborth, Heiko, Über das Maximum bei Stirlingschen Zahlen 2. Art, J. Reine Angew. Math. 230 (1968) 213–214.

6. Harper, L. H., Stirling behavior is asymptotically normal, Ann. Math. Stat. 31 (1967) 410–414.

7. Hayman, Walter K., A generalisation of Stirling’s formula, Journal für die reine und angewandte Mathematik 196 (1956) 67–95.

9. Huxley, M. N., The integer points close to a curve, III, in Number Theory in Progress (K. Győry, H. Iwaniec, and J. Urbanowicz, editors), Walter de Gruyter, Berlin, 1999, pages 911–940.

10. Kanold, Hans-Joachim, Über Stirlingsche Zahlen 2. Art, J. Reine Angew. Math. 229 (1968) 188–193.

11. Kanold, Hans-Joachim, Über eine asymptotische Abschätzung bei Stirlingschen Zahlen 2. Art, J. Reine Angew. Math. 230 (1968) 211–212.

12. Kanold, Hans-Joachim, Einige neuere Abschtzungen bei Stirlingschen Zahlen 2. Art, J. Reine Angew. Math. 238 (1969) 148–160.

13. Lieb, E. H., Concavity properties and a generating function for Stirling numbers, J. Combinatorial Theory 5 (1968) 203–206.

14. Menon, V. V., On the maximum of Stirling numbers of the second kind, J. Combinatorial Theory, A 15 (1973) 11–24.

15. Moser, L. and M. Wyman, Stirling numbers of the second kind, Duke Math. J. 25 (1957) 29–43.

16. Mullin, R., On Rota’s problem concerning partitions, Aequationes Mathematicae 2 (1969) 98–104.

17. Odlyzko, Andrew, Asymptotic enumeration methods, in Handbook of Combinatorics, volume II (R. L. Graham, M. Grötschel, L. Lovász, editors), The MIT Press, North-Holland, 1995, pages 1063–1229.

18. Rennie, B. C., and A. J. Dobson, On Stirling numbers of the second kind, J. Combinatorial Theory 7 (1969) 116–121.

19. Wegner, Horst, Über das Maximum bei Stirlingschen Zahlen zweiter Art, J. Reine Angew. Math. 262/263 (1973) 134–143.

20. Wilf, Herbert S., Generatingfunctionology, Academic Press, San Diego, 1990.