Interpretación combinatoria para la identidad ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

Question

Interpretación combinatoria para la identidad ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

suma
Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

binomio

Una identidad conocida de los coeficientes binomiales es que

\sum_{i} (\binom{metro}{i}) (\binom{norte}{j - i}) = (\binom{metro + norte}{j}) .

$\sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}.$ ¿Hay una prueba/explicación combinatoria de por qué se cumple? Gracias.

Martín Sleziak

Esta es la identidad de Vandermonde . Se proporciona una prueba combinatoria en wikipedia y en proofwiki . Consulte también esta pregunta: math.stackexchange.com/questions/76819

André Nicolás

Tenemos

m

$m$ marcianos y

n

$n$ neptunianos, y desea seleccionar una tripulación de

j

$j$ "gente". El lado derecho da el número de formas. Lo mismo ocurre con el lado izquierdo, ya que podemos elegir

0

$0$ marcianos y

j

$j$ neptunianos, o

1

$1$ marciano y

j - 1

$j-1$ neptunianos o

\dots

$\dots$ .

joriki

Cualquiera de los dos podría publicarse como respuesta.

Respuestas (2)

Interpretación combinatoria para la identidad ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

Esta es la identidad de Vandermonde . Se proporciona una prueba combinatoria en wikipedia y en proofwiki . Consulte también esta pregunta: math.stackexchange.com/questions/76819
Tenemos $m$ marcianos y $n$ neptunianos, y desea seleccionar una tripulación de $j$ "gente". El lado derecho da el número de formas. Lo mismo ocurre con el lado izquierdo, ya que podemos elegir $0$ marcianos y $j$ neptunianos, o $1$ marciano y $j-1$ neptunianos o $\dots$ .

André Nicolás · Answer 1

El capitán de la nave pirata Free Enterprise encuentra $m$ marcianos y $n$ Neptunianos en un bar. ¿De cuántas maneras puede seleccionar una tripulación de $j$ criaturas para una incursión en Júpiter?

El lado derecho $\binom{m+n}{j}$ cuenta el número de formas de seleccionar $j$ criaturas de la $m+n$ criaturas disponibles.

Lo mismo ocurre con el lado izquierdo. Porque ella podría seleccionar $0$ marcianos y $j$ neptunianos. Esto se puede hacer en $\binom{m}{0}\binom{n}{j}$ maneras.

O bien podría seleccionar $1$ marciano y $j-1$ neptunianos. Esto se puede hacer en $\binom{m}{1}\binom{n}{j-1}$ maneras.

O bien podría seleccionar $2$ marcianos y $j-2$ neptunianos. Esto se puede hacer en $\binom{m}{2}\binom{n}{j-2}$ maneras.

Etcétera. Por lo tanto, el número de formas de reclutar $j$ criaturas viene dada por la suma del lado izquierdo.

Comentario: El resultado y el razonamiento siguen siendo correctos incluso si, por ejemplo, $j>n$ . Todo lo que tenemos que hacer es definir $\binom{u}{v}$ ser $0$ si $u<v$ .

Rohan Shinde · Answer 2

Lo que necesitas probar es la identidad de Vandermonde.

La identidad de Vandermonde afirma que $\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r$ , que se puede probar combinatoriamente al notar que cualquier combinación de $r$ objetos de un grupo de $m+n$ los objetos deben tener alguna $0\le k\le r$ objetos del grupo $m$ y el resto del grupo $n$ .

Interpretación combinatoria para la identidad ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

binomio

Martín Sleziak

André Nicolás

joriki

Respuestas (2)

André Nicolás

Rohan Shinde

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 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

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

Demuestra que para r,n∈Nr,n∈Nr,n \in \mathbb{N} con r≥nr≥nr \geq n, ∑n−1i=0(−1)i(ni)(r+n− i−1r)=(r−1n−1)∑i=0n−1(−1)i(ni)(r+n−i−1r)=(r−1n−1)\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i} \binom{r+ni-1}{r} = \binom{r-1}{n-1}

Simplificando el producto de múltiples expansiones binomiales

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Prueba combinatoria sobre factoriales decrecientes y sumas de factoriales decrecientes

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