donde es un número entero positivo.

Question

Recientemente me encontré con el problema de encontrar la suma de $\sum_{k = 0}^n k^2 {n \choose k}$. La solución que he encontrado es algo como esto: $\sum_{k = 0}^n k^2 {n \choose k}=\sum_{k = 0}^n k(k-1) {n \choose k} + \sum_{k = 0}^n k {n \choose k}$. Utilizando el hecho de que $\sum_{k = 0}^n k {n \choose k}=n2^{n-1}$ y $\sum_{k = 0}^n k(k-1) {n \choose k} =[\sum_{k = 0}^n (x^k)'' {n \choose k}]|_{x=1}=[\sum_{k = 0}^n (x^k) {n \choose k}]'' |_{x=1}=[(x+1)^n]'' |_{x=1} = n(n-1)2^{n-2}$

(donde usamos la expansión binomial $(x+1)^n=\sum_{k = 0}^n x^k {n \choose k}$), se puede evaluar fácilmente la suma deseada como un ser igual a $n(n+1)2^{n-3}$.

Claramente, uno puede seguir este método para encontrar (de forma recursiva) las fórmulas para las sumas $\sum_{k = 0}^n k^t {n \choose k}$ donde $t$ es un entero positivo. Por ejemplo, uno de los más iteración da $\sum_{k = 0}^n k^3 {n \choose k}=n^2(n+3)2^{n-3}$ (si no he hecho ningún error de cálculo).

Por lo tanto, si definimos $F(t)$ a ser el polinomio tal que $\sum_{k = 0}^n k^t {n \choose k} = 2^{n-t} F(t)$, mi pregunta es simple:

Hay un cerrado fórmula para $F(t)$?

También, yo sería feliz con cualquier referencia en este tipo de sumas. Gracias!

Answer 1

Al usar los números de Stirling del segundo tipo , tenemos que:$$ k^t = \sum_{j=0}^{t}j!{t \brace j}\binom{k}{j} $ $ por lo tanto:$$\sum_{k=0}^n k^t \binom{n}{k} = \sum_{j=0}^{t}{t \brace j}\sum_{k=0}^{n}j!\binom{k}{j}\binom{n}{k}\tag{1}$ $ pero desde:$$\sum_{k=0}^{n}\binom{k}{j}\binom{n}{k} = 2^{n-j}\binom{n}{j}\tag{2}$ $ sigue que:

PS

donde$$\sum_{k=0}^n k^t \binom{n}{k}=2^{n-t}\sum_{j=0}^{t}{t\brace j}\,2^{t-j}\,(n)_j \tag{3}$ es el símbolo de Pochhammer que cae$(n)_j$.

Answer 2

Mucho me prefieren evitar monomials al hacer balance, porque no se comportan muy bien (aunque para las integrales, que está perfecto). Por otro lado, si utilizamos $1, {x\choose 1}, {x\choose 2},\ldots$ en lugar de $1,x,x^2,\ldots$, tendemos a obtener mucho mejores resultados. Si es necesario, podemos tomar combinaciones lineales para obtener el resultado para monomials (esto es exactamente cómo los números de Stirling surgir en el gato de la solución).

Para ilustrar esto, vamos a calcular el $\sum_{k=0}^n {k\choose t}{n\choose k}$. Esta cuenta el número de maneras de seleccionar, de $n$ jugadores, dos distintos equipos, el segundo de los cuales tiene un tamaño $t$-en primer lugar, elegir el $k$ los jugadores que no están en el primer equipo, luego elegimos la $t$ jugadores del segundo equipo de aquellos. Por lo $\sum_{k=0}^n {k\choose t}{n\choose k} = 2^{n-j} {n\choose j}$.

Ahora bien, decir que queremos encontrar a $\sum_{k=0}^n k^2 {n\choose k}$. Tenemos $k^2 = 2 {k\choose 2} + {k \choose 1}$, así: $$\sum_{k=0}^n k^2 {n\choose k} = 2\sum_{k=0}^n {k\choose 2} {n\choose k} + \sum_{k=0}^n {k\choose 1} {n\choose k}$$ $$=2\cdot 2^{n-2}{n\choose 2} + 2^{n-1} {n\choose 1}$$ $$= 2^{n-1} \left({n\choose 2}+{n\choose 1}\right) $$ $$=2^{n-1} {{n+1}\choose 2}$$

Answer 3

