Deje $f(z)=\binom{z}{n},$ donde $\binom{z}{n}=\frac{z(z-1)\cdots(z-n+1)}{n!}$ e imagine $n\ge 0$. Podemos mostrar es convexa cuando se $z\ge n$, por ejemplo, mediante el cálculo de $f''(z)$. De hecho, es cierto para $z\ge n-1$ dxiv la respuesta, dice. Pero $z\ge n$ es lo suficientemente bueno para combinatoria gusto. Me pregunto que podemos mostrar es convexa por algebraicas o los métodos combinatorios o cualquier otros enfoques? Podemos suponer $f$ se define en reales. Pero las pruebas para los números enteros son muy apreciados.
Respuestas
¿Demasiados anuncios?
dxiv
Puntos
1639
Deje $P(z) = n! f(z) = z(z-1)...(z-n+1)$$n \ge 1$. Desde $n!$ es estrictamente positivo factor constante, $P(z)$ tendrá las mismas propiedades de convexidad como $f(z)$.
$P$ es un polinomio de grado $n$ e ha $n$ distintas raíces reales $\{0,1,..,n-1\}$. De ello se desprende que su derivado $P'$ tienen $n-1$ distintas raíces en el intervalo de $(0, n-1)$ y, por $n \ge 2$, $P''$ se han $n-2$ distintas raíces reales en el mismo intervalo de tiempo. De ello se sigue que:
Para $n \gt 2$ habrá al menos una raíz de $P''$$(0,n-1)$, lo que significa que $P''$ va a cambiar de signo al menos una vez (y, de hecho, exactamente $n-2$ veces) en el intervalo. Por lo tanto, $P$ no puede ser convexa ni cóncava en todo el intervalo de $(0,n-1)$.
$P''$ no tiene raíces fuera de $(0,n-1)$, lo $P$ va a ser cóncava o convexa en cada lado del intervalo. Simple signo consideraciones muestran que la $P$ es:
- convexo en $[n-1,\infty)$ todos los $n \ge 1$
- cóncavo en $(-\infty,0]$ $n$ impar, y convexa en $(-\infty,0]$ $n$ incluso.
David K
Puntos
19172
Interpretar $f(z) = \binom zn$ como el número de combinaciones de $n$ objetos que pueden ser seleccionados a partir de un conjunto de $z$ distintos objetos donde$n, z \in \mathbb Z$$z \geq n \geq 0$.
Para$n = 0$,$f(z) = 1$, que es una función convexa.
Para $n \geq 1$, en un conjunto de $z+1$ distintos objetos, $S_{z+1} = \{a_1, \ldots, a_z, a_{z+1}\}$. A continuación, $\binom {z+1}n$ es el número de combinaciones de $n$ objetos seleccionado de $S_{z+1}$. Podemos partición de estas combinaciones en dos conjuntos:
- Las combinaciones en las que se $a_{z+1}$ es seleccionado.
- Las combinaciones en las que se $a_{z+1}$ es no seleccionado.
El número de combinaciones en la primera partición es el número de formas de seleccionar $a_{z+1}$ $\{a_{z+1}\}$ (es decir,$1$) veces el número de maneras de seleccionar el resto de $n-1$ elementos de la $z$-element set $S_{z+1} \setminus \{a_{z+1}\}$,$\binom z{n-1}$. Así que hay $\binom z{n-1}$ combinaciones en esta partición.
El número de combinaciones en la segunda partición es el número de formas de seleccionar $n$ objetos de la $z$-element set $S_{z+1} \setminus \{a_{z+1}\}$, por lo que hay $\binom zn$ combinaciones en esta partición.
Sumando el tamaño de las particiones da el número total de combinaciones, por lo que tenemos $$\binom z{n-1} + \binom zn = \binom {z+1}n.$$ (Este es un resultado conocido, pero quería asegurarse de que se presentó con una combinatoria explicación.) De ello se sigue que $$ \binom {z+1}n - \binom zn = \binom z{n-1} $$ y desde $z+1 \geq n$ como bueno, $$ \binom {z+2}de n - \binom {z+1}n = \binom {z+1}{n-1}. $$
Desde $n - 1 \geq 0$, un argumento similar a la de arriba (incluso en el caso de $n-1=0$ y en el caso de $n - 1 \geq 1$) muestra que $$ \binom z{n-1} \leq \binom {z+1}{n-1}, $$ es decir, $$ \binom {z+1}n - \binom zn \leq \binom {z+2}de n - \binom {z+1}n. $$
Podemos extender esto a través de la inducción para demostrar que si $n \leq z_i < z_m < z_f$ entonces $$ (z_f - z_m) \left( \binom{z_m}n - \binom{z_i}n \right) \leq (z_m - z_i) \left( \binom{z_f}n - \binom{z_m}n \right). $$
De ello se sigue que $$ f(z_m) = \binom{z_m}n \leq \frac{z_f - z_m}{z_f - z_i} \binom{z_i}n + \frac{z_m - z_i}{z_f - z_i} \binom{z_f}n = (1-\lambda) f(z_i) + \lambda f(z_f) $$ donde $0 < \lambda = \dfrac{z_m - z_i}{z_f - z_i} < 1$, que satisface una razonable definición de lo que significa para un la función más enteros para ser convexa sobre los números enteros mayores o igual a $n$.
