Cómo resolver $\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2$ ?

Question

He intentado algo para resolver la serie $$\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2.$$ Mi enfoque es : $$(1+x)^n=\binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n.$$ Diferenciando la ecuación anterior $$n(1+x)^{n-1} = \binom{n}{1} + \binom{n}{2}x + \cdots + n\binom{n}{n}x^{n-1}$$

También, $$ \left(1+\frac{1}{x}\right)^n =\binom{n}{0} + \binom{n}{1}\frac{1}{x} + \binom{n}{2}\left(\frac{1}{x}\right)^2 + \cdots + \binom{n}{n}\left(\frac{1}{x}\right)^n$$ Multiplicando las dos ecuaciones anteriores obtengo, $$\begin{align*} &{n(1+x)^{n-1}\left(1 + \frac{1}{x}\right)^n}\\ &\quad= \left( \binom{n}{1}^2 + 2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2 + \cdots + n\binom{n}{n}^2\right)\left(\frac{1}{x}\right) + \text{other terms} \end{align*}$$

Así que puedo decir que el coeficiente de $\frac{1}{x}$ en la expansión de $n(1+x)^{n-1}(1+\frac{1}{x})^n$ me dará la respuesta requerida.

¿Lo estoy haciendo bien, por favor corrígeme si me equivoco?

Si estoy en lo cierto, por favor dígame cómo calcular el coeficiente de $\frac{1}{x}$ ?

Basándome en las respuestas, he intentado implementar las cosas en un código C++.

Intenté implementar el código usando el algoritmo euclidiano extendido para que el problema de la división truncada pueda ser eliminado pero todavía no soy capaz de averiguar por qué estoy obteniendo una respuesta incorrecta para n>=3. Este es mi código actualizado: http://pastebin.com/imS6rdWs Estaré agradecido si alguien puede ayudarme a averiguar qué es lo que falla en este código.

Gracias.

Solución:

Gracias a todas las personas que han dedicado su valioso tiempo a mi problema, muchas gracias, este es mi código actualizado:

http://pastebin.com/WQ9LRy6F

Answer 1

En primer lugar, recordemos que el coeficiente de $x^n$ en $(1+x)^n(1+x)^n=(1+x)^{2n}$ implica $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^2 &=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\binom{2n}{n}\tag{1} \end{align} $$ y a continuación, observe que $$ \begin{align} \sum_{k=0}^nk\binom{n}{k}^2 &=\sum_{k=0}^nk\binom{n}{n-k}^2\\ &=\sum_{k=0}^n(n-k)\binom{n}{k}^2\tag{2} \end{align} $$ Añadiendo la primera y la última parte de $(2)$ produce $$ \begin{align} 2\sum_{k=0}^nk\binom{n}{k}^2 &=n\sum_{k=0}^n\binom{n}{k}^2\\ &=n\binom{2n}{n}\tag{3} \end{align} $$ Por lo tanto, $$ \sum_{k=0}^nk\binom{n}{k}^2=\frac{n}{2}\binom{2n}{n}\tag{4} $$

Answer 2

Parece que quieres apelar a la convolución de Vandermonde, o al menos al método que utilizarías para demostrarla. Se puede aplicar directamente de la siguiente manera:

Dejemos que $S = \sum\limits_{k=0}^n k\binom{n}{k}^2$ sea la suma que queremos calcular. Nótese que $S = \sum\limits_{k=0}^n (n-k) \binom{n}{n-k}^2 = \sum\limits_{k=0}^n (n-k) \binom{n}{k}^2$ . Por lo tanto, $2S = n\sum\limits_{k=0}^n \binom{n}{k}^2 = n \binom{2n}{n}$ . Entonces

$$S = \frac{n}{2}\binom{2n}{n}.$$

Answer 3

Basándose en el excelente trabajo de @thomas-belulovich y @robjohn, pero abordando su objetivo revelado posteriormente....

