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

Question

Me encontré con este tiempo que se considera el subconjunto suma problema en relación a otro problema. Definir la relación,

$$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$

y el entero de la secuencia,

$$s_k = k!+\frac{k(k-1)}{2} = k!+C(k,2)$$

donde $C(k,2)$ el rendimiento de los números triangulares. ¿Cómo podemos mostrar que,

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

Por ejemplo, supongamos $k=6$$s_6 = 735$, entonces,

$$\begin{aligned} R\big(734,\,6\big)\; &= 0.99877\dots\\ R\big(735,\,6\big)\; &= 1.00016\dots \end{aligned}$$

Answer 1

He aquí un esbozo de una solución. Fix $k$; buscamos el único (posiblemente no integral) $n>k$ tal que ${n\choose k}=n^{k-1}$. La expansión de la mano izquierda, tenemos $$ n^k - {k\choose 2}n^{k-1} + {\rm error} = k!\, n^{k-1}$$ Si el término de error no estaban allí, esto daría $n = k! + {k\choose 2}$. Vamos a mostrar que el error es de entre cero y $n^{k-1}$.

Para ello, tenemos que mirar más de cerca el polinomio

$$n(n-1)\cdots(n-k+1) = n^k - c_1 n^{k-1} + c_2 n^{k-2} - \cdots$$ donde $c_r$ es la suma de los productos de todas las $r$-subconjuntos de a $\{0,\ldots,k-1\}$. Es fácil ver que para cada una de las $r$, tenemos $c_r < k^2 c_{r-1}$; esto es debido a que cada una de las $(r-1)$-subconjunto puede ser extendido a un $r$-subconjunto en menos de $k$ maneras, y cada uno de esos extensión aumenta el producto por menos de $k$.

Vamos a suponer $k>6$, por lo que el $k^4<k!<n$. A continuación,$c_r < k^2 c_{r-1} < n c_{r-1}$, por lo que $n^k - c_1 n^{k-1} + c_2 n^{k-2} -\cdots$ es un alternando suma de los términos cuyo valor absoluto disminuye. Así tenemos

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

Tenemos $c_1={k\choose 2}$$c_2< k^2{k\choose2}<k^4 < n$, por lo que tenemos $$n^k - c_1 n^{k-1} < n(n-1)\cdots(n-k+1) < n^k - c_1 n^{k-1} + n^{k-1},$$ es decir, el "error" se intercala entre el $0$ $n^{k-1}$ como se reivindica.

A ver de que esta finalice el argumento, recordemos que elegimos $n$ a fin de que ${n\choose k}=n^{k-1}$. Por lo $n(n-1)\cdots(n-k+1)=k!n^{k-1}$, por lo que el "intercalando" la desigualdad dice $$n^k - c_1 n^{k-1} < k! n^{k-1} < n^k - c_1 n^{k-1} + n^{k-1}.$$ Dividiendo todos los 3 lados por $n^{k-1}$, y la adición de $c_1={k\choose 2}$ a los 3 lados, esto da $$n < k! + {k\choose2} < n+1,$$ es decir,$s_k-1<n<s_k$. La observación de que ${n\choose k}/n^{k-1}$ es el aumento en el $n$$n>k$, esto implica que para $n=s_k-1$ el ratio es menor que 1, y para $n=s_k$ el ratio es mayor que 1.

Esto da el resultado de $k>6$; los valores más pequeños se puede comprobar con la mano.

Answer 2

Bueno, no exactamente una respuesta, por desgracia, pero tal vez pueda ayudar un poco con la intuición. A mí me parece que realmente está mirando el asintótica caso, $ n \to \infty$. Por lo tanto, $$ \frac{\binom{n}{k}}{n^{k-1}} \sim \frac{n^k}{n^{k-1} k!} = \frac{n}{k!} $$ porque para un gran $n \ \frac{n!}{(n-k)!} \sim n^k$. Entonces es claro que la relación es mayor que 1 para $n>k!$.