$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Tenga en cuenta que podemos mostrar esto con el uso de la inclusión y el principio de exclusión mediante el uso de Pascal la Identidad de decir $C(n,k)=C(n-1,k)+C(n-1,k-1)$.
Respuestas
¿Demasiados anuncios?
dorian stonehouse
Puntos
11
Ampliado de Pedro Sánchez Terraf la respuesta, pero añadió mi punto de vista para escribir la combinatoria de la prueba.
La visualización de las diagonales del triángulo de Pascal, cabe recordar que la $\binom {m+n-1} m$ representa el $n$'th $m$-dimensional simple número. (Para $0$-la dimensión, números naturales para $1$-la dimensión, entonces el triángulo de números, números tetraédricos, pentatope números, etc.) (por ejemplo, $\binom {n+1} 2$ representa el $n$'th triángulo número)
Con la fija $m$$n$, vamos a $A_i$ ser el conjunto de números enteros de $1$ a $\binom {(m-1)+i-1}{m-1}$, $i = 1 \ldots (n-m+1)$: $$\begin{align*} A_1 &= \left\{1, \ldots, \binom {m-1}{m-1}\right\} = \left\{1\right\}\\ A_2 &= \left\{1, 2, \ldots, \binom{m}{m-1}\right\}\\ &= \left\{1, 2, \ldots,\binom m1\right\}\\ &= \left\{1, 2, \ldots, m\right\}\\ &\vdots\\ A_i &= \left\{1, 2, \ldots, \binom{m+i-2}{m-1}\right\}\\ &\vdots\\ A_{n-m+1} &= \left\{1, 2, \ldots, \binom{(m-1)+(n-m+1)-1}{m-1}\right\}\\ &= \left\{1, 2, \ldots, \binom {n-1}{m-1}\right\}\\\\ \end{align*}$$ Llame al número de series, y también el número de términos, $n-m+1$, se $N$.
Editar añadido: En retrospectiva, $A_{n-m+1}$'s puede ser también de juegos de bolas que forman la $(n-m+1)$th simplex en $m$ dimensión. Todos los otros $A_i$'s son el conjunto de bolas que se forman menor $m$-simplexes de tamaño $i$, son subconjunto de $A_{n-m+1}$, y comparten el mismo vértice.
Para el lado derecho, la unión de todos estos conjuntos es $$\left|\bigcup_{i=1}^{N}A_i\right| = \left|A_{N}\right| = \binom {n-1}{m-1}$$
Para el lado izquierdo, el primer término, $$\begin{align*} \sum_{i=1}^{N} \left|A_i\right| =& \sum_{i=1}^{N} \binom{m+i-2}{m-1} \\ =& \sum_{i=1}^{N} \binom{(m-1)+i-1}{m-1}\\ =& \binom{m + N -1}{m}\\ =& \binom{n}{m} \end{align*}$$ El penúltimo paso proviene de la definición que, la suma de los $1$st $N$'th simplex número es el $N$'th simplex número de la siguiente dimensión.
Para cada uno de los posteriores plazo, dicen los $k$'th, fuera de la $N$ conjuntos, cada vez que $k$ de los juegos tienen su intersección tomadas y se añade. ($1 \le k \le N = n-m+1$)
Hay $\binom{N-1}{k-1}$ conjuntos que contienen $A_1$, y el tamaño de cada una de las intersecciones se $1 = \binom{m-1}{m-1}$. Luego hay $\binom{N-2}{k-1}$ conjuntos que contienen $A_2$ pero no $A_1$, etc. Sumar el recuento de las intersecciones con sus respectivos tamaños, el $k$'th término en el lado izquierdo de la OP de la fórmula es $$\begin{align*} \sum_{i=1}^{N-(k-1)}\binom{m+i-2}{m-1}\binom{N-i}{k-1} &= \sum_{i=1}^{N-k+1}\binom{(m-1)+i-1}{m-1}\binom{(k-1)+(N-k+2-i)-1}{k-1} \end{align*}$$ Cada uno de los dos coeficientes binomiales es una secuencia de hyper-tetraédrica número. El segundo coeficiente binomial, $\binom{N-i}{k-1}$ pistas de$\binom{N-1}{k-1}=\binom{(k-1)+(N-k+1)-1}{k-1}$$\binom{k-1}{k-1} = \binom{(k-1)+1-1}{k-1}$. Cuando se ve como un término-a-término producto de las dos secuencias de números tetraédricos, el resultado es otro tetraédrica número de dimensiones superiores: $$\binom{n}{m+k-1}$$
Ver editado por debajo , Pero esto es sólo mi intuición y todavía no he demostrado plenamente el presente.
La suma es consistente con los dos últimos términos en OP fórmula:
al $k = N-1 = n-m$, la suma que consta de dos términos, $$\begin{align*}\binom {m-1}{m-1}\binom{N-1}{N-2} + \binom {m}{m-1}\binom{N-2}{N-2} & =(N-1)+m\\ &= n \\ &=\binom{n}{n-1} \end{align*}$$ lo que confirma que se $N-1=n-m$ intersecciones cada una con $1$ elemento, y $A_2\cap A_3 \cap \cdots \cap A_N$ ha $m$ elementos.
al $k = N = n-m+1$, la suma se compone de un término, $$\binom {m-1}{m-1}\binom{N-1}{N-1}=1=\binom{n}{n}$$ que también confirma que la intersección de a $A_1, A_2, \ldots, A_{n-m+1}$ tiene un solo elemento.
Edit: Para probar: $$\sum_{i=1}^c\binom {a+i-1}a \binom{b+(c+1-i)-1}b = \binom{(a+b+1)+c-1}{a+b+1}$$ He añadido extra entre paréntesis y condiciones, a fin de que cada coeficiente binomial se puede traducir directamente a un simple número con dimensiones específicas.
En primer lugar, la suma introduce 1 dimensión. Llamamos a esto el $x$-dirección.
Segundo, considere la posibilidad de $\binom{a+i-1}a$ solamente. Cada término en sí mismo es el $i$th simplex número en $a$-dimensión. Extender el 1-dimensional mundo a $1+a$ dimensión mundial, con nuevas direcciones ortogonales $y_1, y_2, \ldots, y_a$.
A continuación, para cada una de las $c$ términos, organizar $\binom{a+i-1}a$ bolas en la simple forma en el nuevo $a$ dimensiones, en un número entero de rejilla de origen $(1,1,1,\ldots, 1)$. El simplex es en ángulo recto con $a+1$ vértices en $(y_1, y_2,y_3, \ldots, y_a) =$ $$(1,1,1,\ldots, 1),\ (i, 1, 1, \ldots, 1),\ (1, i, 1, \ldots, 1),\ (1, 1, i, \ldots, 1),\ldots,\ (1, 1, 1, \ldots, i)$$
La pila de la $c$ simplexes a lo largo de $x$-dirección, poniendo el $i$th simplex en $x=i$. Esta pila de secuencial simplexes da un $(a+1)$-simplex de vértices en $(x; y_1, y_2,y_3, \ldots, y_a)=$ $$(c; 1,1,1,\ldots, 1),\ (c;c, 1, 1, \ldots, 1),\ (c 1, c, 1, \ldots, 1),\ (c, 1, 1, c, \ldots, 1),\ldots,\ (c, 1, 1, 1, \ldots, c)$$ y el origen $(1;1,1,1,\ldots,1)$
Tercero, otra vez, ampliar el mundo de $1+a$ dimensiones a $1+a+b$ dimensiones, llamando a la nueva $b$ direcciones ortogonales como $z_1, z_2, \ldots, z_b$.
Para cada bola previamente en el $x=i$ rebanada, el número tiene que ser multiplicada por $\binom{b+(c+1-i)-1}b$, que es el $(c+1-i)$th simplex número en $b$ dimensión. Organizar $\binom{b+(c+1-i)-1}b$ bolas en un $b$-simplex forma con el ángulo recto en el origen $(z_1, z_2, \ldots, z_b) = (1, 1, \ldots, 1)$. Copia esta tabla por cada balón en el $x=i$ sector. Repita esto para cada sector en el $x$-de la dirección, y el nuevo simplex está terminado, con dimensión de $a+b+1$.
El nuevo simplex tiene los vértices en $(x; y_1, y_2, \ldots, y_a; z_1, z_2, \ldots, z_b)=$
- El origen: $(1;1,1,\ldots,1;1,1,\ldots,1)$
- A $x$-dirección: $(c;1,1,\ldots,1;1,1,\ldots,1)$
- A $y$-direcions: $$(c;c, 1, \ldots, 1;1,1,\ldots,1),\ (c 1, c, \ldots, 1;1,1,\ldots,1),\ldots,\ (c, 1, 1, 1, \ldots, c;1,1,\ldots,1)$$
- A $z$-instrucciones: $$(1;1, 1, \ldots, 1;c,1,\ldots,1),\ (1;1, 1, \ldots, 1;1,c,\ldots,1),\ldots,\ (1;1, 1, 1, \ldots, 1;1,1,\ldots,c)$$
Observe que para el $y$-direcciones, el simplex se corta, y los vértices que no están en los "ejes" donde todos pero uno coordenadas se $1$. Sin embargo, por corte a lo largo de todos los $y$ direcciones, es posible obtener una escala estándar simplex.
Y por último, el número de bolas en el $c$th $(a+b+1)$-simplex es $\binom{(a+b+1)+c-1}{a+b+1}$. Sustituto $a= m-1$, $b=k-1$, $c=n-m+1$.
Y por bolas, me refiero a hyperspheres.
Un ejemplo de cómo las bolas se apilan, $a=2$, $b=2$, $c=4$, que se traduce en un $5$-simplex. El simple arreglo es perpendicular a rodajas $x$, $y_1$ y $y_2$ direcciones.
rlpowell
Puntos
126
Vamos a empezar por volver a escribir la fórmula con un cambio de $n$$m$$n+1$$m+1$, por lo que la expresión para demostrar que es
$${n\choose m} = {n+1\choose m+1}-{n+1\choose m+2}+{n+1\choose m+3}-\cdots+(-1)^{n-m}{n+1\choose n+1}$$
Ahora la imagen de una clase con $n$ de estudiantes y un profesor. Cada término de la derecha es de la forma ${n+1\choose k}$, que cuenta el número de maneras que usted puede elegir un grupo de tamaño de $k$ entre el $n+1$ de personas en la clase. Entre estos grupos se encuentran algunos que incluyen el maestro y algunos que no. Cada grupo de tamaño de $k$ que no incluyen el maestro puede ser identificado con un grupo de tamaño $k+1$ que no incluyen el maestro.
La expresión ${n\choose m}$ puede ser interpretado como contar el número de maneras que usted puede elegir un grupo de tamaño de $m$ entre el $n$ sólo para estudiantes-y luego, si se quiere, añadir el profesor para un grupo de tamaño de $m+1$. La inclusión-exclusión es ahora clara: Comenzar con todas las maneras en que usted puede formar un grupo de tamaño de $m+1$, a continuación, tratar de eliminar el sobre contar, que consta de todos los grupos de estudiantes.
Pedro Sánchez Terraf
Puntos
854
Este es demasiado largo para un comentario, por eso me voy a poner aquí.
La primera observación es que la fórmula ya implica la identidad de Pascal. La sustitución de $m$ $m+1$ hemos $$\binom{n}{m+1}-\binom{n}{m+2}+\cdots+(-1)^{n-m-1}\binom{n}{n}=\binom{n-1}{m}.$$ Añadiendo a la fórmula original da (después de la cancelación) $\binom{n-1}{m}+\binom{n-1}{m-1}=\binom{n}{m}$. Así que, en cierto sentido, toda prueba de esta identidad debe incluir la idea de probar de Pascal.
Ahora hay una manera de poner a la LHS, como una solicitud de Inclusión-Exclusión principio. Tomar los siguientes conjuntos:
$$ \begin{align} A_1 &:= \left\{1,2,\dots,\textstyle\binom{n-1}{m-1}\right\}\\ A_2 &:= \left\{1,2,\dots,\textstyle\binom{n-2}{m-1}\right\}\\ &\dots \\ A_{n-m+1} &:= \left\{\textstyle\binom{m-1}{m-1}\right\} =\{1\}. \end{align} $$ Así que tenemos $A_1\supset A_2 \supset \dots \supset A_{n-m+1}$. Si se aplica En-Ex para demostrar que $$ |A_1\cup \dots \copa A_{n-m+1}| = |A_1|=\estilo de texto\binom{n-1}{m-1}, $$ usted puede obtener (a través de un amplio uso de Pascal y tal vez también de inducción) de la suma en el lado izquierdo de la ecuación.
Markus Scheuer
Puntos
16133
Nota: Esta respuesta es inspirado por el borrado de respuesta de @diracpaul.
Analizamos celosía pathes generados a partir de $(1,0)$ $x$- dirección y $(0,1)$ $y$- dirección. El número de pathes de$(0,0)$$(m,n-m)$$\binom{n}{m}$. Esto es válido, ya que para pathes de longitud $n$ podemos seleccionar $m$ $x$- dirección dejando $n-m$ $y$- dirección.
Vamos a escribir $\binom{n}{m}$ en la más simétrica versión utilizando coeficientes multinomiales $\binom{n}{m,n-m}$. Utilizando esta notación OPs ecuación se convierte en
\begin{align*} \binom{n-1}{m-1,n-m}&=\binom{n}{m,n-m}-\binom{n}{m+1,n-m-1}\\ &\qquad+\binom{n}{m+2,n-m-2}-\cdots+(-1)^{n-m}\binom{n}{n,0}\tag{1} \end{align*}
Para su conveniencia únicamente podemos cambiar la representación mediante el establecimiento $x=m$$y=n-m$. A continuación, OPs ecuación (1) se convierte en
\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\ &\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}\tag{2} \end{align*}
Antes de interpretar la identidad (2) un aspecto adicional. Podemos usar sólo $(1,0)$ o $(0,1)$ pasos. Así, cuando vamos de $(0,0)$ a un punto de $(x,y)$$x,y>0$, tenemos que pasar bien $(x-1,y)$ o $(x,y-1)$. Esto le da a la conocida identidad
\begin{align*} \binom{x+y}{x,y}=\binom{x+y-1}{x-1,y}+\binom{x+y-1}{x,y-1}\tag{3} \end{align*}
Ahora le reclamo las siguientes:
El lado izquierdo de (2) da el número de pathes de longitud $x+y-1$$(0,0)$$(x-1,y)$.
El lado derecho de (2) da el número de pathes de longitud $x+y$ $(0,0)$ $(x,y)$que pasan a $(x-1,y)$.
Puesto que sólo hay una posibilidad para ir de $(0,0)$ $(x,y)$través $(x-1,y)$, es decir, mediante la adición de un $(1,0)$ paso de$(x-1,y)$$(x,y)$, es evidente que ambas partes dan el mismo número. De acuerdo a (3) llegamos a la conclusión de
\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\tag{4} \end{align*}
El lado derecho de la expresión (4) es correcto, pero no es lo mismo el lado derecho de (3).
La idea es acercarnos a la representación (3) paso a paso. Tomamos nota de que $\binom{x+y-1}{x,y-1}$ es el número de pathes de longitud $x+y-1$$(0,0)$$(x,y-1)$. Sostenemos ahora similares a las anteriores, y decir que este es el mismo que el número de pathes de longitud $x+y$ $(0,0)$ $(x+1,y-1)$pasando a través de las $(x,y-1)$.
Esto se realiza de acuerdo a (3) a través de
\begin{align*} \binom{x+y-1}{x,y-1}&=\binom{x+y}{x+1,y-1}-\binom{x+y-1}{x+1,y-2}\tag{5} \end{align*}
La combinación de este con (4) da
\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\ &=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y-1}{x+1,y-2} \end{align*}
Y de nuevo tenemos que sustituir el superávit $\binom{x+y-1}{x+1,y-2}$ por el número de pathes de longitud $x+y$ $(0,0)$ $(x+2,y-2)$pasando a través de las $(x+1,y-2)$. Esto se traduce en
\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\ &=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y}{x+2,y-2}-\binom{x+y-1}{x+2,y-3} \end{align*}
Procediendo de esta manera se llega paso a paso por el lado derecho de (2). Observar que las cantidades de excedentes son compensados de acuerdo a la inclusión-exclusión principio.
Llegamos a la conclusión: El binomio identidad
\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\ &\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}=\tag{2} \end{align*}
muestra que el número de pathes de longitud $x+y-1$ $(0,0)$ $(x-1,y)$es el mismo que el número de pathes de longitud $x+y$ $(0,0)$ $(x,y)$pasando a través de $(x-1,y)$, por el excedente puede ser compensada por sucesivamente sumar y restar pathes de longitud $x+y$ de acuerdo a la inclusión-exclusión principio.
