使$k^n/k!$最大的$k$

hbghlyj

The greatest term in Dobiński's formula

Question. Find the greatest term in Dobiński's formula; let $k_{0}$ denote the value of $k$ that maximizes $k^{n} / k !$.
Let $x=\lambda(n)$ be defined by the equation $x \ln x=n$.
Claim. $\left|k_{0}-\lambda(n)\right|<1$.
In other words, $k_{0}$ is either $\lfloor\lambda(n)\rfloor$ or $\lceil\lambda(n)\rceil$.
We prepare the proof with an estimate.
Lemma.
$$
\frac{1}{k}>\ln (k+1)-\ln (k)>\frac{1}{k+1} .
$$
Proof. Both inequalities follow from the identity
$$
\ln (k+1)-\ln (k)=\int_{k}^{k+1} \frac{d t}{t} .
$$$\square$
Proof of the Claim. Let $f(k)=k^{n} / k !$. Let $\ell=\lfloor\lambda(n)\rfloor$, so we have $\ell \leq$ $\lambda(n)<\ell+1$. We shall show that $k_{0} \in\{\ell, \ell+1\}$. This will follow from the following two statements.
(a) If $k \leq \ell-1$ then $f(k)<f(k+1)$.
(b) If $k \geq \ell+1$ then $f(k)>f(k+1)$
We need to study the quantity
$$
\frac{f(k+1)}{f(k)}=\frac{(k+1)^{n}}{(k+1) !} \cdot \frac{k !}{k^{n}}=\frac{(k+1)^{n-1}}{k^{n}}\tag1
$$
Let
$$
g(k)=\ln \left(\frac{f(k+1)}{f(k)}\right)=(n-1) \ln (k+1)-n \ln k .\tag2
$$
We need to show that
(a) if $k \leq \ell-1$ then $g(k)>0$, and
(b) if $k \geq \ell+1$ then $g(k)<0$.
Proof of statement (a). We restate the inequality $g(k)>0$ :
$$
(n-1) \ln (k+1)>n \ln k,\tag3
$$
or equivalently,
$$
\frac{\ln (k+1)}{\ln k}>\frac{n}{n-1} .\tag4
$$
Subtracting 1 from each side, this is equivalent to
$$
\frac{\ln (k+1)-\ln k}{\ln k}>\frac{1}{n-1} .\tag5
$$
By the Lemma, we have $\ln (k+1)-\ln k>1 /(k+1)$, so for Eq. (5) to hold, it suffices if
$$\frac{1}{(k+1) \ln k} \geq \frac{1}{n-1}\tag6$$
in other words,
$$
(k+1) \ln k \leq n-1\tag7
$$
So we need to show that if $k \leq \ell-1$ then Eq. (7) holds. But in this case $(k+1) \ln k \leq \ell \ln (\ell-1)=\ell \ln (\ell)-\ell(\ln (\ell)-\ln (\ell-1))<n-\ell(\ln (\ell)-\ln (\ell-1))<$ $n-1$. In the last step we used that $\ln (\ell)-\ln (\ell-1)>1 / \ell$ (see the Lemma). This completes the proof of statement (a).
Proof of statement (b). We need to show that if $k \geq \ell+1$ then $g(k)<0$, i. e.,
$$
(n-1) \ln (k+1)<n \ln k .\tag8
$$
As above (see Eq. (5)), this is equivalent to
$$
\frac{\ln (k+1)-\ln k}{\ln k}<\frac{1}{n-1} .\tag9
$$
By the Lemma, we have $\ln (k+1)-\ln k<1 / k$, so for Eq. (9) to hold, it suffices if
$$
\frac{1}{k \ln k}<\frac{1}{n-1}\tag{10}
$$
in other words,
$$k \ln k > n − 1.\tag{11}$$
In fact, by definition, $k \ln k ≥ (\ell+ 1) \ln(\ell+ 1) > n$.$\square$

战巡

回复 1# hbghlyj

\[\frac{d}{dk}\frac{k^n}{\Gamma(k+1)}=\frac{k^{n-1}}{k!}(n-k\psi(k+1))\]
其中$\psi(x)=\frac{d}{dx}\ln(\Gamma(x))$为双伽马函数

那它的极值点在$n=k\psi(k+1)$取到，注意到双伽马函数有
\[\psi(x)\approx\ln(x)-\frac{1}{2x}\]
因此这个解近似为
\[n\approx k\ln(k+1)-\frac{k}{2(k+1)}\]

hbghlyj

The Art of Mathematics: Coffee Time in Memphis, page 12

51. Bell Numbers. The $n$th Bell number $B_{n}$ is the number of (unordered) partitions of $[n]=\{1,2, \ldots, n\}$. Thus $B_{1}=1, B_{2}=2, B_{3}=5$ and $B_{4}=15$. For example, the set $[3]=\{1,2,3\}$ has the following five partitions: $\{123\},\{12,3\}$, $\{13,2\},\{23,1\}$ and $\{1,2,3\}$. Show that
$$
B_{n}=\left[\frac{1}{e} \sum_{k=1}^{2 n} \frac{k^{n}}{n !}\right\rceil
$$

hbghlyj

回复 3# hbghlyj
en.wikipedia.org/wiki/Dobiński's_formula#Reduced_formula

The computation of the sum of Dobiński's series can be reduced to a finite sum of  $n+o(n)$  terms, taking into account the information  that $B_n$ is an integer. Precisely one has, for any integer $K > 1$
$$B_n = \left\lceil {1 \over e}\sum_{k=0}^{K-1}\frac{k^n}{k!}\right\rceil$$
provided $\frac{K^n}{K!}\le 1$ (a condition that of course implies $K > n$, but that is satisfied by some $K$ of size $n+o(n)$). Indeed, since $K > n$, one has
$$\Big(\frac{K+j}K\Big)^n\le\Big(\frac{K+j}K\Big)^K=\Big(1+\frac jK\Big)^K \le \Big(1+\frac j1\Big)\Big(1+\frac j2\Big)\dots\Big(1+\frac jK\Big)=\frac{1+j}1 \frac{2+j}2 \dots  \frac{K+j}K=\frac{(K+j)!}{K!j!}.$$
Therefore $\frac{(K+j)^n}{(K+j)!}\le \frac{K^n}{K!}\frac 1{j!} \le \frac1{j!}$ for all  $j \ge0$
so that the tail $\sum_{k\ge K} \frac{k^n}{k!}=\sum_{j\ge 0} \frac{(K+j)^n}{(K+j)!}$ is dominated by the series $\sum_{j\ge 0} \frac{1}{j!}=e$, which implies $0 < B_n - \frac1{e}\sum_{k=0}^{K-1}\frac{k^n}{k!}<1$, whence the reduced formula.