Combinatoria interpretación de una corriente alterna binomio suma

Question

Deje $n$ ser un fijo número natural. Tengo razones para creer que $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ Sin embargo no puedo probar esto. Cualquier método para demostrar esto se aprecia, sino una combinatoria de la solución es muy preferido. Gracias por tu ayuda.

Answer 1

La reescritura de la identidad con el índice de la suma cambió de $i$ $j$donde $j=i-k+1$: $$\sum_{j=1}^{n+1-k}(-1)^{j-1}\binom{n+1}{k+j}\binom{k+j-1}k=1.$$ Definir una "buena palabra" a ser una palabra de longitud $n+1$ sobre el alfabeto $\{A,B,C\}$ la satisfacción de las condiciones: no son exactamente $k$ $C$'s, hay al menos un $B$, y el primer $B$ precede a todas las $C$'s.

Si $j$ es el número de $B$'s en una buena palabra, entonces debemos tener $1\le j\le n+1-k$; por otra parte, el número de palabras con exactamente $j$ $B$'s está dada por la expresión $$\binom{n+1}{k+j}\binom{k+j-1}k.$$ La combinatoria significado de la identidad es que el número de palabras con un número impar de $B$s'es uno más que el número de palabras con un número de $B$'s. Aquí está una bijective prueba de ese hecho.

Deje $w$ ser la palabra que consta de una sola $B$ precedido por $n-k$ $A$'s y seguido por $k$ $C$'s; esta es una buena palabra con un número impar de $B$'s. Deje $W$ ser el conjunto de todas las buenas palabras diferentes de $w$; tenemos que demostrar que $W$ sólo contiene la mayor cantidad de palabras con un extraño con un número de $B$'s. Para ver esto, observe que la operación de conmutación de la última no-$C$ letra en una palabra (de $A$ $B$o de$B$$A$) es una involución en $W$ que cambios en la paridad del número de $B$'s.

Answer 2

Todavía no he venido para arriba con una combinatoria de prueba, pero una prueba usando inducción y la fórmula binominal es bastante claro.

Reparamos $k \geqslant 0$ y el uso de la inducción en $n \geqslant k$. El caso base $n = k$ es simplemente

$$\sum_{i=k}^k (-1)^{i-k}\binom{i}{k}\binom{k+1}{i+1} = (-1)^0 \binom{k}{k}\binom{k+1}{k+1} = 1.$$

Para la inducción de paso, hemos

$$\begin{align} \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\binom{n+2}{i+1} &= \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\left\lbrace \binom{n+1}{i+1} + \binom{n+1}{i}\right\rbrace\\ &=\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1} + \sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}\\ &=\underbrace{\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1}}_1 + \underbrace{\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}}_{m(k,n)} \end{align}$$

donde en el primer sumando de la derecha el plazo para $i = n+1$ se desvanece desde $\binom{n+1}{n+1+1} = 0$ y el resto corresponde a la suma de$n$, $1$ por la hipótesis de inducción.

Queda por ver que $m(k,n) = 0$. Pero que es el coeficiente de $x^k$ en

$$\begin{align} x^{n+1} &= \bigl(1 - (1-x)\bigr)^{n+1}\\ &= \sum_{i=0}^{n+1} (-1)^i\binom{n+1}{i}(1-x)^i\\ &= \sum_{i=0}^{n+1} \sum_{k=0}^i (-1)^{i+k}\binom{i}{k}\binom{n+1}{i}x^k\\ &= \sum_{k=0}^{n+1}\left(\sum_{i=k}^{n+1}(-1)^{i+k}\binom{i}{k}\binom{n+1}{i}\right)x^k, \end{align}$$

desde $(-1)^{i+k} = (-1)^{i-k}$. Tenemos $k \leqslant n < n+1$, por lo tanto el coeficiente de es $0$.

Answer 3

Esta es una combinatoria de la prueba de $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ Puede ser reordenada para $$\sum_{i=k+2t } \binom{i}{k} \binom{n+1}{i+1} = 1+ \sum_{i=k+1+2t} \binom{i}{k} \binom{n+1}{i+1} $$

