Una identidad de número de Stirling que representa los números eulerianos de segundo orden.

Question

Graham, Knuth y Patashnik dan en CMath una introducción completa a los números de Stirling. En la tabla 250 y la tabla 251, recopilan dos páginas de identidades de los números Stirling.

Por supuesto, hay muchas más identidades de este tipo. Aquí damos una que no está incluida y que no pudimos encontrar en ninguna otra parte (lo que significa poco), pero que quizás le gustaría a Knuth. Se pueden demostrar con las técnicas de CMath. Tal vez alguien disfrute mostrándonos la prueba?

Al igual que en CMath, los números de los ciclos Stirling son sin signo. {n, k} y [n, k] se definen para 0 <= k <= n, y para este rango se cumple la siguiente identidad:

$$ \sum \limits_{j\,=\,0}^{k} (-1)^{k-j}\binom{2n+1}{k-j} {n+j \brace j} = \sum \limits_{j\,=\,0}^{n-k} (-1)^j \binom{2n+1}{j} {n+m \brack m} $$

Para una mejor legibilidad utilizamos el atajo $ m = n-k-j+1$ .

Las referencias a la OEIS son A132393 , A048993 y A340556 .

Answer 1

Pretendemos demostrar que con $0\le k\le n$ se cumple la siguiente identidad:

$$\sum_{j=0}^k (-1)^{k-j} {2n+1\choose k-j} {n+j\brace j} = \sum_{j=0}^{n-k} (-1)^j {2n+1\choose j} {2n-k-j+1\brack n-k-j+1}.$$

Empezaremos por el LHS. El capítulo 6.2 sobre los números eulerianos de Matemáticas concretas de Knuth et al. propone la fórmula

$${n\brace m} = (-1)^{n-m+1} \frac{n!}{(m-1)!} \sigma_{n-m}(-m)$$

donde $\sigma_n(x)$ es un polinomio de Stirling y tenemos la identidad

$$\left(\frac{1}{z} \log\frac{1}{1-z}\right)^x = x \sum_{n\ge 0} \sigma_n(x+n) z^n.$$

Obtenemos

$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^x = x \sigma_{n-m}(x+n-m)$$

y por lo tanto

$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n} = -n \sigma_{n-m}(-m)$$

lo que implica que para $n\ge m\ge 1$

$$\bbox[5px,border:2px solid #00A000]{ {n\brace m} = (-1)^{n-m} \frac{(n-1)!}{(m-1)!} [z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n}.}$$

Esto da para el LHS

$$\sum_{j=1}^k (-1)^{k-j} {2n+1\choose k-j} (-1)^n \frac{(n+j-1)!}{(j-1)!} [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-j} \\ = (-1)^{n-k+1} n! [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1} [w^{k-1}] (1+w)^{2n+1} \\ \times \sum_{j=1}^k {n+j-1\choose n} (-1)^{j-1} w^{j-1} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-j+1}.$$

Ahora el extractor de coeficientes en $w$ impone el límite superior de la y podemos ampliar $j$ hasta el infinito, obteniendo

$$(-1)^{n-k+1} n! [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1} [w^{k-1}] (1+w)^{2n+1} \frac{1}{(1+w/(\frac{1}{z} \log\frac{1}{1-z}))^{n+1}} \\ = (-1)^{n-k+1} n! [z^n] [w^{k-1}] (1+w)^{2n+1} \frac{1}{(w+\frac{1}{z} \log\frac{1}{1-z})^{n+1}}.$$

Continuando,

$$ (-1)^{n-k+1} n! [z^n] [w^{n+k}] (1+w)^{2n+1} \frac{1}{(1+\frac{1}{w} \frac{1}{z} \log\frac{1}{1-z})^{n+1}} \\ = (-1)^{n-k+1} n! [z^n] [w^{n+k}] (1+w)^{2n+1} \sum_{q\ge 0} {n+q\choose n} (-1)^q \frac{1}{w^q} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^q \\ = (-1)^{n-k+1} n! [z^n] \sum_{j=n+k}^{2n+1} {2n+1\choose j} {n+j-(n+k)\choose n} (-1)^{j-(n+k)} \\ \times \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j-(n+k)} \\ = (-1)^{n-k+1} n! [z^n] \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} n! \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} [z^{n+j}] \left(\log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} n! \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} \\ \times \frac{j!}{(n+j)!} \times (n+j)! [z^{n+j}] \frac{1}{j!} \left(\log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} (-1)^j {n+j\brack j} \\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1} {2n+1\choose 2n-j+1} (-1)^{n-k-j+1} {2n-k-j+1\brack n-k-j+1} \\ = \sum_{j=0}^{n-k+1} {2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$

El número de Stirling es cero para $j=n-k+1$ y obtenemos por fin

$$\sum_{j=0}^{n-k} {2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$

Este es el RHS y tenemos el reclamo.