Combinatoria de la prueba que $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}$

Question

Este reciente pregunta contiene dos pruebas que $$\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}.$$ Uno, por Antonio Vargas, utiliza una integral doble. El otro, por mí, utiliza la absorción de identidad dos veces. Me gustaría ver una combinatoria de prueba, pero no he logrado llegar a uno todavía.

Algunos pensamientos hasta el momento:

1. Desde el lado de la derecha está claro que no es un número entero para $n \geq 1$, podemos necesidad de interpretar la identidad como una probabilidad. Yo aceptaría una combinatoria basada argumento de probabilidad.
2. Alternativamente, podríamos girar a ambos lados en los enteros multiplicando por $(n+1)!^2$. La nueva identidad se $$ \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k (n+1)!^2}{(k+1)^2} = (n+1)! \, n! \, H_{n+1}.$$ aceptaría una combinatoria prueba de esta versión de la identidad.
3. Necesitamos una combinatoria de interpretación de la armónica de los números. Hay dos en este papel por Benjamin, Preston, y Quinn. La primera es que el $n! \, H_n$ es el número de permutaciones en $n+1$ elementos que contienen exactamente dos ciclos. Esto implica que a $\dfrac{H_n}{n+1}$ (muy cerca del lado derecho de la identidad que queremos probar) es la probabilidad de que una permutación aleatoria en $n+1$ elementos contiene exactamente dos ciclos. La segunda interpretación en el papel es que una permutación aleatoria en $n$ elementos tiene, en promedio, $H_n$ ciclos.
4. Es probable que la necesidad de inclusión/exclusión para interpretar el lado izquierdo.

Answer 1

He encontrado un probabilística de la prueba con una combinatoria de sabor. Voy a publicar aquí, así que esta pregunta es oficialmente respondió, así como para cualquier persona que pueda estar interesado en verlo.

Seleccione los puntos de $(x_1, y_1), (x_2, y_2), \ldots, (x_{n+1}, y_{n+1})$ independientemente de la bivariante distribución uniforme sobre la unidad de la plaza.

Cada lado es la probabilidad de que, para todos los $i \in \{2, 3, \ldots, n+1 \}$, $x_1 < x_i$ o $y_1 < y_i$.

Lado izquierdo: Vamos a $A_i$ denotar el caso de que cualquiera de las $x_1 < x_i$ o $y_1 < y_i$. Queremos $\cap_{i=2}^{n+1} A_i$, la cual puede ser calculada a través de la inclusión-exclusión. El uso de la inclusión-exclusión, tenemos que la probabilidad de que $x_1 > x_i$ $y_1 > y_i$ para cualquier colección de $k$ de los puntos en $\{(x_2, y_2), \ldots, (x_{n+1}, y_{n+1})\}$. Esta es la probabilidad de que $x_1$ es el más grande de $k+1$ al azar elegido puntos y $y_1$ es el más grande de $k+1$ al azar-puntos escogidos. Puesto que el $x_i$'s y $y_i$'s son independientes, esto es $\dfrac{1}{(k+1)^2}$. Por lo tanto, una manera de calcular la probabilidad que buscamos es $$1 - \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k-1}}{(k+1)^2} = \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2}.$$

Lado derecho: Condición en la posición de $x_1$ en el ordenamiento de las $x_i$'s de menor a mayor. La probabilidad de que $x_1$ es el más pequeño es $\dfrac{1}{n+1}$, la probabilidad de que $x_1$ es el segundo más pequeño es $\dfrac{1}{n+1}$, y así sucesivamente, independientemente de la posición que $x_1$ toma en el ordenamiento de las $x_i$'s. Entonces, dado que el $x_1$ $k+1$ más pequeña de las $x_i$'s, debemos tener $y_1 < y_j$ por cada $j$ tal que $x_j < x_1$. Desde allí se $k$ estos $y_j$, la probabilidad de que $y_1$ es menor que todas las $k$$\dfrac{1}{k+1}$. Resumiendo, tenemos que la probabilidad que buscamos también es $$\frac{1}{n+1} \sum_{k=0}^n \frac{1}{k+1} = \frac{H_{n+1}}{n+1}.$$