Usted quiere $$ T(n) =S(n)-m\left\lfloor\frac{S(n)}m\right\rfloor =S(n)\text{ mod }m \qquad\text{for}\qquad S(n) =\frac{n}{2}{2n\choose n}. $$ Tenga en cuenta que $$ \frac{S(n)}{S(n-1)} =\frac{n}{n-1}\cdot\frac{2n(2n-1)}{n^2} =2\frac{2n-1}{n-1}. $$ Un enfoque de fuerza bruta para esto podría ser calcular $$ R(k)=2(2k-1)(k-1)^{-1}\pmod m $$ para cada $1<k\le n$ y luego multiplicar por el módulo $m$ para obtener $$ T(n)=S(1)\prod_{k=2}^nR(k). $$ Calculando cada $R(k)=(4k-2)x$ requiere $O(\log k)$ divisiones utilizando el algoritmo euclidiano ampliado para encontrar un $x$ para que $$ (k-1)x+my=1. $$

Algoritmo euclidiano ampliado : Dado que no es cero $a,b\in\mathbb{Z}$ , encontrar $x,y\in\mathbb{Z}$ para que $ax+by=\text{gcd}(a,b)$ . (Adaptado de El libro de David Joyner .)

1. Establecer $\overline{u}=\langle{u_0,u_1,u_2}\rangle$ $\leftarrow\langle{a,1,0}\rangle$ y $\overline{v}\leftarrow\langle{b,0,1}\rangle$ (vectores en $\mathbb{Z}^3$ ). Establecer $\overline{v}\leftarrow-\overline{v}$ si $b<0$ .

2. Mientras que $v_0 \ne 0$ repite:

3. $\qquad$ Calcular el cociente $q=\text{quo}(u_0,v_0)=u_0-v_0\left\lfloor\frac{u_0}{v_0}\right\rfloor$ .

4. $\qquad$ Establecer $\quad\overline{w}=\overline{u}-q\overline{v},\quad$ entonces $\quad\overline{u}=\overline{v},\quad$ y luego $\quad\overline{v}=\overline{w}.\quad$

5. Volver $a=u_0$ , $x=u_1$ y $y=u_2$ .

Esto se puede hacer en no muchas líneas de código C, y funciona siempre y cuando $m=10^9+7$ no tiene factores (primos) $p\le n$ (de hecho, este $m$ es primo). Si necesitas un algoritmo más eficiente y $m$ fuera un producto compuesto de primos distintos (que no lo es), se podría utilizar la factorización en primos de $m$ y un buen hecho sobre los coeficientes binomiales módulo de primos [Lukas 1878] para calcular por separado los residuos $$ {a\choose b}\equiv{[a/p]\choose[b/p]}{a\mod p\choose b\mod p}\pmod p $$ modulando cada factor $p$ y luego recuperar $T(n)$ utilizando el Teorema chino del resto .

Aquí hay algunos valores precalculados: $$\matrix{ k& n=10^k &{2n\choose n}\text{ mod }m &T(n) \\0& 1 &2 &1 \\1& 10 &184756 &923780 \\2& 100 &407336795 &366839610 \\3& 1000 &72475738 &237868748 \\4& 10000 &703593270 &966325381 \\5& 100000 &879467333 &366342189 \\6& 1000000 &192151600 &799327475 }$$

Si quieres encontrar un método eficiente para resolver este problema, probablemente querrás mirar los trabajos de Donald Knuth, Andrew Granville y Richard Stanley, que también ha recopilado excelentes listas de problemas de prueba biyectiva y caracterizaciones de los números catalanes $C_n=\frac1{n+1}{2n\choose n}$ a la que nuestro $S(n)$ están estrechamente relacionados ya que $S(n)={n+1\choose2}C_n$ .

---

