Prueba de que$ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \binom{n-m}{m}$

Question

Prueba de que $$ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \binom{n-m}{m}$ $

Traté de resolver eso en dos enfoques (en ambos fallaron):
1. Algebraicamente:
Use el teorema de negación: $$ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \sum_k \binom{n-k}{n-m} \binom{k-m-1}{k} $ $ y luego puedo:
$$ \sum_k \binom{n-k}{n-m} \binom{k-m-1}{k} = \sum_k \binom{n-k}{n-m} \binom{k-m-1}{-m-1} $ $ pero atascado ...
Otro enfoque fue tratar de probar eso a través de la interpretación combinatoria. Debido a la falta de resultados no tengo nada que mostrar de esa manera ..

Answer 1

La prueba de álgebra

\begin{align} \sum_k (-1)^k\binom{n-k}{n-m}\binom{m}{k} &=(-1)^m\sum_k (-1)^{m-k}\binom{n-k}{m-k}\binom{m}{k} \\&\stackrel{\text{n}}=(-1)^m\sum_k \binom{m-n-1}{m-k}\binom{m}{k} \\&\stackrel{\text{V}}=(-1)^m\binom{2m-n-1}{m} \\&\stackrel{\text{n}}=\binom{n-m}m \end{align} $\stackrel{\text{n}}=$ es la negación teorema.
$\stackrel{\text{V}}=$ es el (Chu)-Vandermonde de identidad.

Combinatoria prueba de croquis

Ambos lados de responder a la pregunta

¿Cuántos subconjuntos de a$\{1,2,\dots,n\}$ tienen un tamaño $m$, no hay dos elementos consecutivos, y no contienen $n$?

El RHS es cierto porque $$ (i_1,i_2,\dots,i_m)\implica (i_1,i_2+1,i_3+2,\dots,i_m+{m-1}) $$ es un bijection de aumento de secuencias de longitud $m$ cuyas entradas están entre $1$ e $n-m$, a los subconjuntos de a$\{1,2,\dots,n-1\}$ sin elementos adyacentes (escrito en orden creciente).

Contamos tales subconjuntos mediante el principio de inclusión y de exclusión. Es decir, para $1\le i\le n-1$ deje $E_i$ el conjunto de los subconjuntos donde la $i^{th}$ más pequeño es el elemento adyacente a la $(i+1)^{st}$ elemento más pequeño, y deje $E_n$ el conjunto de los subconjuntos que incluyen $n$. Estos son los malos subconjuntos, así que queremos que $|E_1^c\cap E_2^c\cap \dots \cap E_n^c|$, que es $$ \sum_{S\subseteq \{1,2,\dots,m\}} (-1)^{|C|}\left|\bigcap_{i\in S}E_i\right| $$ Resulta que $\left|\bigcap_{i\in S}E_i\right|=\binom{n-k}{m-k}$ siempre $|S|=k$. Aproximadamente, cuando $k$ de los elementos del subconjunto que están obligados a ser adyacentes, podemos agrupar estos elementos juntos en un solo bloque, por lo que hay sólo $m-k$ elementos para ser elegido en un espacio más pequeño de $n-k$. Os dejo los detalles más complejos.

Answer 2

Con $n\ge m$ donde $m\ge 0$ buscamos mostrar que

$$\sum_{k=0}^m {m\elegir k} (-1)^k {n-k\elegir n-m} = {n-m\elegir m}.$$

La suma es

$$\sum_{k=0}^m {m\elegir k} (-1)^k [z^{n-m}] (1+z)^{n-k} \\ = [z^{n-m}] (1+z)^n \sum_{k=0}^m {m\elegir k} (-1)^k (1+z)^{-k} \\ = [z^{n-m}] (1+z)^n \left(1-\frac{1}{1+z}\right)^m \\ = [z^{n-m}] (1+z)^{n-m} z^m = [z^{n-2m}] (1+z)^{n-m} \\ = {n-m\elegir n-2m} = {n-m\elegir m}.$$