Yo prefiero hablar de la elección de $i$ elementos de un conjunto con $n$ elementos a la elección de $i+1$ elementos de un conjunto con $n+1$ elementos así que me sustituya $i$ por $i-1$, $k$ por $k-1$ $n$ $n-1$ y obtener $$\sum_{i=k+2t } \binom{i-1}{k-1} \binom{n}{i} = 1+ \sum_{i=k+1+2t} \binom{i-1}{k-1} \binom{n}{i} \tag{1} $$

Uno bien conocido interpretación de $\binom{n}{i}$ es como el número de subconjuntos con $i$ elementos de las $ \{1,2,\ldots,n \}$.

si $n=9$ $\{2,3,4,6,8\}$ es un subconjunto con $i=5$ elementos de $\{1,2,3,4,5,6,7,8,9\}$. Tenga en cuenta que en la notación de la larga nos encontramos con $i-1=4$ comas (","). Vamos a seleccionar dos de este comas un reemplazarlos por "} {". Llegamos $\big\{\{2\}\;\{3,4\}\;\{6,8\}\big\}$ si se sustituye la primera y la tercera por comas. Por lo $\binom{i-1}{k-1}$ puede ser interpretado como el número de las formas un conjunto con $i$ elementos puede ser dividido en $k$ no vacía de subconjuntos de a $ A_r$ tal que para cada par a, B de tales subconjuntos de la siguiente se tiene: $$(a \lt b, \;\; \forall a \in A, \forall b \in B) \;\;\text{or} \;\; (a \gt b, \;\; \forall a \in A, \forall b \in B)$$

El producto $\binom{i-1}{k-1} \binom{n}{i}$ puede ser interpretado como el número de maneras en las que podemos encontrar $k$ subconjuntos $A_j$ $\{1,2,\ldots,n \}$ tal que $$ A_r \cap A_s = \emptyset, \forall 1 \le r \lt s \le k \tag{2a}$$ $$ a_r \lt a_s, \forall a_r \in A_r, \forall a_s \in A_s, 1 \le r \lt s \le k \tag{2b}$$ $$ \sum_{r=1}^{k}|A_r|=i \tag{2c}$$

Llamamos al conjunto de todos los $\{A_1,\ldots \}$ que satisfacer $(2)$$\Omega_{n,k,i}$. Ya hemos visto que $$|\Omega_{n,k,i}|=\binom{i-1}{k-1} \binom{n}{i} \tag{3}$$ Porque de $(2c)$ $$\Omega_{n,k,i} \cap \Omega_{n,k,j} = \emptyset, \; \; \forall i \ne j \tag{4}$$

Definimos $$\Omega_{n,k}'' = \cup_{i=k+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ y $$\Omega_{n,k}' = \cup_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \Omega_{n,k,i}$$ y $$\Omega_{n,k} = \cup_{i=k}^{n} \Omega_{n,k,i}= \Omega_{n,k}'' \cup \Omega_{n,k}'$$

Se desprende de lo $(4)$ $(3)$ que $$|\Omega_{n,k}''| = \sum_{i=k+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$ un $$|\Omega_{n,k}'| = \sum_{i=k+1+2t , i \le n,t \in \mathbb{N_0}} \binom{i-1}{k-1} \binom{n}{i}$$

Así que para demostrar $(1)$ tenemos que demostrar que hay un bijection $\phi$ a partir de $\Omega_{n,k}'' \backslash \{\text{one element}\}$ $\Omega_{n,k}'$. Deje $\omega=\{A_1,\ldots, A_k\}$ un elemento de $\Omega_{n,k}$.

• Si $n \notin A_k$ definimos $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \cup \{n\} \}$
• Si $n \in A_k$ $ A_k \ne \{n\}$ definimos $\phi(\{A_1,\ldots, A_{k-1}, A_k\})=\{A_1,\ldots, A_{k-1}, A_k \backslash \{n\} \}$

$\phi$ definido hasta ahora es un bijection de $\Omega_{n,k}'' \backslash \Theta_k $ a $\Omega_{n,k}' \backslash \Theta_k $. $\Theta_k $ es $\{A_1,\ldots, A_{k-1}, \{n\} \}$

Pero si $\omega \in \Theta_n$ no es un problema. $A_k \backslash \{n\}= \emptyset$ $\{A_1,\ldots, A_{k-1}, \emptyset \} $ no $\Omega_{n,k}$. ¿Cómo podemos extender $\phi$$\Theta_k$?

De forma recursiva!

• Si $n-1 \notin A_{k-1}$ definimos $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2}, A_{k-1}\cup \{n-1\}, \{n\} \}$
• Si $n-1 \in A_{k-1}$ $ A_{k-1} \ne \{n-1\}$ definimos $\phi(\{A_1,\ldots, A_{k-2}, A_{k-1}, \{n\} \})=\{A_1,\ldots, A_{k-2} , A_{k-1} \backslash \{n-1\} , \{n\} \}$

