Suma de binomios con factor al cuadrado

Question

Cómo probar que $$ \sum_{k=0}^n k^2 {n \choose k}^2 = n^2 {2n-2 \choose n-1} $$ de forma combinatoria?

Answer 1

He aquí una prueba puramente combinatoria, que no utiliza preliminares algebraicos.

Usted tiene un grupo de $n$ hombres y $n$ mujeres. Quieres formar dos comités, uno de mujeres y otro de hombres, y nombrar a un presidente de cada comité; la única restricción es que los dos comités deben tener el mismo tamaño. ¿De qué manera se puede hacer esto?

Por un lado, podría decidir primero el tamaño de los comités. Supongamos que se decide un tamaño de $k$ ; hay $\binom{n}k$ formas de elegir el $k$ mujeres y $\binom{n}k$ formas de elegir el $k$ hombres. Una vez que haya elegido el $k$ miembros de cada comité, hay $k$ formas de elegir al presidente de la comisión de mujeres y $k$ formas de elegir al presidente del comité masculino. Así, hay en total $k^2\binom{n}k^2$ formas de elegir los comités de tamaño $k$ y elegir sus sillas, y sumar sobre $k$ da el total deseado: es

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

Como alternativa, puede empezar por seleccionar las dos sillas; evidentemente, esto puede hacerse en $n^2$ formas. Ahora viene la parte un poco complicada. Supongamos que elijo $n-1$ de la $2n-2$ las personas que quedan después de la selección de las sillas y me encuentro con que tengo $k$ mujeres en mi selección, algo que puedo hacer en $\binom{2n-2}{n-1}$ diferentes maneras. Entonces debo tener $n-1-k$ hombres en mi selección, así que debe haber $(n-1)-(n-1-k)=k$ hombres a los que he no seleccionado. El $k$ mujeres seleccionadas y el $k$ no seleccionado Los hombres serán los miembros no presidentes de los comités. De este modo, puedo conseguir todas las parejas posibles de comités de igual tamaño, por lo que hay

$$n^2\binom{2n-2}{n-1}$$

maneras de llevar a cabo la tarea, y se deduce que

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

Se puede dar un argumento combinatorio más fácil si aplicamos primero la misma manipulación inicial que hermes utilizado:

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

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

y podríamos simplificar la notación demostrando en su lugar que

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

Finalmente, podemos reescribir el lado izquierdo para hacer esto

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

Entonces hacemos el simple argumento combinatorio de que ambos lados son el número de formas de elegir un comité de $n$ personas de un grupo formado por $n$ hombres y $n$ mujeres; el lado izquierdo simplemente desglosa el recuento según el número $k$ de mujeres en el comité.

Answer 2

Tenga en cuenta que $$ k {n \choose k}=n{n-1\choose k-1} $$ Por lo tanto, $$ \sum_{k=0}^n k^2 {n \choose k}^2=n^2\sum_{k=1}^n {n-1 \choose k-1}^2=n^2\sum_{k=0}^{n-1} {n-1 \choose k}^2=n^2\sum_{k=0}^{n-1} {n-1 \choose k}{n-1 \choose n-k-1}=n^2 {2n-2 \choose n-1} $$ El último paso se obtiene comparando el término en $x^{n-1}$ en la expansión de $$ (1+x)^{n-1}(1+x)^{n-1}=(1+x)^{2n-2} $$

Answer 3

Me gusta mucho la prueba proporcionada por @hermes, pero en caso de que quieras una prueba combinatoria pura, aquí tienes una candidata basada en el análisis de hermes. Sea $S_n=\{1 \ldots n\}$ y definir $Z$ para ser el conjunto de cuartetos ordenados $(a,b,A,B)$ , donde $a,b \in S_n$ y $A,B \subseteq S_n$ Satisfaciendo a $a \in A$ , $b \in B$ y $|A| = |B|$ .

Para cualquier $k \in \{0 \ldots n\}$ Hay exactamente $k^2 {{n} \choose{k}}$ tales cuatrillizos que $|A| = |B| = k$ ; $n\choose k$ opciones para cada uno de $A$ y $B$ y luego $k$ opciones para cada uno de $a$ y $b$ . Así, $|Z| = \displaystyle \sum_{k=0}^n k^2 {{n} \choose{k}}$ .

