Prueba combinatoria de$\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}} = {{n+p} \choose p}^2$

Question

(Valido para $n\geq p \geq 1$)

Básicamente, me gustaría exhibir dos conjuntos, uno con cardinalidad${{n+p} \choose p}^2$, otro con cardinalidad$\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}}$ y encontrar una biyección entre los dos.

Definiendo$C_{k}^{n}$ como los subconjuntos de$\left \{ 1,...,n \right \}$ con cardinalidad k, está claro que$(C_{p}^{n+p})^{2}$ tiene una cardinalidad de${{n+p} \choose p}^2$, y que$\bigcup_{k=0}^{p}\left ( (C_{k}^{p})^2 \times C_{2p}^{n+2p-k}\right )$ tiene una cardinalidad de$\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}}$, pero no puedo encontrar una biyección entre los dos conjuntos.

Answer 1

El lado derecho cuenta el número de formas de elegir los dos subconjuntos $A,B$$[n+p]$, de tamaño $p$ cada uno. Deje $t = |A \cap B|$, y escribir el $2p-t$ elementos de $A \cup B$ en la secuencia: $\vec{x} = x_1,\ldots,x_{2p-t}$. Supongamos que entre los primeros a $p$ elementos, $p-k$ elementos pertenecen a $A$, que forman un conjunto $A'$, de los cuales, $\ell$ pertenecen también a $B$, a decir de posiciones $i_1,\ldots,i_\ell$ dentro $A'$. Añadimos los elementos $n+p+i_1,\ldots,n+p+i_\ell$$\vec{x}$. Entre las $p-t$ elementos $x_{p+1},\ldots,x_{2p-t}$, $p-k-\ell$ elementos que pertenecen a $B$, que forman un conjunto $B'$, de los cuales, $t-\ell$ pertenecen también a $A$, a decir de posiciones $j_1,\ldots,j_{\ell-t}$ dentro $B'$. Añadimos los elementos de número de $j_1,\ldots,j_{\ell-t}$ $\{n+p+1,\ldots,n+2p-t\} \setminus \{n+p+i_1,\ldots,n+p+i_\ell\}$ a $\vec{x}$.

Después de que todas las adiciones, $\vec{x}$ se compone de $2p$ índices en $[n+2p-t]$. Con el fin de decodificar $\vec{x}$ a $A,B$, necesitamos alguna información adicional. En primer lugar, necesitamos saber que $p-k$ $x_1,\ldots,x_p$ pertenecen a $A$. En segundo lugar, debemos saber que $p-k$ $x_{p+1},\ldots,x_{2p}$ pertenecen a $B$; un elemento seleccionado más allá de $[n+p]$ indica un elemento de $B$ que proviene de $A'$, y un no-elegido elemento más allá de $[n+p]$ indica un elemento de $A$ que la que viene de $B'$. Hemos llegado a la mano izquierda.

