When $\frac{C(n, k)}{n^{k-1}} > 1$?

Question

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}$$

Answer 1

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!$.

Answer 2

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.