2

I'm looking for an asymptotic approximation of $\prod_{k=1}^nk^\binom{n}{k}$ in order to get a better impression of its growth rate. Does anyone know how to deal with the given product? Any hints are appreciated.

MaxWell
  • 319
  • 1
    A very rough estimate: $\prod_{k=1}^nk^{n\choose k}\le\prod_{k=1}^nn^{n\choose k}=n^{\sum_{k=1}^n{n\choose k}}=n^{2^n-1}$. I am pretty sure that this can be improved, but the question is - does it do the work for you? –  Jan 11 '18 at 19:04
  • 2
    Are sure sure the product starts at $k=0$? – Jack D'Aurizio Jan 11 '18 at 19:04
  • @JackD'Aurizio Thank's for that hint. You're right. It should be start with $k=1$ of course. I've updated my question. – MaxWell Jan 11 '18 at 19:06
  • 1
    Take the logarithm. Note that $\log k$ is quite close to $\log n$ for most of the $k$. – Daniel Fischer Jan 11 '18 at 19:16

2 Answers2

3

The given product equals

$$\begin{eqnarray*} \exp\sum_{k=1}^{n}\binom{n}{k}\log k&=&\exp\sum_{k=1}^{n}\binom{n}{k}\int_{0}^{+\infty}\frac{e^{-x}-e^{-kx}}{x}\,dx\\ &=& \exp\int_{0}^{+\infty}\left[1+(2^n-1)e^{-x}-(1+e^{-x})^n\right]\,\frac{dx}{x}\end{eqnarray*}$$ by Frullani's theorem, and the last integral can be estimated through Laplace's method.
A crude approximation is given by $$ \prod_{k=1}^{n}k^{\binom{n}{k}}\approx \exp\left(\frac{2^{n+1}(n-2)^2}{n(n+1)}\right) $$ for any $n\gg 2$.

Jack D'Aurizio
  • 353,855
  • are you sure the given products equal ? I can be totally wrong, but I would expect on his expression to see $\log(k)^{n-k}$ and since the exponents are missing once took logarithm ... I may be doing something wrong... – abr Jan 11 '18 at 19:27
  • @abr: $k^{\binom{n}{k}}=\exp\left[\binom{n}{k}\log k\right]$, where the $\log(k)^{n-k}$ term should come from? – Jack D'Aurizio Jan 11 '18 at 19:29
  • I got, it you are totally right :) Sorry for the misunderstanding. – abr Jan 11 '18 at 19:34
  • This is a nice calculation indeed. – Antonio Vargas Feb 15 '18 at 23:38
0

What about:

$\prod\limits_{k=1}^{n}{k^{{n\choose k}}} = x$

Taking $\log$ to both sides:

$\sum\limits_{k=1}^{n}{ {n\choose k} \log{k}} = \log{x}$

Reshaping by binomial theorem, assuming $n>3$ to be sure $\log(n) > 1$:

$\sum\limits_{k=1}^{n}{ {n\choose k} \log{k}} = \log{x} < (1+\log{n})^n$

Taking exponential back:

$x<e^{ \big((1+\log{n})^n -1\big)}, n>3$

O Bounding:

$x = O\big(e^{ ((1+\log{n})^n)}\big), n >3$

abr
  • 436