La confusa lector podría considerar las siguientes simple identidad en primer lugar: $$ \sum_{k=0}^p \binom{p}{k}^2 \binom{n+p}{2} = \binom{n+p}{p} \binom{n}{p}. $$ El lado derecho cuenta el número de formas de elegir los dos distintos subconjuntos $A,B$$[n+p]$, cada uno de tamaño $p$. Dada la $2p$ elementos $x_1,\ldots,x_{2p}$$A \cup B$$k := |\{x_1,\ldots,x_p\} \cap B|$, podemos decodificar $A,B$ $\{x_1,\ldots,x_p\} \cap A$ (codificado como un subconjunto de a $[p]$ del tamaño de la $p-k$) y $\{x_{p+1},\ldots,x_{2p} \cap B$ (codificado como un subconjunto de a $[p]$ del tamaño de la $p-k$).

Answer 2

Durante el transcurso de esta prueba me encontré con que uno puede, de hecho, muestran el resultado general más $$\sum_{k=0}^q {l+q\choose k}{p\choose q-k}{n+l+p+k\choose l+p+q}={n+l+p\choose l+p}{n+l+q\choose q}$$ a partir de la cual el resultado original de la siguiente manera mediante el establecimiento $l=0$$p=q$.

Podemos mostrar esta contando el número de maneras para formar un Comité General (GC) y un Comité de Mujeres (WC) de un grupo de $l+q$ hombres y $n+l+p$ mujeres, con las limitaciones que no son sólo las mujeres en el WC y que no son exactamente $l+p$ de las mujeres en el WC, y que la GC tiene exactamente $q$ de los miembros.

En primer lugar, podemos simplemente elija $l+p$ a las mujeres a estar en el WC en ${n+l+p\choose l+p}$ caminos; entonces podemos optar $q$ desde el resto de $n$ mujeres y $l+q$ a los hombres a estar en el GC en ${n+l+q\choose q}$ maneras. Por lo tanto, hay ${n+l+p\choose l+p}{n+l+q\choose q}$ maneras de formar los comités.

Que en lugar de especificar cómo muchas de las $p$ más antiguas de las mujeres en los comités están en el WC. Llame a este número $q-k$. Podemos elegir cual de las $p$ más antiguas de las mujeres en los comités están en el WC en ${p\choose q-k}$ maneras.

Aviso de que no va a ser $l+p+q$ total de personas en los comités. Ahora tenemos que decidir qué personas están en un comité, y que de las mujeres más jóvenes (entre los p mayor) en los comités están en el WC y vamos a tener especificado nuestros comités (ya que los hombres en los comités deben estar en el GC).

Asociado con cada hombre una clara ticket con un número entre el$1$$l+q$, y elija $k$ de estas entradas (en ${l+q\choose k}$ formas). Colocar en un balde con los nombres de cada una de las mujeres y elija $l+p+q$ desde el cubo a estar en un comité (en ${n+l+p+k\choose l+p+q}$ formas). Los hombres asociados con las entradas saldrán a la GC. Borrar el número en cada uno elegido de entradas y de cambio de los números en todos los boletos con un número mayor. Vamos a decidir que el comité de cada una de las mujeres escogidas son sobre el uso de la unchosen entradas.

Sabemos que el comité de cada una de las $p$ más antiguas de las mujeres en la elección de tres párrafos atrás. Ahora, por cada boleto a la izquierda en la cubeta de la mano el billete con la etiqueta $i$ $i$th mujer más joven, cuyo nombre fue elegido. Las mujeres con las entradas están a la DUCHA, y el resto (que no están entre los $p$ más antiguo) en el GC. Por lo tanto, cada comité está especificado, y hay $${l+q\choose k}{p\choose q-k}{n+l+p+k\choose l+p+q}$$ maneras para formar con ellos para un determinado $k$.

Algunos justificación para que el último párrafo: en Primer lugar tenga en cuenta que no hay manera de que uno de los $p$ más antiguas de las mujeres en los comités para recibir un boleto (por lo que no pueden recibir conflicto de tareas). Porque de la manera que se desplaza hacia abajo de las entradas, el número más grande que puede haber en un unchosen billete es $l+q-j$ donde $j$ es el número de entradas. Desde allí se $l+q-j+p$ mujeres elegidos, estos billetes no pueden ser entregados a la más antigua de $p$ (y, potencialmente, podría ser dado a cualquiera de las mujeres que no son los más antiguos de la $p$). Observe también que cada juego de $k-j$ boletos a la izquierda en el cubo de producir una clara elección de las mujeres para el WC; puesto que el $j$ boletos recogidos en el cubo también producen conjuntos distintos de los hombres para la GC, descubrimos que de hecho puede elegir cada uno de nuestros tres juegos de forma independiente. La correspondencia anterior también es exhaustiva; cualquier comité montaje de nuestras limitaciones, puede ser formado en una forma única de alguna elección de los billetes de poner en la cubeta, nombres extraídos de la cubeta, y las asignaciones para la $p$ más antiguas de las mujeres en los comités.

Suma más de $k$ nos da la identidad anterior. Puede ser escrito más útil: $$\sum_{k=0}^{q} {m\choose k}{p-m+q\choose q-k}{w+k\choose p+q}={w\choose p}{w-p+m\choose q}$$ (Me puede reescribir esta utilizando estas variables más tarde, ya que probablemente son más fáciles de entender.)