Ahora hemos ampliado $\phi$$\Theta_n \backslash \Theta_{n-1}$. Este proceso puede continuar. Finalmente, llegamos a la siguiente definición para $\phi$:

Para $\{A_1,\ldots, A_r\}, \;A_j \ne \{n-j\}, \; A_{r-t}=\{n-t\}, t=0,\ldots,j-1$ definimos

• $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \cup \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ si $\{n-j\} \notin A_j $
• $\phi(\{A_1,\ldots, A_r\})=\{A_1,\ldots, A_{j-1},A_j \backslash \{n-j\},\{n-j+1\},\ldots,\{n\}\}$ si $\{n-j\} \in A_j $

$\phi$ no está definida para $\{\{n-k+1\},\ldots,\{n\}\}$ pero es un bijection de$\Omega_{n,k}'' \backslash \{\{n-k+1\},\ldots,\{n\}\}$$\Omega_{n,k}'$. Por lo tanto, $(1)$ mantiene.

un ejemplo

Para $n=5$, $k=3$ obtenemos la siguiente asignación de $\phi$

$$ \begin{array}{l|l} \hline{} \\ \omega & \phi(\omega) \\ \hline{} \\ \Omega_{5,3,3} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1\}\;\{2\}\;\{3\} & \{1\}\;\{2\}\;\{3,5\}\\ \{1\}\;\{2\}\;\{4\} & \{1\}\;\{2\}\;\{4,5\}\\ \{1\}\;\{2\}\;\{5\} & \{1\}\;\{2,4\}\;\{5\}\\ \{1\}\;\{3\}\;\{4\} & \{1\}\;\{3\}\;\{4,5\}\\ \{1\}\;\{3\}\;\{5\} & \{1\}\;\{3,4\}\;\{5\}\\ \{1\}\;\{4\}\;\{5\} & \{1,3\}\;\{4\}\;\{5\}\\ \{2\}\;\{3\}\;\{4\} & \{2\}\;\{3\}\;\{4,5\}\\ \{2\}\;\{3\}\;\{5\} & \{2\}\;\{3,4\}\;\{5\}\\ \{2\}\;\{4\}\;\{5\} & \{2,3\}\;\{4\}\;\{5\}\\ \{3\}\;\{4\}\;\{5\} & \text{no image} \\ \hline{} \\ \Omega_{5,3,4} \subset \Omega_{5,3}' & \subset \Omega_{5,3}'' \\ \hline{} \\ \{1\}\;\{2\}\;\{3,4\} & \{1\}\;\{2\}\;\{3,4,5\} \\ \{1\}\;\{2,3\}\;\{4\} & \{1\}\;\{2,3\}\;\{4,5\} \\ \{1,2\}\;\{3\}\;\{4\} & \{1,2\}\;\{3\}\;\{4,5\} \\ \{1\}\;\{2\}\;\{3,5\} & \{1\}\;\{2\}\;\{3\} \\ \{1\}\;\{2,3\}\;\{5\} & \{1\}\;\{2,3,4\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{5\} & \{1,2\}\;\{3,4\}\;\{5\} \\ \{1\}\;\{2\}\;\{4,5\} & \{1\}\;\{2\}\;\{4\} \\ \{1\}\;\{2,4\}\;\{5\} & \{1\}\;\{2\}\;\{5\} \\ \{1,2\}\;\{4\}\;\{5\} & \{1,2,3\}\;\{4\}\;\{5\} \\ \{1\}\;\{3\}\;\{4,5\} & \{1\}\;\{3\}\;\{4\} \\ \{1\}\;\{3,4\}\;\{5\} & \{1\}\;\{3\}\;\{5\} \\ \{1,3\}\;\{4\}\;\{5\} & \{1\}\;\{4\}\;\{5\} \\ \{2\}\;\{3\}\;\{4,5\} & \{2\}\;\{3\}\;\{4\} \\ \{2\}\;\{3,4\}\;\{5\} & \{2\}\;\{3\}\;\{5\} \\ \{2,3\}\;\{4\}\;\{5\} & \{2\}\;\{4\}\;\{5\} \\ \hline{} \\ \Omega_{5,3,5} \subset \Omega_{5,3}'' & \subset \Omega_{5,3}' \\ \hline{} \\ \{1,2,3\}\;\{4\}\;\{5\} & \{1,2\}\;\{4\}\;\{5\} \\ \{1,2\}\;\{3,4\}\;\{5\} & \{1,2\}\;\{3\}\;\{5\} \\ \{1,2\}\;\{3\}\;\{4,5\} & \{1,2\}\;\{3\}\;\{4\} \\ \{1\}\;\{2,3,4\}\;\{5\} & \{1\}\;\{2,3\}\;\{5\} \\ \{1\}\;\{2,3\}\;\{4,5\} & \{1\}\;\{2,3\}\;\{4\} \\ \{1\}\;\{2\}\;\{3,4,5\} & \{1\}\;\{2\}\;\{3,4\} \\ \hline{} \end{array} $$