Una puede estarían tentados a intentar acortar el cómputo utilizando el teorema de Wilson, $$ p\text{ prime} \quad\implies\quad (p-1)!\equiv-1\pmod p $$ La congruencia de Morley (1895), $$ p=2n+1\text{ prime} \quad\implies\quad {2n\choose n}\equiv(-1)^n4^{2n}\pmod{p^3} $$ y/o Teorema de Kummer usando suficientes primos "de referencia" cerca de $n$ y $2n$ , con el algoritmo euclidiano extendido para las inversas y el CRT (¡ahí está el truco!) para obtener el resultado final. Por ejemplo, aquí hay algunos pares primos $q_i=2p_i+1$ cerca de $n=10^6$ y $2n$ : $$ \matrix{ i & p_i-n & q_i-2n \\ 1 & -251 & -501 \\ 2 & -191 & -381 \\ 3 & 151 & 303 \\ 4 & 193 & 387 \\ } $$ Del teorema de Wilson para los primos Impares $q$ , agrupación $(q-1)!=(1\cdots\frac{q-1}2)(\frac{q+1}2\cdots q-1)$ y observando que el segundo término es $(-1)^\frac{q-1}2$ veces el primer término módulo $q$ encontramos que $$ \left(\left(\tfrac{q-1}{2}\right)!\right)^2 \equiv(-1)^{\frac{q+1}2} \pmod q $$ de modo que para los pares primos $q_i=2p_i+1$ , $$ {2p_i\choose p_i}\equiv(-1)^{p_i}=-1\pmod{q_i}. $$ Así, podemos calcular (utilizando el algoritmo euclidiano extendido para las inversas de $k$ modulo $q_i$ ) $$ {2n\choose n}\equiv-\prod_{k=p_i+1}^n\frac{4k-2}{k} \pmod{q_i} $$ para $i=1,2$ arriba. Sin embargo, no podemos utilizar el CRT para obtener $T(n)$ . Tendríamos que tener suficientes pares primos para reconstruir $S(n)$ , y luego calcular su residuo al final. Como el coeficiente central del binomio es aproximadamente $${2n\choose n}\approx\frac{4^n}{\sqrt{\pi n}}\left(1-\frac1{nc_n}\right),\qquad c_n\in(8,9)$$ necesitaríamos unos 96 mil pares (p,q), lo que hace inviable este enfoque.

Answer 4

En primer lugar, abordamos el problema del desbordamiento. Tenga en cuenta que $10^9+7$ es relativamente primo de todos los números que aparecen en un cálculo ingenuo de $\binom{2n}{n}$ . En efecto, $10^9+7$ resulta ser primordial. Así que cuando estamos calculando, siempre podemos reducir el módulo $10^9+7$ tan a menudo como sea necesario para evitar el desbordamiento.

Ahora a la identidad. Tenemos $n$ niños y $n$ chicas. Queremos elegir $n$ personas. El número de formas en que esto puede hacerse es $\binom{2n}{n}$ . Pero podemos elegir $0$ niños y $n$ chicas, o $1$ niño y $n-1$ chicas, y así sucesivamente. Podemos elegir $k$ niños y $n-k$ chicas en $\binom{n}{k}\binom{n}{n-k}$ formas, o equivalentemente en $\binom{n}{k}^2$ formas. Esto da la derivación estándar de la identidad $$\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2.$$ Tenga en cuenta ahora que el $\binom{2n}{n}$ las opciones son todas igual de probables. El esperado número de chicos es, por simetría, igual a $\frac{n}{2}.$ Pero la probabilidad de que haya $k$ los chicos es $\frac{\binom{n}{k}^2}{\binom{2n}{n}}$ y, por lo tanto, el número esperado de niños es $$\sum_{k=0}^n k\frac{\binom{n}{k}^2}{\binom{2n}{n}}.$$ El término correspondiente a $k=0$ es $0$ por lo que se puede omitir, y obtenemos $$\sum_{k=1}^n k\frac{\binom{n}{k}^2}{\binom{2n}{n}}=\frac{n}{2},$$ que es esencialmente nuestra identidad.

Observación: Hay un libro muy bueno sobre pruebas biyectivas llamado Pruebas que realmente cuentan . Un título que hasta ahora no parece haber sido utilizado es Pruebas medias .