Interpretación combinatoria de la identidad: $\sum\limits_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$

Question

Actualmente, estoy tratando de probar las siguientes dos identidades, que surgieron como resultado de mi otra pregunta en el StackExchange de matemáticas recientemente:

\begin {Ecuación} \sum_ {j=0}^b \binom {b}{j}^2 \binom {n+j}{2b}= \binom {n}{b}^2 \end {Ecuación}

\begin {Ecuación} \sum_ {j=0}^b(-1)^j \binom {b}{j} \binom {n+j}{2b} = \left (-1 \right )^b \binom {n}{b} \end {Ecuación}

En particular, la primera identidad apareció como una observación en el volumen 4 de las Identidades Combinatorias de Henry Gould.

Por curiosidad, me pregunto si existe una prueba combinatoria para alguna de estas dos identidades.

EDIT: He conseguido demostrar la segunda identidad, considerando el coeficiente de $x^{n-b}$ en la expansión de $(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$ .

EDIT 2: También he conseguido encontrar una prueba para la primera identidad utilizando la identidad de Vandermonde. Sin embargo, me interesaría una prueba de la segunda identidad utilizando un enfoque más combinatorio.

Answer 1

La primera identidad es el caso particular (para $a=b$ y $x=n$ ) de la identidad $$ \sum_{i=0}^b \dbinom{a}{i} \dbinom{b}{i} \dbinom{x+i}{a+b} = \dbinom{x}{a} \dbinom{x}{b} , $$ que ha aparecido en math.stackexchange pregunta #280481 . Para las pruebas combinatorias, véase

• George E. Andrews, Identidades en combinatoria, I: sobre la clasificación de dos conjuntos ordenados Discrete Mathematics, Volumen 11, Número 2, 1975, Páginas 97--106 .

• George E. Andrews, David M. Bressoud, Identidades en combinatoria III: Otros aspectos de la ordenación de conjuntos ordenados Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236 .

También doy una prueba algebraica en la Proposición 3.39 (f) de mi Notas sobre los fundamentos combinatorios del álgebra (busque "surtido de otras identidades" si la numeración ha cambiado, o bien mire el versión archivada del 10 de enero de 2019 ).

---

La segunda identidad es el caso particular (para $d=2b$ ) de la siguiente identidad: $$ \sum_{j=0}^b \left(-1\right)^j \dbinom{b}{j} \dbinom{n+j}{d} = \left(-1\right)^b \dbinom{n}{d-b} , $$ donde $d$ y $b$ son dos enteros no negativos y $n$ es un número arbitrario (por ejemplo, racional). Esto se puede demostrar fácilmente por inducción sobre $b$ . Alternativamente, uno puede WLOG asumir que $n \in \left\{d, d+1, d+2, \ldots\right\}$ y luego aplicar algo de simetría y negación superior para reducirlo a la convolución de Vandermonde. Para otra prueba, intente usar diferencias finitas (las ideas necesarias están en la respuesta de Marc van Leeuwen https://math.stackexchange.com/a/381939/ ). Esto no da una prueba combinatoria, pero me hace sospechar que es conocido, y ojalá alguien ha reunido pruebas combinatorias de tales identidades.

Answer 2

Prueba combinatoria de la segunda identidad

Dejemos que $B$ ser un $b$ -conjunto de elementos y dejar que $N$ ser un $n$ -conjunto de elementos disjuntos a $B$ .

La suma $\sum_j\binom b{b-j}\binom{n+j}{2b}$ cuenta el número de pares de conjuntos $T\subset B$ , $X\subset N\cup B$ s.t. $|X|=2b$ y $X\cap T=\varnothing$ . (De hecho, un sumando corresponde a la elección de la primera $(b-j)$ -conjunto de elementos $T\subset B$ y luego $2b$ -conjunto de elementos $X\subset N\cup(B\setminus T)$ .) Y el LHS cuenta tales pares con signos $(-1)^{|B \setminus T|}$ .

Ahora hay una involución de signo inverso: encuentra el elemento más pequeño de $B\setminus X$ y luego añadirlo a $T$ si no está ya en $T$ Si no es así, elimínelo de $T$ . Así que en el LHS todo lo que no está vacío $B\setminus X$ se anula; y hay exactamente $\binom nb$ variantes con $X\supset B$ y se cuentan con signo $(-1)^b$ .

(Y la RHS lo es, de hecho, $(-1)^b\binom nb$ .)

Answer 3

A modo de enriquecimiento, permítanme presentar una prueba algebraica.

Supongamos que buscamos verificar que $$\sum_{j=0}^b {b\choose j}^2 {n+j\choose 2b} = {n\choose b}^2.$$ donde $0\le b\le n.$

Introduzca $${b\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b-j+1}} \frac{1}{(1-z)^{j+1}} \; dz$$

y $${n+j\choose 2b} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2b+1}} (1+w)^{n+j} \; dw.$$

Esto da como resultado para la suma $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{1-z} \sum_{j=0}^b {b\choose j} (1+w)^j \frac{z^j}{(1-z)^j} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{1-z} \left(1+\frac{(1+w)z}{1-z}\right)^b \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{(1-z)^{b+1}} (1+wz)^b \; dz \; dw.$$

El residuo interior es $$\sum_{q=0}^b {b\choose q} w^q {b-q+b\choose b}.$$ Sustituyendo esto en la integral exterior se obtiene $$\sum_{q=0}^b {b\choose q} {2b-q\choose b} {n\choose 2b-q}.$$

Observe que $${2b-q\choose b}{n\choose 2b-q} = \frac{(2b-q)!}{b! (b-q)!}\frac{n!}{(2b-q)! (n-2b+q)!} \\ = \frac{(n-b)!}{b! (b-q)!}\frac{n!}{(n-b)! (n-2b+q)!} = {n\choose b} {n-b\choose b-q}.$$

Esto da como resultado para la suma $${n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose b-q}.$$

que se evalúa como $${n\choose b}^2$$ mediante una inspección.

También se puede hacer con la integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b-q+1}} (1+z)^{n-b} \; dz$$

que da como resultado $${n\choose b} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} (1+z)^{n-b} \sum_{q=0}^b {b\choose q} z^q \; dz \\ = {n\choose b} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} (1+z)^{n} \; dz = {n\choose b}^2.$$