Esto está estrechamente relacionado con Jack D'Aurizio la respuesta, pero he pensado que vale la pena vincular a algunas otras preguntas relacionadas.

---

Como he usado en varios puestos relacionados (por ejemplo, aquí, aquí, y en esta estrechamente relacionados con la respuesta), cada uno de los poderes de $k$ puede ser escrita como una suma de los coeficientes binomiales considerado como polinomios (combinatoria polinomios) $$ \newcommand{\stirtwo}[2]{\left\{{#1}\cima{#2}\right\}} k^m=\sum_{j=0}^m\binom{k}{j}\,\stirtwo{m}{j}j!\la etiqueta{1} $$ donde $\stirtwo{m}{j}$ es un Número de Stirling del Segundo Tipo. También tenemos $$ \binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}\etiqueta{2} $$ que se comprueba fácilmente por la expansión de los coeficientes binomiales en factoriales.

Por lo tanto, $$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^m &=\sum_{k=0}^n\sum_{j=0}^m\binom{n}{k}\binom{k}{j}\,\stirtwo{m}{j}j!\\ &=\sum_{k=0}^n\sum_{j=0}^m\binom{n}{j}\binom{n-j}{k-j}\,\stirtwo{m}{j}j!\\ &=\sum_{j=0}^m\binom{n}{j}2^{n-j}\stirtwo{m}{j}j!\\ &=2^{n-m}\color{#C00000}{\sum_{j=0}^m\binom{n}{j}2^{m-j}\stirtwo{m}{j}j!}\\ &=2^{n-m}\color{#C00000}{P_m(n)}\tag{3} \end{align} $$ donde $P_m$ es un grado-$m$ polinomio. La suma que está en rojo es lo más cercano a una forma cerrada para $P_m$ ya que he visto.

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{t = 1,2,3,\ldots}$ e $\ds{0 < a < 1}$:

\begin{align} \color{#66f}{\large\sum_{k = 0}^{n}k^{t}{n \choose k}}& =\sum_{k = 1}^{\infty}k^{t}{n \choose n - k} =\sum_{k = 1}^{\infty}k^{t}\oint_{\verts{z}\ =\ a} {\pars{1 + z}^{n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} \sum_{k = 1}^{\infty}{z^{k} \over k^{-t}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} {\rm Li}_{-t}\pars{z}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n + 1}} \pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1} \pars{1 - z}^{-\ell - 1}\,{\dd z \over 2\pi\ic} \end{align} donde $\ds{{\rm S}\pars{n,k}}$ son Los Números de Stirling del Segundo Tipo.

\begin{align} \color{#66f}{\large\sum_{k = 0}^{n}k^{t}{n \choose k}}& =\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1} \times \\[3mm]&\sum_{\ell' = 0}^{\infty}{-\ell - 1 \choose \ell'} \pars{-1}^{\ell'}\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{n - \ell' + 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell}{\rm S}\pars{t + 1,\ell + 1}\sum_{\ell' = 0}^{n}{\ell + \ell' \choose \ell'} {n \choose \ell'} \\[3mm]&=\color{#66f}{\large\pars{-1}^{t}\sum_{\ell = 0}^{t}\pars{-1}^{\ell} {\rm S}\pars{t + 1,\ell + 1}\ _{2}{\rm F}_{1}\pars{1 + \ell,-n;1;-1}} \end{align}

Answer 5

Otra posible respuesta se encuentra en el uso de funciones de generación. La respuesta es dada por el coeficiente de $x^n$ (o de $x^n/n!$ en el caso de la exponencial de generación de función).

Vamos a escribir $a_{n,t}=\sum_{k=0}^nk^t\binom nk$ y definir $$f_t(x)=\sum_{n=0}^\infty a_{n,t}x^n =\sum_{n=0}^\infty\sum_{k=0}^nk^t\binom nkx^n.$$ Reordenar las sumas y obtener $$f_t(x)=\sum_{k=0}^\infty\sum_{n=k}^\infty k^t\binom nkx^n =\sum_{k=0}^\infty k^t\frac{x^k}{(1-x)^{k+1}}=\frac1{1-x}\Phi\left(\frac x{1-x},-t,0\right)$$ donde $\Phi$ es el Lerch trascendente función.

La exponencial de generación de función $$g_t(x)=\sum_{n=0}^\infty a_{n,t}\frac{x^n}{n!}=\mathrm e^{2x}B_t(x)$$ se encuentra utilizando el mismo método. $B_t$ es la Campana polinomio de orden $t$.