Observación. Queremos demostrar que esto se mantiene incluso cuando se $n\lt m$ donde de nuevo $m\ge 0.$ Estamos usando el poder formal de la serie y no hay parte principal como en una Laurent de la serie, por lo tanto el coeficiente de extractor $[z^{n-m}]$ está definida para devolver cero cuando se $n\lt m.$ Este es también el el comportamiento del sistema cuando el Coeficiente de Cauchy Fórmula se utiliza, en donde hemos

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-m+1}} (1+z)^{n-k} \; dz$$

y con $n\lt m$ ningún polo en cero nunca aparecen. En estos circunstancias de algunos autores y de álgebra computacional, como los sistemas de Arce definir el valor a ser

$${n-k\elegir (n-k)-(n-m)} = {n-k\elegir m-k} = \frac{(n-k)^{\underline{m-k}}}{(m-k)!}$$

suponiendo que $m\ge k.$ Con esta configuración estamos, de hecho, no-cero los valores de $n\lt k \le m.$ también disponemos de acuerdo con los valores desde el primer caso ($n\ge m$).

Obtenemos entonces para nuestros suma

$$\sum_{k=0}^m {m\elegir k} (-1)^k [z^{m-k}] (1+z)^{n-k} \\ = [z^m] (1+z)^n \sum_{k=0}^m {m\elegir k} (-1)^k z^k \frac{1}{(1+z)^k} \\ = [z^m] (1+z)^n \left(1-\frac{z}{1+z}\right)^m = [z^m] (1+z)^{n-m} = {n-m\elegir m}.$$

Esta prueba va a través de todos los enteros $n$ e $m\ge 0.$

Answer 3

He aquí un semi-combinatoria prueba. Vamos a considerar un término en el lado izquierdo. En primer lugar, sabemos que $\binom{m}{k}$ cuenta el tamaño de la-$k$ subconjuntos de a$[m]$. A continuación, considere la posibilidad de $\binom{n-k}{n-m}=\binom{n-k}{m-k}$; ya que tienen un tamaño-$k$ subconjunto $A$ de $[m]$, podemos pensar en esto como el conteo de tamaño-$(m-k)$ subconjuntos de a$[n]-A$. Por lo tanto, el lado izquierdo cuenta los pares de conjuntos de $(A,B)$ tal que $A\subseteq [m]$ con $|A|=k$ e $B\subseteq [n]-A$ con $|B|=m-k$. Sin embargo, existe la salvedad de que tal un par de $(A,B)$ tiene una contribución positiva si $|A|$ es par, y una contribución negativa si $|A|$ es impar.

Desde $A$ e $B$ son distintos, el de la unión de $A\cup B=C$ tiene el tamaño de $m$. Mirando en su lugar a todos esos $C=A\cup B$, esto es equivalente a mirar en todas las $C\subseteq [n]$ tal que $|C|=m$, y para cada una de las $C$, considerando todos los subconjuntos de a$A\subseteq C\cap [m]$; cada uno de esos $(C,A)$ par le da una contribución positiva si $|A|$ es par, y una contribución negativa si $|A|$ es impar.

Ahora hago la siguiente afirmación: para cada una de las $C$, la suma de las contribuciones de todos los $(C,A)$ pares es $0$ si $C\cap [m]$ es no vacío, y $1$ si $C\cap[m]=\varnothing$. Usted puede mostrar esta usando el mismo argumento de que un tamaño de$n$ tiene exactamente el número impar subconjuntos como lo hace incluso subconjuntos cuando $n\geq 1$, y sólo uno, incluso subconjunto (en sí mismo) y no extraño subconjuntos cuando $n=0$. A continuación, se deduce que realmente estamos contando tamaño-$m$ conjuntos de $C$ con $C\subseteq [n]-[m]$, que se cuentan por $\binom{n-m}{m}$. Hay algunos detalles que usted puede llenar para entender por qué esto funciona.