cómo probar esta combinatoria de identidad accidentalmente encontrar?

Question

Hoy cuando he resolver un recuento problema utilizando diferentes métodos para encontrar el siguiente (aparentemente correcta) combinatoria de identidad, pero no puedo encontrar en Internet, y no puedo probar su exactitud ni. Pero he verificado su exactitud con entero positivo $n$ dentro $[0, 1000]$ mediante un sencillo programa de ordenador. Cualquier persona puede hacer una prueba de esta identidad (o cualquier enlace a su prueba)?

$$\frac{(n+1)n}{2} \cdot n! = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{n!}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$

Y, equivalentemente, si quieres,

$$\frac{(n+1)n}{2} = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{1}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$

Answer 1

La identidad puede ser escrito

$$n!\binom{n+1}2=\sum_k(-1)^k\binom{n}k(n-k)^{n+1}\;.\tag{1}$$

El lateral derecho tiene el aspecto de una inclusión-exclusión en el cálculo, por lo que podemos buscar una combinatoria de interpretación sobre esa base. Si $K$ es un subconjunto de a $[n]=\{1,\ldots,n\}$ $k$ elementos, $(n-k)^{n+1}$ puede ser interpretado como el número de funciones de$[n+1]$$[n]\setminus K$. Si por $k\in[n]$ dejamos $A_k$ el conjunto de funciones de$[n+1]$$[n]\setminus\{k\}$, entonces para cada a $K\subseteq[n]$ $|K|=k$ hemos

$$\left|\,\bigcap_{k\in K}A_k\,\right|=(n-k)^{n+1}\;.$$

Hay $\binom{n}k$ tales subconjuntos de a $[n]$, por lo que

$$\begin{align*} \left|\bigcup_{k=1}^nA_k\right|&=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}\left|\,\bigcap_{k\in K}A_k\,\right|\\ &=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}(n-k)^{n+1}\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\;. \end{align*}$$

$\bigcup_{k=1}^nA_k$ es el conjunto de funciones de $[n+1]$ $[n]$que no son surjections, por lo que el número de surjections de $[n+1]$ $[n]$debe ser

$$\begin{align*} n^{n+1}-\left|\bigcup_{k=1}^nA_k\right|&=n^{n+1}-\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\\ &=n^{n+1}+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^{n+1}\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^{n+1}\;. \end{align*}$$

Para completar la prueba de $(1)$ sólo necesitamos mostrar que hay $n!\binom{n+1}2$ surjections de$[n+1]$$[n]$.

Si $f:[n+1]\to[n]$ es un surjection, no deben ser diferenciadas $k,\ell\in[n+1]$ tal que $f(k)=f(\ell)$, mientras que $f$ es inyectiva en a $[n+1]\setminus\{k,\ell\}$. Deje $D=[n+1]\setminus\{\ell\}$; cada surjection $g$ $D$ $[n]$se extiende a un único surjection $f:[n+1]\to[n]$$f(k)=f(\ell)$, la función definida por

$$f(i)=\begin{cases} g(i),&\text{if }i\in D\\ g(k),&\text{if }i=\ell\;. \end{casos}$$

Cada surjection $f:[n+1]\to[n]$ tal que $f(k)=f(\ell)$ surge de esta manera de un surjection de$D$$[n]$, e $|D|=n$ hay $n!$ surjections de $D$ $[n]$y, por tanto, $n!$ surjections $f:[n+1]\to[n]$ tal que $f(k)=f(\ell)$. Por último, hay $\binom{n+1}2$ formas de elegir el $k$ $\ell$ que $f$ es enviar el mismo elemento de $[n]$, por lo que hay un total $n!\binom{n+1}2$ surjections de$[n+1]$$[n]$.

Answer 2

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[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{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}\pars{-1}^{k}{n! \sobre k!\pars{n - k}!} \,\pars{n - k}^{n + 1}\ =\ {\pars{n + 1}n \over 2}\,n!:\ ?}$

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

---

$\ds{\pars{\expo{z} - 1}^{n}}$ está relacionado, como la generación de función, a la Los Números de Stirling del Segundo Tipo. Es decir, \begin{equation} \pars{\expo{z} - 1}^{n} = n!\sum_{j = 0}^{\infty}\braces{j \atop n}\,{z^{\, j} \over j!} \tag{1.1} \end{equation} $\ds{\braces{j \atop n}}$ es un Número de Stirling del Segundo Tipo. Con esta expresión, $\ds{\pars{1}}$ se reduce a: \begin{align} &\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}}\ =\ \pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\ \overbrace{\oint_{\verts{z}\ =\ 1}\,\, {1 \over z^{n + 2 - j}}\,\,{\dd z \over 2\pi\ic}} ^{\ds{\delta_{n + 2 - j,1}}} \\[5mm] = &\ \pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\, \delta_{j,n + 1} = \pars{n + 1}!\, n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!} = n!\braces{n + 1 \atop n}\tag{2} \end{align}

