Probar identidades como $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

Question

Tengo que dar una combinatoria prueba de

$$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$

Me parece difícil de resolver esos problemas. Yo no soy una persona brillante y nunca lo va a ser, así que necesita tener algoritmos para solucionar la mayoría de problemas. Por lo general, no sólo "ver" las soluciones a menos que tenga un profundo suficiente comprensión de una teoría. Este también es el caso aquí. Yo sé lo que los símbolos significan, pero no veo lo que debo contar y cómo obtener la identidad.

Creo que el lado derecho de la cuenta $n$-elemento de subconjuntos de a $(2n-1)$-elemento de conjunto con un solo elemento elegido para ser "especial". Creo que debo encontrar una partición del conjunto de los subconjuntos de a $n$ partes, de manera que el lado izquierdo es la suma de las cardinalidades de las partes. Hay $n$ de la nada en el lado derecho? Bueno, hay $n$ opciones para el "especial" de los elementos, pero sólo después de que he elegido el $n$-elemento del subconjunto. De lo contrario puede elegir el "elemento" en $2n-1$ maneras.

Esta es una tarea problema por lo que yo probablemente no debería pedir una solución completa. Pero me gustaría tener algunas pautas para abordar este tipo de problemas, tal vez con base en este ejemplo.

Answer 1

Parece más fácil mirar en el lado izquierdo :

$\sum \binom n k ^2 = \binom {2n} n$ es el número de formas de elegir los $n$ elementos de un conjunto $X$ $2n$ elementos, donde se da una partición de $X = X_1 \cup X_2$$\# X_i = n$.
Siguiente, $\sum k \binom n k ^2$ es el número de maneras de hacer esto y, a continuación, elija un elemento especial entre los elegidos en $X_1$. Así, invirtiendo el orden de las opciones (seleccione el elemento especial la primera), luego olvidar tanto como sea posible acerca de la partición, se obtiene que es el número de formas de seleccionar un elemento especial en $X_1$ y, a continuación, recoger $n-1$ otros elementos en $X$.

A continuación, que no debería ser demasiado difícil de explicar por qué esto es igual para el lado derecho.

Answer 2

Desde $\binom{n}{k} = \dfrac{n}{k}\binom{n-1}{k-1}$ la identidad puede ser escrito como $$\sum_{k=1}^n\binom{n}{n-k}\binom{n-1}{k-1} = \binom{2n-1}{n-1}.$$

Supongamos que tenemos $2n-1$ artículos en línea y tenemos que elegir el $n-1$ artículos de ellos. El lado derecho es el número de maneras de hacer esto de una manera obvia. Otra manera de elegir nuestra $n-1$ elementos de esta línea: Dividir la línea en dos secciones; la primera sección contiene la primera $n$ elementos, el segundo contiene la última $n-1$ artículos. A la hora de recoger $n-1$ elementos de toda la línea, se podría recoger todas $n-1$ desde la primera línea y ninguno en el segundo ( $k=1$ ) o $n-2$ desde la primera línea y $1$ a partir del segundo ($k=2$) ... ... o ninguno de la primera línea y $n-1$ a partir del segundo ($k=n$).

Answer 3

$a,b,n \in \mathbb{N}$ Tenemos

$$\binom{a+b}{n} = \sum_{p+q=n} \binom{a}{p} \cdot \binom{b}{q}$$

puesto que ambos lados contar los subconjuntos de $\{1,\dotsc,a\} \sqcup \{1,\dotsc,b\}$ $n$ elementos. Esto podría también derivar el isomorfismo $\Lambda^n(V \oplus W) = \bigoplus_{p+q=n} \Lambda^p(V) \otimes \Lambda^q(W)$ de los poderes exteriores, donde $V,W$ son módulos libres de fila $a$y $b$ (decategorification).

En particular,

$$\sum_{k=0}^{n} k \binom{n}{k}^2 = n \sum_{k=0}^{n} \binom{n}{n-k} \binom{n-1}{k-1}=n \binom{2n-1}{n-1}=n \binom{2n-1}{n}.$$

Uno puede también derivar muchas otras fórmulas como un caso especial, por ejemplo

$$\sum_{k=0}^{n} \binom{n}{k}^2 = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \binom{2n}{n}.$$

Answer 4

$\newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert}$ $\ds{\sum_{k = 1}^{n}k{n \choose k}^{2} = n{2n - 1 \choose n}:\ {\large ?}}$

\begin{align}&\sum_{k = 1}^{n}k{n \choose k}^{2} =\sum_{k = 1}^{n}k{n \choose k}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z}\sum_{k = 1}^{n}k{n \choose k}\pars{1 \over z}^{k} \,{\dd z \over 2\pi\ic} \end{align}

Tenga en cuenta que $\ds{\sum_{k = 1}^{n}k{n \elegir k}^{k} =a\,\partiald{}{a}\sum_{k = 0}^{n}{n \elegir k}^{k} =a\,\partiald{\pars{1 + a}^{n}}{un} = na\pars{1 + a}^{n - 1}}$ tal que

\begin{align} &\color{#66f}{\large\sum_{k = 1}^{n}k{n \choose k}^{2}} =\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z}\bracks{n\,{1 \over z}\,\pars{1 + {1 \over z}}^{n - 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=n\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n - 1} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} =\color{#66f}{\large n{2n - 1 \choose n}} \end{align}