Delimitación ${(2d-1)n-1\choose n-1}$

Question

Reclamo: ${3n-1\choose n-1}\le 6.25^n$.

1. Por qué?

2. Puede que la prueba se extiende a obtener un límite de ${(2d-1)n-1\elegir n-1}$, with the bound being $f(d)^n$ para algunos la función $f$?

(Estos números se describe el número de algunos de los $d$-dimensiones de objetos combinatorios; la reivindicación 1 es el caso de $d=2$, y no es mi reclamación).

Answer 1

En primer lugar, permite obligado cosas tan fácilmente como sea posible. Considerar la desigualdad $$\binom{n}{k}=\frac{(n-k)!}{k!}\leq\frac{n^{k}}{k!}\leq e^{k}\left(\frac{n}{k}\right)^{k}.$$ The $n^k$ comes from the fact that $n$ is bigger then each factor of the product in the numerator. Also, we know that $k!e^k>k^k$ by looking at the $k^{th}$ term in the Taylor series, as $e^k=1+k+\cdots +\frac{k^k}{k!}+\cdots $.

Ahora, veamos el similar $3n$ $n$ en lugar de $3n-1$$n-1$. Entonces podemos ver que $$\binom{3n}{n}\leq e^{n}\left(3\right)^{n}\leq\left(8.15\right)^{n}$$and then for any $k$ we would have $$\binom{kn}{n}\leq\left(ke\right)^{n}.$$

Podríamos utilizar Stirlings fórmula, y mejorar esta más. ¿Qué es lo más que esto puede ser mejorado? Al parecer, según Wolfram lo mejor posible es $$\binom{(k+1)n}{n}\leq \left(\frac{(k+1)^{k+1}}{k^k}\right)^n.$$

(Observe que cuando se $k=2$ tenemos $27/4$$6.25$)

Espero que ayude.

Answer 2

En el mientras tanto, se puede considerar la siguiente.

Supongamos que $X$ es un binomio$((2d-1)n-1,p)$ variable aleatoria ($0 < p < 1$). A continuación, $$ {\rm P}(X = n - 1) = {(2d-1)n-1 \elegir n-1} p^{n-1}(1-p)^{n(2d-2)} \leq 1. $$ Poner a $z=1/p > 1$, por lo tanto tenemos $$ {(2d-1)n-1 \elegir n-1} \leq z^{n-1} \bigg(\frac{z}{{z z z - 1}}\bigg)^{n(2d - 2)} = \frac{1}{z}\bigg[\frac{{z^{2d - 1} }}{{(z - 1)^{2d - 2} }}\bigg]^n . $$ Por lo tanto, queremos minimizar $$ \psi(z) = \frac{{z^{2d - 1} }}{{(z - 1)^{2d - 2} }},\;\; z > 1. $$ En el caso de que $d=2$, obtenemos $$ {3n-1 \elegir n-1} \leq \frac{1}{z}\bigg[\frac{{z^3 }}{{(z - 1)^2 }}\bigg]^n. $$ Aquí, $\psi(z) = \frac{{z^3 }}{{(z - 1)^2 }}$ alcanza su mínimo en $z=3$ donde $\psi(z)=27/4$. Por lo tanto $$ {3n-1 \elegir n-1} \leq \frac{1}{3}\bigg(\frac{{27}}{4}\bigg)^n = \frac{1}{3}6.75^n . $$

EDIT: Para general $d$, la función de $\psi(z)$ alcanza su mínimo en $z=2d-1$ ($\psi(z) \to \infty$$z \downarrow 1$ o $z \to \infty$, y, como un elemental cálculo de la muestra, $\psi'(z)=0$$z=2d-1$). Por lo tanto, $$ {(2d-1)n-1 \elegir n-1} \leq \frac{1}{{2d - 1}}\bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^n . $$

Answer 3

(Primera nota Gadi, el comentario de debajo de la pregunta.)

En mi respuesta anterior, me derivados de la desigualdad $$ {(2d-1)n-1 \elegir n-1} \leq \frac{1}{{2d - 1}}\bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^n , $$ que ya es más de lo necesario debido a que el factor de $1/(2d-1)$ (recordemos que en el caso de $d=2$ el lado derecho es igual a $(1/3)6.75^n$). Sin embargo, esta desigualdad puede mejorarse aún más para $$ {(2d-1)n-1 \elegir n-1} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n-1} , $$ que es óptimo ya que la igualdad tiene al $n=1$.