---

Sin embargo, $\ds{\braces{n + 1 \atop n}}$ satisface la 'simple identidad' $\ds{\braces{n + 1 \atop n} = {n + 1 \choose 2} = {\pars{n + 1}n \over 2}}$ de manera tal que la expresión $\ds{\pars{2}}$ se convierte en: $$ \color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \sobre k!\pars{n - k}!} \,\pars{n - k}^{n + 1}} = \color{#f00}{{\pars{n + 1}n \over 2}\,n!} $$

ADDENDA:
Siguiendo @MarkoRiedel comentario ( ver a continuación ), se puede 'saltar directamente a partir de la expresión de $\ds{\pars{1}}$: \begin{align} &\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}} = \pars{n + 1}!\bracks{z^{n + 1}}\bracks{\pars{\expo{z} - 1}^{n}} \\[5mm] = & \pars{n + 1}!\bracks{n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!}} = n!\braces{n + 1 \atop n} = \color{#f00}{{\pars{n + 1}n \over 2}\,n!} \end{align} donde hemos utilizado la generación de la función $\ds{\pars{1.1}}$.

Answer 3

Otra forma es considerar que el de las diferencias finitas hacia atrás (hacia atrás Delta) se define como $$ \nabla _x \,f(x) = f(x) - f(x - 1) $$ y tenemos que su $n$-ésima iteración es: $$ \nabla _x ^n \,f(x) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\;f(x - k)} $$ por lo tanto, el lado derecho es: $$ \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\;\left( {n - k} \right)^{n + 1} } = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} $$ Ahora $x^{\,n + 1} $ es un polinomio de grado $n+1$ y podemos expresarlo en términos de los Números de Stirling de $2$nd tipo y la Caída de los Factoriales de $x$ $$ x^{\,n + 1} = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \n} \right)} {\left\{ \begin{gathered} n + 1 \\ k \\ \end{reunieron} \right\}\;x^{\,\underline {\k\;} } } $$ El retroceso del Delta de la caída factorial está dada por: $$ \begin{gathered} \nabla _x \;x^{\,\underline {\,m\;} } = \left( {x\left( {x - 1} \right) \cdots \left( {x - m + 1} \right)} \right) - \left( {\left( {x - 1} \right)\left( {x - 2} \right) \cdots \left( {x - m} \right)} \right) = m\left( {x - 1} \right)^{\,\underline {\,m - 1\;} } \hfill \\ \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} } = m^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,m - n\;} } \quad \Rightarrow \quad \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} } = 0\quad \left| {\;m < n} \right. \hfill \\ \end{reunieron} $$ por lo tanto: $$ \begin{gathered} \nabla _x ^n \,x^{n + 1} = \nabla _x ^n \,\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered} n + 1 \\ k \\ \end{reunieron} \right\}\;x^{\,\underline {\k\;} } } = \nabla _x ^n \,\left( {\left\{ \begin{gathered} n + 1 \\ n + 1 \\ \end{reunieron} \right\}\;x^{\,\underline {\n + 1\;} } + \left\{ \begin{gathered} n + 1 \\ n \\ \end{reunieron} \right\}\;x^{\,\underline {\n\;} } } \right) = \hfill \\ = \left( {\left\{ \begin{gathered} n + 1 \\ n + 1 \\ \end{reunieron} \right\}\;\left( {n + 1} \right)^{\,\underline {\n\;} } \left( {x n} \right)^{\,\subrayado {\,1\;} } + \a la izquierda\{ \begin{gathered} n + 1 \\ n \\ \end{reunieron} \right\}n^{\,\underline {\,n\;} } \;\left( {x n} \right)^{\,\subrayado {\,0\;} } } \right) = \hfill \\ = \left( {1\;\left( {n + 1} \right)^{\,\underline {\n\;} } \left( {x n} \right)^{\,\subrayado {\,1\;} } + \a la izquierda( \begin{gathered} n + 1 \\ n - 1 \\ \end{reunieron} \right)^{\,\underline {\n\;} } \;\left( {x n} \right)^{\,\subrayado {\,0\;} } } \right) = \hfill \\ = n!\a la izquierda( {\;\left( \begin{gathered} n + 1 \\ n \\ \end{reunieron} \right)\left( {x n} \right) + \left( \begin{gathered} n + 1 \\ n - 1 \\ \end{reunieron} \right)} \right) \hfill \\ \end{se reunieron} $$ que, calculado en $x=n$ le da: $$ \begin{gathered} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{reunieron} \right)\;\left( {n - k} \right)^{n + 1} } = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} = \hfill \\ = n!\a la izquierda( \begin{gathered} n + 1 \\ n - 1 \\ \end{reunieron} \right) = n!\frac{{\left( {n + 1} \right)n}} {2} \hfill \\ \end{se reunieron} $$ demostrando así su afirmación, mientras que la generalización a otros valores de $x$.

