A sequence is defined as $f(n)=\sum_{i=0}^nC_n^i\cdot i^{n-i}$, where $C_n^i$ is the combination number choosing $i$ from $n$. I would like to know how does the limit of this sequence behave like. According to numerical computation, it is potentially exponential.
3
-
$\begingroup$ It is obviously faster than exponential. For asymptotics, the e.g.f. is $\displaystyle\sum_{n=0}^{\infty}\frac{f(n)}{n!}x^n = e^{xe^x}$ (to start). $\endgroup$– metamorphyCommented Aug 31, 2018 at 15:51
-
$\begingroup$ It will grow super-exponentially. The $i=n/2$ term grows like $\binom{n}{n/2} (n/2)^{n/2}\approx (2n)^{n/2}$. A good method would be to find the index $i(n)$ for which $a_i=\binom{n}ii^{n-i}$ is maximized. Then you get the estimate $a_{i(n)}\le (n)\le na_{i(n)}$, which is a great answer since the $n$ on the upper bound is small compared to $a_{i(n)}$. $\endgroup$– Mike EarnestCommented Aug 31, 2018 at 15:57
-
1$\begingroup$ This is A000248 in the OEIS and it's the exponential generating function for $\exp\big(x\,\exp(x)\big)$. It also counts the number of ways to partition $\{1,2,\dots,n\}$ and elect a representative for each part. To see this, in $$f(n) = \sum_{i=0}^n\,\binom ni i^{n-i}$$ we proceed as follows: first, we determine the number $i$ of classes in our partition. Next, we elect $i$ representatives, one for each class, from among the $n$ possiblities in $\binom ni$ ways. Finally, we assign each of the remaining $n-i$ elements to one of the $i$ classes. $\endgroup$– FimpellizzeriCommented Aug 31, 2018 at 15:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
According to $\text{A000248}$ there are asymptotics (Harris and Schoenfeld, 1968) given by
$$f(n) \sim \sqrt{\frac{r+1}{2\pi(n+1)(r^2+3r+1)}}\,\exp\left(\frac{n+1}{r+1}\right)\,\frac{n!}{r^n},$$
where $r$ is the root of $r(r+1)\exp(r) = n+1$.
answered Aug 31, 2018 at 16:04