La última desigualdad se puede demostrar mediante la inducción de la siguiente manera (para $d \geq 2$ fijo entero). En primer lugar, tenemos la igualdad cuando la $n=1$. La próxima nota de que $$ {(2d-1)(n+1)-1 \elegir n} = \frac{{((2d - 1)n - 1)!}}{{(n - 1)!((2d - 2)n)!}}\frac{{(2d - 1)n}}{n}\frac{{\prod\nolimits_{k = 1}^{2d - 2} {((2d - 1)n + k)} }}{{\prod\nolimits_{k = 1}^{2d - 2} {((2d - 2)n + k)} }}. $$ Ya que, por cualquier $1 \leq k \leq 2d-2$, $$ \frac{{(2d - 1)n + k}}{{(2d - 2)n + k}} \le \frac{{2d - 1}}{{2d - 2}}, $$ de esto se sigue que $$ {(2d-1)(n+1)-1 \elegir n} \leq {(2d-1)n-1 \elegir n-1} \frac{{2d - 1}}{1} \bigg(\frac{{2d - 1}}{{2d - 2}}\bigg)^{2d - 2} . $$ Ahora, bajo la hipótesis de que la inducción $$ {(2d-1)n-1 \elegir n-1} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n-1} , $$ tenemos $$ {(2d-1)(n+1)-1 \elegir n} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n}, $$ completar la prueba.

Answer 4

Sólo el uso de la fórmula de Stirling $$n! \sim \sqrt{2\pi n} (n/e)^n$$ para un gran $n$ y el abandono de la $\sqrt{2\pi n}$ factor por un tiempo. Eso nos da una buena estimación de su expresión $$(3n-1)! / [ (n-1)!(2n)! ] \sim (2n)^{-2n}(n-1)^{1-n} (3n-1)^{3n-1} $$ Tenga en cuenta que los poderes de la $e$ cancelar. Para un gran $n$, usted también puede aproximar las bases de los poderes simplemente por $2n,n,3n$, respectivamente. Entonces usted consigue $$\sim 2^{-2n} 3^{3n} = (27/4)^{n} $$ porque los poderes de $n$ cancelar, demasiado. Tenga en cuenta que $27/4 = 6.75$. Sólo he calculado la estimación - que es en realidad un mejor resultado, ya que muestra que el número de $6.75$ es exacta en la gran $n$ límite. Para demostrar la desigualdad, se tiene que ver detenidamente si la fórmula de Stirling subestima o sobrestima. En cualquier caso, es sencillo comprobar que la desigualdad se cumple para cualquier positivos $n$.

Es suficiente para comprobar explícitamente para un par de primero a pequeña valores de $n$, y para los mayores, se puede demostrar que el $(27/4)^n$ Ansatz está siendo abordado desde el lado derecho mediante el cálculo de la señal de la primera subleading corrección para esta aproximación. Si usted enumerar los primeros coeficientes binomiales sobre la aproximación (que debe ser menor que uno) por Mathematica

[Table[Binomial[3 n - 1, n - 1]/(27/4)^n, {n, 1, 20}]]

usted recibirá

{0.14814815, 0.10973937, 0.091043032, 0.079482012, 0.071435685, 0.06542258, 0.060709598, 0.056887142, 0.053706089, 0.051005081, 0.048674402, 0.046636504, 0.04483482, 0.043226987, 0.041780567, 0.040470244, 0.039275935, 0.038181474, 0.037173681, 0.036241691}

Los números son claramente menor que uno, y desde el principio, la disminución es uniforme.

Para su caso de $d$ dimensiones, los términos restantes son reemplazados por $$ \sim (2d-2)^{(2-2d)(n-1)} (2d-1)^{(2d-1)(n-1)} $$ por lo $27/4$ se sustituye por $(2d-1)^{2d-1}/(2d-2)^{2d-2}$. Para $d=2$, consigue $3^3/2^2 = 27/4$. Para $d=3$, obtendría $5^5/4^4$, y así sucesivamente.

Tenga en cuenta que la prueba sólo funciona para 27/4 = 6.75. Este número no podía ser reducido de nuevo (6.25 es un error tipográfico) y cualquier prueba que sustituye a 6.75 por un número mayor no puede probar la afirmación original.