Para contar de otra manera, primero elige $a$ y $b$ que se puede hacer en $n^2$ maneras. Para elegir $A$ y $B$ , considere el conjunto de pares $P=\{(x,y):x \in S_n, y \in \{0,1\}\} \setminus \{(a,0),(b,1)\}$ claramente $|P| = 2n-2$ . Sea $Q$ sea cualquier subconjunto de $P$ de tamaño $n-1$ para lo cual hay ${2n-2} \choose {n-1}$ posibilidades. Dejar que $A = \{a\} \cup \{x:x \in S|(x,0) \in Q\}$ y $B = \{x:x \in S|(x,1) \notin Q\}$ , afirmamos que $(a,b,A,B) \in Z$ . Claramente $a \in A$ y $b \in B$ desde $(b,1) \notin P$ y tenemos $$|A| = k \Leftrightarrow \\ |\{x:x \in S|(x,0) \in Q\}| = k-1 \Leftrightarrow \\ |\{x:x \in S|(x,1) \in Q\}| = n-k \Leftrightarrow \\ |\{x:x \in S|(x,1) \notin Q\}| = |B| = k$$ Está claro que cualquier selección de $Q$ da lugar a diferentes opciones para $A$ y $B$ Así que sabemos que hay al menos ${2n-2} \choose {n-1}$ posibilidades de $A$ y $B$ . Pero no es difícil ver que para cualquier cuatrillizo $(a,b,A,B) \in Z$ se puede invertir este proceso para crear $Q \subset P$ de tamaño $n-1$ .

Answer 4

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $$\bbox[10px,#efe,border:0.1em groove navy]{\mbox{This is an 'algebraic proof' which can still be useful besides the 'combinatorical way'.}}$$

En adelante, utilizaré las identidades $$\left\{\begin{array}{rcl} \ds{m \choose n} & \ds{=} & \ds{\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{m} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}\,,\qquad n \in \mathbb{Z}}. \\[3mm] \ds{\sum_{k = 0}^{n}{n \choose k}k^{2}z^{k}} & \ds{=} & \ds{\pars{z\,\partiald{}{z}}^{2}\sum_{k = 0}^{n}{n \choose k}z^{k} = \pars{z\,\partiald{}{z}}^{2}\pars{1 + z}^{n} = \pars{n^{2}z^{2} + nz}\pars{1 + z}^{n - 2}} \end{array}\right. $$

\begin {align} \color {#f00}{ \sum_ {k = 0}^{n}k^{2}{n \choose k}^{2}} & = \sum_ {k = 0}^{n}k^{2}{n \choose k}{n \choose n - k} = \sum_ {k = 0}^{n}k^{2}{n \choose k} \oint_ { \verts {z}\ =\ 1^{-}}\!\!\!{ \pars {1 + z}^{n} \over z^{n - k + 1}} \,{ \dd z \over 2 \pi\ic } \\ [5mm] & = \oint_ { \verts {z}\ =\ 1^{-}}\!\!\!{ \pars {1 + z}^{n} \over z^{n + 1}} \sum_ {k = 0}^{n}{n \choose k}k^{2}z^{k}\N-, { \dd z \over 2 \pi\ic } \\ [5mm] & = \oint_ { \verts {z}\ =\ 1^{-}}\!\!\!{ \pars {1 + z}^{n} \over z^{n + 1}} \bracks { \pars {n^{2}z^{2} + nz} \pars {1 + z}^{n - 2}}, { \dd z \over 2 \pi\ic } \\ [5mm] & = n^{2} \oint_ { \verts {z}\ =\ 1^{-}}\!\!\!{ \pars {1 + z}^{2n - 2} \over z^{n - 1}} \,{ \dd z \over 2 \pi\ic } + n \oint_ { \verts {z}\ =\ 1^{-}}\!\!\!{ \pars {1 + z}^{2n - 2} \over z^{n}} \,{ \dd z \over 2 \pi\ic } \\ [5mm] & = n^{2}{2n - 2 \choose n - 2} + n{2n - 2 \choose n - 1} = n^{2}{ \pars ¡{2n - 2}! \over \pars {n - 2}!n!} + n{2n - 2 \choose n - 1} \\ [5mm] & = n^{2}\N-, {n - 1 \over n}{ \pars ¡{2n - 2}! \over \pars ¡{n - 1}! \pars {n - 1}!} + n{2n - 2 \choose n - 1} = \pars {n^{2} - n}{2n - 2 \choose n - 1} + n{2n - 2 \choose n - 1} \\ [5mm] & = \color {#f00}{n^{2}{2n - 2 \choose n - 1}} \end {align}

Answer 5

Tenemos $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k $$ Diferenciando con respecto a $x$ obtenemos $$n(1+x)^{n-1} = \sum_{k=0}^n k \binom{n}{k}x^{k-1}$$ y por lo tanto $$n\left(1+\frac{1}{x}\right)^{n-1} = \sum_{k=0}^{n}k\binom{n}{k}\frac{1}{x^k} $$ La expresión dada es el término constante en $$n^2(1+x)^{n-1}\left(1+\frac{1}{x}\right)^{n-1} $$ y por lo tanto en $$n^2\frac{(1+x)^{2n-2}}{x^{n-1}}$$ y es igual a $$n^2\binom{2n-2}{n-1}$$