Of course, I can use Stirling's approximation, but for me it is quite interesting, that, if we define $k = (n-1)!$, then the left function will be $(nk)!$, and the right one will be $k! k^{n!}$. I don't think that it is a coincidence. It seems, that there should be smarter solution for this, other than Stirling's approximation.
Asked
Active
Viewed 568 times
7
-
You don't think "what" is a coincidence? – GeoffDS Oct 09 '12 at 14:09
-
I cannot explicitely explain why did I say so. Probably, I just wanted to point that it seems that there should be smarter solution others than Stirling's approximation. But, of course, I can be wrong. – Kos Oct 09 '12 at 14:22
2 Answers
3
For $(nk)!$ your factors are $1,2,3,\dots, k$ then $k+1, \dots, 2k,2k+1 \dots, k!$.
For $k! k^{n!}$ your factors are $1,2,3,\dots, k$ but then constant $k,\dots,k$.
So every factor of (nk)! is > or = to each factor of k!k^(n!)
cactus314
- 24,438
-
-
1But total numher of factors in the first function is $n!$, while in the second it is $k+n!$, so it has extra $k$ factors, each equals to $k$ – Kos Oct 10 '12 at 07:24
0
Take $\log$ on both sides and use the $\log {n!} = \Theta(n\log n)$. The first terms becomes $\Theta(n!\log{(n!)})$, the second one becomes $\Theta((n-1)!\log {(n-1)!}) + \Theta(n!\log{(n-1)!})$. So it's obvious that the first terms grows faster than the second one.
platinor
- 101
-
It might be useful to expand on this answer a little bit. In particular, it's not immediately clear to me why there's an asymptotic gap between $n! log(n!)$ and $n! \log((n-1)!)$. – Micah Sep 05 '13 at 21:05
-
$n!\log(n!) - n!\log{(n-1)!} = n!(\log{n!} - \log{(n-1)!}) = n!(\log{n})$ – platinor Sep 06 '13 at 21:10
-
That looks an awful lot like a proof that $n! log(n!)$ is $\Theta(n!(\log(n-1)!))$ to me (since $n! \log n$ grows more slowly than either of the other two terms). It looks to me like you need sharper asymptotics than $\Theta$-notation gives you, which leads back towards Stirling's approximation... – Micah Sep 06 '13 at 21:26