I am trying to upper bound the following sum:
$\sum_{k=1}^{n/2} \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}.$
Based on numerical computations, it seems like the upper bound is a constant (there is also another complicated proof that suggested the upper bound should be a constant). Any idea how to prove this? Stirling's approximation does not seem to help: using Stirling's (in a loose way) I can show that the sum is $O(log n)$.
A related bound that would imply the bound on the above sum is to show that
$ \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}} \leq \frac{c}{k^2}$
for some constant $c$.
Thanks!