When $\frac{C(n, k)}{n^{k-1}} > 1$? I came across this while considering the subset sum problem in relation to another problem. Define the ratio,
$$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$
and the integer sequence,
$$s_k = k!+\frac{k(k-1)}{2} = k!+C(k,2)$$
where $C(k,2)$ yield the triangular numbers. How do we show that,
$$\begin{aligned}
R\big(n,\,k\big)\; &< 1,\quad\text{if}\;n < s_k\\
R\big(n,\,k\big)\; &\geq 1,\quad\text{if}\;n \geq s_k
\end{aligned}$$ 
For example, let $k=6$ so $s_6 = 735$, then,
$$\begin{aligned}
R\big(734,\,6\big)\; &= 0.99877\dots\\
R\big(735,\,6\big)\; &= 1.00016\dots
\end{aligned}$$ 
 A: Here's an outline of a solution.  Fix $k$; we seek the unique (possibly non-integral) $n>k$ such that ${n\choose k}=n^{k-1}$.  Expanding the left-hand side, we have
$$ n^k - {k\choose 2}n^{k-1} + {\rm error} = k!\, n^{k-1}$$
If the error term weren't there, this would give $n = k! + {k\choose 2}$.  We'll show that the error is between zero and $n^{k-1}$.
To do this, we have to look more closely at the polynomial
$$n(n-1)\cdots(n-k+1) = n^k - c_1 n^{k-1} + c_2 n^{k-2} - \cdots$$
where $c_r$ is the sum of the products of all $r$-subsets of $\{0,\ldots,k-1\}$.
It's easy to see that for each $r$, we have
$c_r < k^2 c_{r-1}$; this is because each $(r-1)$-subset can be extended to an $r$-subset
in less than $k$ ways, and each such extension increases the product by less than $k$.
We'll assume $k>6$, so that $k^4<k!<n$. Then $c_r < k^2 c_{r-1} < n c_{r-1}$, so that
$n^k - c_1 n^{k-1} + c_2 n^{k-2} -\cdots$ is an alternating sum of terms whose absolute value decreases.  Thus we have
$$n^k - c_1 n^{k-1} < n(n-1)\cdots(n-k+1) < n^k - c_1 n^{k-1} + c_2 n^{k-2}$$
We have $c_1={k\choose 2}$ and $c_2< k^2{k\choose2}<k^4 < n$, so we get
$$n^k - c_1 n^{k-1} < n(n-1)\cdots(n-k+1) < n^k - c_1 n^{k-1} + n^{k-1},$$
i.e. the "error" is sandwiched between $0$ and $n^{k-1}$ as claimed.
To see that this finishes the argument, recall that we chose $n$ in order that ${n\choose k}=n^{k-1}$.  So $n(n-1)\cdots(n-k+1)=k!n^{k-1}$, so the "sandwiching" inequality says
$$n^k - c_1 n^{k-1} < k! n^{k-1} < n^k - c_1 n^{k-1} + n^{k-1}.$$
Dividing all 3 sides by $n^{k-1}$, and adding $c_1={k\choose 2}$ to all 3 sides, this gives
$$n < k! + {k\choose2} < n+1,$$
i.e. $s_k-1<n<s_k$.
Observing that ${n\choose k}/n^{k-1}$ is increasing in $n$, for $n>k$, this implies that for $n=s_k-1$ the ratio is less than 1, and for $n=s_k$ the ratio is greater than 1.
This gives the result for $k>6$; smaller values can be checked by hand.
A: Well, not an exact answer, unfortunately, but maybe it will help a bit with the intuition. It seems to me you are actually looking at the asymptotic case, $ n \to \infty$. Therefore,
$$
\frac{\binom{n}{k}}{n^{k-1}} \sim \frac{n^k}{n^{k-1} k!} = \frac{n}{k!}
$$
because for large $n \ \frac{n!}{(n-k)!} \sim n^k$. Then clearly the ratio is greater than 1 for $n>k!$. 
