Cómo demostrar esta identidad? Por favor alguien puede darme algunos detalles ?
$$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
Respuestas
¿Demasiados anuncios?
Añadido 2014-06-13: de Acuerdo a un comentario de David he añadido un poco más cerca de la inspección de la combinatoria de los aspectos de la $(1)$ $(2)$ por debajo. El desafío era encontrar una adecuada interpretación combinatoria para $l_k=n!\binom{n}{k}\frac{1}{k}$.
Esta es una especie de combinatoria prueba de la identidad anterior. Como David ya se mencionó en su respuesta, una verdadera prueba combinatoria parece casi imposible si tenemos en cuenta el factor de $\frac{1}{k}$. Pero, siempre podemos escribir el Número Armónico $H_n$ como
\begin{align*} H_n=\sum_{k=1}^{n}\frac{1}{k}=\frac{a_n}{n!} \end{align*}
con $a_n$ un número natural y podemos intentar encontrar una combinatoria de prueba para el numerador $a_n$. Así, podemos interpretar $H_n$ como proporción aritmética de $a_n$ $n!$ basado en la combinatoria de los argumentos.
La prueba se basa en dos ideas:
Permutación de $n+1$ elementos que contiene exactamente dos ciclos y el
Inclusión-Exclusión Principio (IEP).
Primer paso: Permutación con dos ciclos. Deje $(a_1,\dots,a_j)(a_{j+1},\dots,a_{n+1})$ ser una permutación de $n+1$ elementos con dos ciclos. Podemos suponer que la $a_1=1$ e indicar el ciclo de con $a_1$ ciclo izquierdo. También podemos suponer que $a_{j+1}$ es el elemento más pequeño de la derecha ciclo.
Ahora, es válido lo siguiente:
El número de $e_k$ de Permutaciones de $n+1$ elementos con dos ciclos de la cual el derecho de ciclo contiene exactamente $k$ $(1\leq k\leq n)$ los elementos se \begin{align*} e_k = \frac{n!}{k} \end{align*}
Primero elegimos $k$ elementos de la $n$-element set $\{2,3,\dots,n+1\}$ ($1$ se fijan en la primera posición en el ciclo izquierdo). Esto se puede hacer en $\binom{n}{k}$ maneras. $k$ elementos en el ciclo correcto puede ser colocado en $(k-1)!$ formas ($a_{j+1}$ es fijar en la primera posición de la derecha ciclo), mientras que el resto de $n-k$ elementos se pueden organizar en $(n-k)!$ formas en el ciclo izquierdo. Observamos:
\begin{align*} e_k=\binom{n}{k}(k-1)!(n-k)!=\frac{n!}{k} \end{align*}
Desde $k$ puede variar de $1$ $n$tenemos
El número de permutaciones de $n+1$ elementos con dos cicloses \begin{align*} e_1+e_2+\dots+e_n=\sum_{k=1}^{n}\frac{n!}{k}=n!H_n \end{align*}
Así, obtenemos una combinatoria de interpretación para $n!H_n$ basado en el $e_k$ (RHS). Observar, el $e_k$ están proporcionando la información para exactamente $k$ elementos dentro del ciclo correcto. Aquí podemos pensar acerca de la inclusión-exclusión principio (IEP) que se transforma , al menos, la información a exactamente la información (y viceversa).
Segundo paso: Inclusión-Exclusión Principio (IEP)
Ahora introducimos $l_k$ denota el número de permutaciones de $n+1$ elementos con $k$ elementos en el ciclo correcto de la longitud de , al menos, $k$.
$\binom{m}{k}$ ... número de arreglos para seleccionar $k$ elementos específicos de la derecha ciclo de longitud $m(\geq k)$ de permutaciones con $n$ elementos
$e_k$ ... número de permutaciones con exactamente $k$ elementos en el ciclo correcto
$l_k$ ... número de permutaciones con $k$ elementos en el ciclo correcto de la longitud de , al menos, $k$
Observar, que \begin{align*} l_k&=\sum_{m=k}^{n}\binom{m}{k}e_m\qquad\qquad1\leq k\leq n\tag{1}\\ &=n!\binom{n}{k}\frac{1}{k}=\binom{n}{k}e_k\tag{2} \end{align*}
Ahora una inspección más cercana de $l_k$ a identificar con mayor precisión el significado de el número de permutaciones con $k$ elementos en el ciclo correcto de la longitud de , al menos, $k$:
Combinatoria interpretación de $(1)$: $l_k=\sum_{m=k}^{n}\binom{m}{k}e_m$
Cada sumando del lado derecho es de la forma$\binom{m}{k}e_m$$k \leq m \leq n$. Desde $e_m$ cuenta el número de permutaciones con derecho a la longitud de ciclo de la $m$, $\binom{m}{k}$ posibilidades para elegir un correcto ciclo de longitud $k$ a partir de ellas. Desde $m$ varía de $k$ $n$ tenemos todas las permutaciones con $k$ elementos en el ciclo correcto de la longitud de , al menos, $k$.
Si nos centramos en específico de permutación con la derecha ciclo de longitud $m$ podemos identificar a $\binom{m}{k}$ permutaciones con derecho a la longitud de ciclo de la $k$ respetando el orden de los elementos dentro de la izquierda ciclo y también respetando el orden de los elementos dentro del ciclo correcto. (Vea la siguiente sección para una explicación más detallada de este fin de respetar aspecto).
Un poco más exigente:
Combinatoria interpretación de $(2)$: $l_k = n!\binom{n}{k}\frac{1}{k}=\binom{n}{k}e_k$
El RHS $\binom{n}{k}e_k$ multiplica cada ocurrencia de una permutación con la derecha ciclo de longitud $k$$\binom{n}{k}$.
Vamos a centrarnos en un determinado permutación con la derecha ciclo de longitud $k$ a averiguar cómo , al menos, la información se pone en juego:
\begin{align*} (1, a_2,a_3,\dots,a_{n-k+1})(a_{n-k+2},a_{n-k+3},\dots,a_{n+1})\tag{3} \end{align*} Consideramos que el $n$ posiciones comenzando con el primero ocupado por $a_2$ y la última de ellas ocupada por $a_{n+1}$ y podemos seleccionar $k$ estos $n$ posiciones en $\binom{n}{k}$ maneras. No podemos hacer lo siguiente: Nos llene estos $k$ posiciones seleccionadas con el $k$ elementos de la derecha ciclo por la preservación de su orden. Por eso,$a_{n-k+2}$$a_{n-k+3}$, que está a la izquierda de$a_{n-k+4}$$a_n$, que está a la izquierda de $a_{n+1}$. A continuación nos llene el resto de $n-k$ posiciones con los elementos de la izquierda ciclo de con $a_2, a_3$ $a_{n-k+1}$ también por la preservación de su orden. Por eso,$a_2$$a_3$, etc.
Para cada una de estas selecciones se define el derecho de ciclo que empieza con $a_{n-k+2}$ que fue de más a la izquierda (la más pequeña) elemento de la derecha ciclo de trabajo en $(3)$. Si $a_{n-k+2}$ no es el elemento más pequeño, se puede girar el ciclo, de modo que el elemento más pequeño de la derecha ciclo se convierte en la de la izquierda (bjiective operación).
Observamos: Por estas operaciones obtenemos $\binom{n}{k}$ permutaciones con derecho a la longitud de ciclo de la $\geq k$ $\leq n$ y, además, preservar el orden de ambos ciclos. Así, se han identificado todas las permutaciones de longitud de , al menos, $k$ que contienen un permutación como $(3)$.
De acuerdo con el IEP tenemos
\begin{align*} e_1+e_2+\cdots+e_n&=l_1-l_2\pm\cdots+(-1)^{n-1}l_n\\ n!H_n&=n!\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}\frac{1}{k}\tag{4}\\ \end{align*}
Así, hemos demostrado:
RHS: $n!H_n=n!\sum_{k=1}^{n}\frac{1}{k}$ da el número de permutaciones de $n+1$ elementos con dos ciclos, por lo que cada sumando $\frac{n!}{k}$ da el número de permutaciones de derecho de ciclos de longitud exactamente $k$
LHS: $n!\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}\frac{1}{k}$ da también el número de permutaciones de $n+1$ elementos con dos ciclos, por lo que cada sumando $n!\binom{n}{k}\frac{1}{k}$ da el número de arreglos de $k$ elementos en el ciclo correcto con una longitud de , al menos, $k$.
Algunas notas:
Nota: Identidad $(4)$ da lugar a lo que se denomina binomial inversa par con la Armónica de los Números de $H_n$ \begin{align*} H_n=\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{k+1}}{k}&&\frac{1}{n}=\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}H_k \end{align*}
(Usted puede ver la respuesta a la pregunta 730885 para obtener más detalles y otra prueba de identidad $(1)$ que es algebraicamente no combinatorically).
Nota: El unsigned los Números de Stirling de primera especie $|s(n,k)|$ están fuertemente relacionados con la combinatoria de la interpretación anterior. El $|s(n,k)|$ dar el número de permutaciones con $n$ elementos que contiene exactamente $k$ ciclos. Observamos $$n!H_n=|s(n+1,2)|$$
Esta prueba se basa en el Teorema 1 de Stirling Encuentro con la Armónica de los Números y los relacionados con el IEP pregunta 749390.
Añadido 2014-06-10: Ejemplo: Permutación de $n+1=4$ elementos
De acuerdo con un comentario de abel a continuación encontrará un ejemplo con las permutaciones de $4$ elementos, mostrando las interconexiones entre los $e_k$$l_k$.
La siguiente tabla enumera todos los $11$ permutación de $n+1=4$ elementos con exactamente $2$ ciclos.
- la primera columna muestra un identificador para cada permutación
- la segunda columna muestra todos los $11$ permutaciones de $4$ elementos con exactamente $2$ ciclos
- la tercera columna titulada $e_k$ listas de las contribuciones de $e_1, e_2$$e_3$.
- todas las demás columnas de la lista de las contribuciones de $l_k\ (1\leq k\leq 3)$ para el correspondiente ciclo de derecho en el encabezado de la línea de
Por favor nota: esta tabla muestra
- $6 e_1, 3 e_2$ $2 e_3$ , resultando en un total de $e_1+e_2+e_3=11$ permutaciones $(=3!H_3)$
- $18 l_1, 9 l_2$ $2 l_3$ , resultando en un total de $l_1-l_2+l_3=11$ permutaciones $(=3!H_3)$
\begin{array}{rccccccccccc} Id&()(a_{j+1}\dots)&e_k&(2)\ &(3)\ &(4)\ &(23)\ &(24)\ &(34)\ &(234)\ &(243)&\\ \hline\\ 1&(123)(4)&e_1&-\ &-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &\\ 2&(132)(4)&e_1&-\ &-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &\\ 3&(124)(3)&e_1&-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 4&(142)(3)&e_1&-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 5&(134)(2)&e_1&l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 6&(143)(2)&e_1&l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 7&(12)(34)&e_2&-\ &l_1\ &l_1\ &-\ &-\ &l_2\ &-\ &-\ &\\ 8&(13)(24)&e_2&l_1\ &-\ &l_1\ &-\ &l_2\ &-\ &-\ &-\ &\\ 9&(14)(23)&e_2&l_1\ &l_1\ &-\ &l_2\ &-\ &-\ &-\ &-\ &\\ 10&(1)(234)&e_3&l_1\ &l_1\ &l_1\ &l_2\ &l_2\ &l_2\ &l_3\ &-\ &\\ 11&(1)(243)&e_3&l_1\ &l_1\ &l_1\ &l_2\ &l_2\ &l_2\ &-\ &l_3\ & \end{array}
De acuerdo a las entradas de la tabla de $e_k$ $l_k$ anterior, podemos observar
\begin{align*} &e_1=\sum_{m=1}^{3}(-1)^{m+1}\binom{m}{1}l_m=\binom{1}{1}l_1-\binom{2}{1}l_2+\binom{3}{1}l_3=18-18+6=6\\ &e_2=\sum_{m=2}^{3}(-1)^{m+2}\binom{m}{2}l_m=\binom{2}{2}l_2-\binom{3}{2}l_3=9-6=3\\ &e_3=\sum_{m=3}^{3}(-1)^{m+3}\binom{m}{3}l_m=\binom{3}{3}l_3=2\\ \\ &l_1=\sum_{m=1}^{3}\binom{m}{1}e_m=\binom{1}{1}e_1+\binom{2}{1}e_2+\binom{3}{1}e_3=6+2\cdot3+3\cdot2=18\\ &l_2=\sum_{m=2}^{3}\binom{m}{2}e_m=\binom{2}{2}e_2+\binom{3}{2}e_3=3+3\cdot2=9\\ &l_3=\sum_{m=3}^{3}\binom{m}{3}e_m=\binom{3}{3}e_3=2\\ \\ &l_1=3!\binom{3}{1}\frac{1}{1}=6\cdot3\cdot1=18\\ &l_2=3!\binom{3}{2}\frac{1}{2}=6\cdot3\cdot\frac{1}{2}=9\\ &l_3=3!\binom{3}{3}\frac{1}{3}=6\cdot1\cdot\frac{1}{3}=2\\ \end{align*}
De la siguiente manera:
\begin{array}{llll} 3!H_3&=e_1+e_2+e_3&=6+3+2&=11\\ 3!H_3&=l_1-l_2+l_3&=18-9+2&=11 \end{array}
Jean-François Corbett
Puntos
16957
No sé cómo hacerlo por una combinatoria de prueba, pero aquí hay una alternativa: $$\eqalign{RHS &=\sum_{k=1}^n\int_0^1^{k-1}\,dx\cr &=\int_0^1 \frac{1-x^n}{1-x}\,dx\cr &=\int_0^1 \frac{1-(1-y)^n}{s}\,dy\cr &=\int_0^1 \sum_{k=1}^n\binom{n}{k}(-1)^{k+1}y^{k-1}\,dy\cr &=LI\ .\cr}$$ Yo estaría muy interesado en ver si hay una verdadera prueba combinatoria: yo habría pensado que el $1/k$ términos haría bastante difícil.
Phonics The Hedgehog
Puntos
111
este es demasiado largo para un comentario. ya está establecido que $ n! RHS = s(n+1, 2).$ vamos a mostrar que el $s(n+1, 2) - \frac{n!}{1} {n \choose 1} + \frac{n!}{2}{n \choose 2} + \ldots = 0$ @markus respuesta, vamos a los elementos de $s(n,2)$ escrito en el ciclo izquierdo con $1$ como el primer elemento y el derecho ciclo comienza con el elemento más pequeño de ese ciclo.
deje $\alpha_j, j = 1, 2, \ldots$ ser la propiedad de que la $j+1$ está en el derecho de ciclo. reclamo: $N(\alpha_j) = n!, N(\alpha_j \alpha_k) = \frac{n!}{2}, \ldots.$ lugar $1$ en el ciclo izquierdo y $2$ en el ciclo correcto como el primero de los elementos. ahora, $3$ tiene dos opciones, $4$ $2$ opciones, $\ldots (n+1) \mbox{has} n$ opciones. poniendo todo junto, $ N(\alpha_1) = n!.$
para probar la segunda afirmación, en lugar de $1,2$ como antes y poner $3$ a la derecha de $2.$ podemos colocar $4$ $3$ formas entre $1$ $2, 2$ $3$ o a la derecha de $3,$ hay $3$ maneras. misma manera que $5$ $4$ opciones que nos da $N(\alpha_j \alpha_k = \frac{n!}{2}.$
por simetría, $N(\alpha_j), N(\alpha_j \alpha_k), \ldots$ no dependen $j, k, \ldots.$
ahora estamos listos para aplicar el principio de inclusión-inclusión en el formulario $N[(1-\alpha_1)(1-\alpha_2)\ldots] = N(1) - {n \choose 1} N(\alpha_1) + {n \choose 2} N(\alpha_1 \alpha_2) + \ldots.$ esto nos da $$0 = s(n+1, 2) - \frac{n!}{1} {n \choose 1} + \frac{n!}{2}{n \choose 2} + \ldots $$
