Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Question

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

Yoshi

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

\sum_{j = 0}^{b} {(\binom{b}{j})}^{2} (\binom{norte + j}{2 b}) = {(\binom{norte}{b})}^{2}

$\begin{equation} \sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2 \end{equation}$

\sum_{j = 0}^{b} (- 1)^{j} (\binom{b}{j}) (\binom{norte + j}{2 b}) = {(- 1)}^{b} (\binom{norte}{b})

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

En particular, la primera identidad apareció como un comentario en el Volumen 4 de Combinatorial Identities de Henry Gould.

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

EDITAR: He logrado probar 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 logré encontrar una prueba para la primera identidad usando la identidad de Vandermonde. Sin embargo, todavía estaría interesado en una prueba de la segunda identidad utilizando un enfoque más combinatorio.

marco m

No estoy seguro de si esto va a alguna parte, pero en la primera identidad, el RHS es la cantidad de formas de elegir dos subconjuntos de

{1, 2, \dots, n}

$\{ 1,2, \ldots , n \}$ con

b

$b$ elementos. Estaba tratando de encontrar una biyección para llegar al LHS; mi intuición es que tal vez el

j

$j$ en el LHS representa la cantidad de elementos que los dos conjuntos tienen en común, pero no pude llegar a ninguna parte con eso.

Respuestas (2)

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

No estoy seguro de si esto va a alguna parte, pero en la primera identidad, el RHS es la cantidad de formas de elegir dos subconjuntos de $\{ 1,2, \ldots , n \}$ con $b$ elementos. Estaba tratando de encontrar una biyección para llegar al LHS; mi intuición es que tal vez el $j$ en el LHS representa la cantidad de elementos que los dos conjuntos tienen en común, pero no pude llegar a ninguna parte con eso.

Darij Grinberg · Answer 1

La primera identidad es el caso particular (por $a=b$ y $x=n$ ) de la identidad

\sum_{i = 0}^{b} (\binom{a}{i}) (\binom{b}{i}) (\binom{X + i}{a + b}) = (\binom{X}{a}) (\binom{X}{b}),

$\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 la pregunta #280481 de math.stackexchange . Para demostraciones combinatorias, véase

George E. Andrews, Identidades en combinatoria, I: sobre la clasificación de dos conjuntos ordenados , Matemáticas discretas, volumen 11, número 2, 1975, páginas 97-106 .
George E. Andrews, David M. Bressoud, Identidades en combinatoria III: Otros aspectos de la clasificación de conjuntos ordenados , Matemáticas discretas, volumen 49, número 3, mayo de 1984, páginas 223-236 .

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

La segunda identidad es el caso particular (por $d=2b$ ) de la siguiente identidad:

\sum_{j = 0}^{b} {(- 1)}^{j} (\binom{b}{j}) (\binom{norte + j}{d}) = {(- 1)}^{b} (\binom{norte}{d - b}),

$\sum_{j=0}^b \left(-1\right)^j \dbinom{b}{j} \dbinom{n+j}{d} = \left(-1\right)^b \dbinom{n}{d-b} ,$ dónde

d

$d$ y

b

$b$ son dos enteros no negativos y

n

$n$ es un número arbitrario (por ejemplo, racional). Esto se puede probar fácilmente por inducción sobre

b

$b$ . Alternativamente, WLOG puede suponer que

n \in {d, d + 1, d + 2, \dots}

$n \in \left\{d, d+1, d+2, \ldots\right\}$ , y luego aplique algo de simetría y negación superior para reducirlo a la convolución de Vandermonde. Para otra prueba más, intente usar diferencias finitas (las ideas necesarias están en la respuesta de Marc van Leeuwen https://math.stackexchange.com/a/381939/ ). Esto no proporciona una prueba combinatoria, pero me hace sospechar que es bien conocido y, con suerte, alguien ha recopilado pruebas combinatorias de tales identidades.

(+1). Las referencias y observaciones son una buena mejora de la página.

grigorio m · Answer 2

Prueba combinatoria de la segunda identidad

Dejar $B$ ser un $b$ -conjunto de elementos y let $N$ frijol $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$ calle $|X|=2b$ y $X\cap T=\varnothing$ . (De hecho, un sumando corresponde a elegir primero $(b-j)$ -conjunto de elementos $T\subset B$ y luego $2b$ -conjunto de elementos $X\subset N\cup(B\setminus T)$ .) Y LHS cuenta tales pares con signos $(-1)^{|B \setminus T|}$ .

Ahora hay una involución que invierte el signo: encuentre el elemento más pequeño de $B\setminus X$ y luego agregarlo a $T$ si no está ya en $T$ , de lo contrario eliminarlo de $T$ . Entonces en LHS todo con no vacío $B\setminus X$ cancela; y hay exactamente $\binom nb$ variantes con $X\supset B$ y se cuentan con signo $(-1)^b$ .

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

Supongo que este argumento también se aplica a la generalización $\sum\limits_{j=0}^b \left(-1\right)^j \dbinom{b}{j} \dbinom{n+j}{d} = \left(-1\right)^b \dbinom{n}{d-b}$ ?

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Yoshi

marco m

Respuestas (2)

Darij Grinberg

Marko Riedel

grigorio m

Prueba combinatoria de la segunda identidad

Darij Grinberg

grigorio m

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Cómo probar que (nr)(nr)n \choose r = n+1−rrn+1−rr\frac{n+1-r}{r} (nr−1)(nr−1)n \choose r -1 sin usar la expansión factorial de (nr)(nr)n \choose r? [cerrado]

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Prueba combinatoria de identidad de tipo binomial

Verificación de la solución: Demuestre que ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an− i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} para n ≥1n≥1n\geq 1

Prueba combinatoria de ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Prueba combinatoria y algebraica de una identidad que implica números de Stirling de segunda clase {n+1k+1}=∑i(ni){ik}{n+1k+1}=∑i(ni){ik}{n+1 \brace k+1}=\sum_i \binom{n}{i}{i\brace k}

Explicación combinatoria de por qué n2=(n2)+(n+12)n2=(n2)+(n+12)n^2 = {n \elegir 2} + {n+1 \elegir 2}