Answer 4

Aquí hay otra prueba de álgebra. Observar que cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\elegir k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ es decir, el producto de las dos funciones de generación es la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

La suma que estamos tratando de evaluar es $$\sum_{k=j}^n (-1)^{k-j} {k\elegir j} {n+1\elegir k+1} = (n+1) \sum_{k=j}^n \frac{(-1)^{k-j}}{k+1} {k\elegir j} {n\elegir k}.$$ Ahora vamos $$A_1(z) = \sum_{k\ge 0} (-1)^{k-j} {k\elegir j} \frac{z^k}{k!} = \frac{1}{j!} \sum_{k\ge j} (-1)^{k-j} \frac{z^k}{(k-j)!} \\= \frac{1}{j!} z^j \sum_{k\ge j} (-1)^{k-j} \frac{z^{k-j}}{(k-j)!} = \frac{1}{j!} z^j \exp(-z).$$ A continuación, se deduce que $$ A(z) = \sum_{k\ge 0} \frac{(-1)^k}{k+1} {k\elegir j} \frac{z^k}{k!} = \frac{1}{z} \left(C + \int A_1(z) dz\right)$$ con $C$ una constante a determinar.

Ahora no es difícil demostrar (consulte el final de este post) que $$\int A_1(z) dz = -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}$$ y debemos tener $$C = -[z^0] \left(-\exp(-z) \sum_{q=0}^j \frac{z^q}{q!} \right)= 1$$ así que $$A(z) = \frac{1}{z} \left(1 -\exp(-z) \sum_{q=0}^j \frac{z^q}{q!}\right).$$ Ahora hemos determinado $A(z)$ para la convolución de las dos funciones de generación.

Tomamos $$B(z) = \sum_{k\ge 0} \frac{z^k}{k!} = \exp(z).$$ De ello se sigue que $$A(z) B(z) = \frac{1}{z} \left(\exp(z) - \sum_{q=0}^j \frac{z^p}{q!}\a la derecha).$$ Ahora aplicando el coeficiente de operador de extracción obtenemos $n\ge j$ que $$(n+1) n! [z^n] A(z) B(z) = (n+1)! [z^{n+1}] \left(\exp(z) - \sum_{q=0}^j \frac{z^p}{q!}\a la derecha).$$ Ninguno de los términos de la suma a contribuir, porque $n+1>j$ lo que nos deja con $$(n+1)! [z^{n+1}] \exp(z) = (n+1)! \frac{1}{(n+1)!} = 1.$$

La verificación. $$\left(-\exp(-z) \sum_{q=0}^j \frac{z^p}{q!}\right)' = \exp(-z) \sum_{q=0}^j \frac{z^p}{q!} - \exp(-z) \sum_{q=0}^{j-1} \frac{z^p}{q!} = \exp(-z) \frac{z^j}{j!}.$$

Answer 5

Wolfram Alpha rendimientos de este resultado:

Es aquí !!!

Es demasiado malo para Wolfram Alpha que ${\bf they\ don't\ say}$ que el lado derecho es idéntico a $\color{#0000ff}{\large\mbox{ONE}\ = 1}$.