Yo mismo estoy estudiando combinatoria este semestre. Pero el texto es difícil de seguir y sólo puedo entender el material básico, pero sin saber cómo demostrar el ejercicio de nivel intermedio. Quiero saber cómo demostrar $$s(n,k)=\sum_{j=0}^{n-k}(-1)^j{n-1+j\choose n-k+j}{2n-k\choose n-k-j}S(n-k+j,j)$$ Cualquier pista o solución detallada es bienvenida.
Respuestas
¿Demasiados anuncios?A partir de
$$(-1)^{n+k} {n\brack k} = \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-k+j} {2n-k\choose n-k-j} {n-k+j\brace j}$$
introducimos el EGF para los números de Stirling del segundo tipo en el RHS, obteniendo
$$\sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-k+j} {2n-k\choose n-k-j} (n-k+j)! [z^{n-k+j}] \frac{(\exp(z)-1)^j}{j!} \\ = (n-k)! [z^{n-k}] \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-k+j} {2n-k\choose n-k-j} {n-k+j\choose j} \frac{(\exp(z)-1)^j}{z^j}.$$
Ahora
$${n-1+j\choose n-k+j} {n-k+j\choose j} = \frac{(n-1+j)!}{(k-1)! \times j! \times (n-k)!} = {n-1\choose k-1} {n-1+j\choose n-1}$$
y encontramos
$$\frac{(n-1)!}{(k-1)!} [z^{n-k}] \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-1} {2n-k\choose n-k-j} \frac{(\exp(z)-1)^j}{z^j} \\ = \frac{(n-1)!}{(k-1)!} [z^{n-k}] \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-1} \frac{(\exp(z)-1)^j}{z^j} [w^{n-k-j}] (1+w)^{2n-k} \\ = \frac{(n-1)!}{(k-1)!} [w^{n-k}] (1+w)^{2n-k} [z^{n-k}] \sum_{j=0}^{n-k} (-1)^j {n-1+j\choose n-1} \frac{(\exp(z)-1)^j}{z^j} w^j.$$
Obsérvese que no hay contribución al extractor de coeficientes $[w^{n-k}]$ cuando $j\gt n-k$ por lo que podemos escribir
$$\frac{(n-1)!}{(k-1)!} [w^{n-k}] (1+w)^{2n-k} [z^{n-k}] \sum_{j\ge 0} (-1)^j {n-1+j\choose n-1} \frac{(\exp(z)-1)^j}{z^j} w^j \\ = \frac{(n-1)!}{(k-1)!} [w^{n-k}] (1+w)^{2n-k} [z^{n-k}] \frac{1}{(1+w(\exp(z)-1)/z)^n} \\ = \frac{(n-1)!}{(k-1)!} [w^{n-k}] (1+w)^{2n-k} [z^{n-k}] \frac{z^n/(\exp(z)-1)^n}{(w+z/(\exp(z)-1))^n}.$$
Trabajar con
$$\mathrm{Res}_{w=0} \frac{1}{w^{n-k+1}} (1+w)^{2n-k} \frac{1}{(w-C)^n}$$
calculamos los residuos en $C$ y en el infinito para aplicar el hecho de que deben sumar cero. Empezando por el primero, necesitamos (regla de Leibniz)
$$\frac{1}{(n-1)!} \left(\frac{1}{w^{n-k+1}} (1+w)^{2n-k}\right)^{(n-1)} \\ = \frac{1}{(n-1)!} \sum_{q=0}^{n-1} {n-1\choose q} \frac{(n-k+q)!}{(n-k)!} (-1)^q \frac{1}{w^{n-k+1+q}} \\ \times \frac{(2n-k)!}{(2n-k-(n-1-q))!} (1+w)^{2n-k-(n-1-q)} \\ = \sum_{q=0}^{n-1} {n-k+q\choose q} (-1)^q \frac{1}{w^{n-k+1+q}} {2n-k\choose n-1-q} (1+w)^{n-k+1+q} \\ = \left(\frac{1+w}{w}\right)^{n-k+1} \sum_{q=0}^{n-1} {n-k+q\choose q} (-1)^q {2n-k\choose n-1-q} \left(\frac{1+w}{w}\right)^{q}.$$
Tenemos dos observaciones importantes, la primera es que
$$\frac{z^n}{(\exp(z)-1)^n} = 1+\cdots$$
es decir, que no hay ningún polo en el cero y que
$$\left.\frac{1+w}{w}\right|_{w=-z/(\exp(z)-1)} = \frac{1+z-\exp(z)}{z} = -\frac{1}{2} z + \cdots.$$
Por lo tanto, al sustituir en el extractor de coeficientes en $[z^{n-k}]$ obtenemos para todos los términos de la suma
$$[z^{n-k}] (1+\cdots) \left(-\frac{1}{2} z + \cdots\right)^{n-k+1} \times \left(-\frac{1}{2} z + \cdots\right)^q = 0,$$
es decir, debido al término medio hay una contribución nula de la residuo en $w=-z/(\exp(z)-1).$ Volviendo al cálculo principal obtenemos obtenemos para el residuo en el infinito
$$\mathrm{Res}_{w=\infty} \frac{1}{w^{n-k+1}} (1+w)^{2n-k} \frac{1}{(w-C)^n} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^2} w^{n-k+1} (1+1/w)^{2n-k} \frac{1}{(1/w-C)^n} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^2} w^{2n-k+1} \frac{(1+w)^{2n-k}}{w^{2n-k}} \frac{1}{(1-Cw)^n} \\ = - \mathrm{Res}_{w=0} \frac{1}{w} (1+w)^{2n-k} \frac{1}{(1-Cw)^n} = -1.$$
Al invertir el signo y sustituirlo en el extractor de coeficientes en $z$ obtenemos
$$\frac{(n-1)!}{(k-1)!} [z^{n-k}] \frac{z^n}{(\exp(z)-1)^n} \\ = \frac{(n-1)!}{(k-1)!} \mathrm{Res}_{z=0} \frac{1}{z^{n-k+1}} \frac{z^n}{(\exp(z)-1)^n}.$$
Sumando obtenemos para el OGF
$$\sum_{k=1}^n x^k \frac{(n-1)!}{(k-1)!} \mathrm{Res}_{z=0} \frac{z^{k-1}}{(\exp(z)-1)^n} \\ = x (n-1)! \times \mathrm{Res}_{z=0} \frac{1}{(\exp(z)-1)^n} \sum_{k=1}^n \frac{x^{k-1} z^{k-1}}{(k-1)!} \\ = x (n-1)! \times \mathrm{Res}_{z=0} \frac{\exp(xz)}{(\exp(z)-1)^n}.$$
Ahora evaluamos el residuo para $1\le x\le n$ un número entero. Tenemos
$$\mathrm{Res}_{z=0} \frac{\exp(xz)}{(\exp(z)-1)^n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(xz)}{(\exp(z)-1)^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((x-1)z)}{(\exp(z)-1)^n} \exp(z) \; dz $$
y poniendo $\exp(z) = w$ para que $\exp(z) \; dz = dw$ obtenemos
$$\frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{w^{x-1}}{(w-1)^n} \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(w-1)^n} \sum_{q=0}^{x-1} {x-1\choose q} (w-1)^q\; dw.$$
Este valor es cero cuando $x-1\lt n-1$ o $x\lt n$ y es uno cuando $x=n.$ Por construcción el residuo es un polinomio en $x$ de grado $n-1.$ Tenemos el $n-1$ raíces, están en $x=1,2,\ldots,n-1$ por lo que sabemos que es
$$Q (x-1)(x-2)\times\cdots\times (x-(n-1)).$$
Pero también sabemos que en $x=n$ se evalúa a uno, por lo que debemos tener $$Q (n-1)(n-2)\times\cdots\times 1 = 1$$ o $Q=1/(n-1)!.$ Restaurando los dos términos anteriores obtenemos finalmente
$$x(n-1)! \times \frac{1}{(n-1)!} (x-1)(x-2)\times\cdots\times (x-(n-1)) \\ = x(x-1)(x-2)\times\cdots \times (x-(n-1)) = \sum_{k=1}^n (-1)^{n+k} {n\brack k} x^k$$
que es precisamente el número de Stirling OGF, del primer tipo, y hemos terminado.
No es una respuesta sino un comentario largo.
Buena prueba, Marko Riedel. Yo añadiría que se puede llegar al final un poco más rápido a partir de 'Al voltear el signo...' Utiliza el poli de Norlund para concluir $$[z^{n-k}]\Big(\frac{z}{e^z-1}\Big)^n = [z^{n-k}]\sum_{m=0}^\infty\frac{z^m}{m!}B_m^{(n)}(0)=\frac{B_{n-k}^{(n)}(0)}{(n-k)!}.$$
Entonces utiliza el hecho conocido de que $$ \begin{bmatrix} n \\ k \\ \end{bmatrix} = \frac{(n-1)!}{(k-1)!} \,\frac{B_{n-k}^{(n)}(0)}{(n-k)!} $$