Answer 4

Aquí es otra variación del tema. Es conveniente utilizar el coeficiente de operador $[t^k]$ para denotar el coeficiente de $t^k$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} \binom{n}{k}=[t^k](1+t)^n\qquad\text{and}\qquad k^n=n![t^n]e^{kt} \end{align*}

OPs identidad puede ser escrito como

\begin{align*} \frac{n}{2}(n+1)!=\sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\quad\qquad n\geq 0 \end{align*}

Empezamos con la mano derecha y obtener \begin{align*} \sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+1}\tag{1}\\ &=\sum_{k=0}^\infty(-1)^{n-k}[u^k](1+u)^n(n+1)![t^{n+1}]e^{kt}\tag{2}\\ &=(-1)^n(n+1)![t^{n+1}]\sum_{k=0}^\infty(-e^t)^k[u^k](1+u)^n\tag{3}\\ &=(-1)^n(n+1)![t^{n+1}]\left(1-e^t\right)^n\tag{4}\\ &=(n+1)![t^{n+1}]\left(t+\frac{t^2}{2}+\cdots\right)^n\tag{5}\\ &=\frac{n}{2}(n+1)!\tag{6} \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) podemos cambiar el orden de la suma: $k\longrightarrow n-k$

• En (2) se aplica el coeficiente de operador dos veces. También ampliamos el rango de la suma hasta el infinito, sin cambiar nada, ya que estamos añadiendo ceros sólo.

• En (3) vamos a hacer algunos cambios y el uso de la linealidad del coeficiente de operador.

• En (4), usamos la sustitución de la regla con $u=-e^t$ \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[u^k]A(u)\\ \end{align*}

• En (5) factor $(-1)^n$ y ampliar la exponencial de la serie.

• En (6) tomamos nota de que en el fin de extraer el coeficiente de $t^{n+1}$ tenemos $n$ posibilidades para seleccionar el término $t$ y una posibilidad para seleccionar el término $\frac{t^2}{2}$ dar $\frac{n}{2}$.

Answer 5

Escribir $$(n-k)^{n+1}=\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}$$ for some $a_0,a_1,a_2,\ldots,a_{n+1}\in\mathbb{Z}$. Clearly, $$a_{n+1}=(-1)^{n+1}\,(n+1)!$$ and $$a_n=(-1)^n\,\frac{n(n+1)}{2}\,n!\,.$$ Es decir, $$\sum_{k=0}^{n}\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}=\sum_{j=0}^{n+1}\,a_j\,\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\binom{k}{j}\,.$$ El uso de la identidad de $\binom{n}{k}\,\binom{k}{j}=\binom{n}{j}\,\binom{n-j}{k-j}$ para los números enteros $n,k,j$$0\leq j\leq k\leq n$, obtenemos $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{j=0}^{n}\,(-1)^j\,a_j\,\binom{n}{j}\,\sum_{k=j}^n\,(-1)^{k-j}\,\binom{n-j}{k-j}\,,$$ o $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=(-1)^n\,a_n=\frac{n(n+1)}{2}\,n!\,.$$

P. S. Mientras que el término que involucra $a_{n+1}$ se desvanece, el coeficiente de $a_{n+1}$ necesitan ser evaluados para determinar $a_n$. En general, $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,f(k)=(-1)^n\,b_n\,,$$ donde $$f(x)=\sum_{j=0}^d\,b_j\,\binom{x}{j}$$ with $d\in\mathbb{Z}$ greater than or equal to $n$ and $b_0,b_1,b_2,\ldots,b_d\in K$, where $K$ is an extension field of $\mathbb{Q}$.