A complicated combinatoric equation for Stirling number

Question

I'm self studying combinatoric this semester. But the text is hard to follow and I can only understand the basic material, but not knowing how to prove the intermediate level exercise. I want to know how to prove $$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)$$ Any hint or detail solution is welcome.

Answer 1

Starting from

$$(-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}$$

we introduce the EGF for Stirling numbers of the second kind on the RHS, getting

$$\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}.$$

Now

$${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}$$

and we find

$$\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.$$

Note that there is no contribution to the coefficient extractor $[w^{n-k}]$ when $j\gt n-k$, so we may write

$$\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}.$$

Working with

$$\mathrm{Res}_{w=0} \frac{1}{w^{n-k+1}} (1+w)^{2n-k} \frac{1}{(w-C)^n}$$

we compute the residues at $C$ and at infinity in order to apply the fact that they must sum to zero. Starting with the first we require (Leibniz rule)

$$\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}.$$

We have two important observations, the first is that

$$\frac{z^n}{(\exp(z)-1)^n} = 1+\cdots$$

i.e. no pole at zero and that

$$\left.\frac{1+w}{w}\right|_{w=-z/(\exp(z)-1)} = \frac{1+z-\exp(z)}{z} = -\frac{1}{2} z + \cdots.$$

Hence on substituting into the coefficient extractor on $[z^{n-k}]$ we get for all sum terms

$$[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,$$

i.e. due to the middle term there is zero contribution from the residue at $w=-z/(\exp(z)-1).$ Returning to the main computation we get for the residue at infinity

$$\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.$$

On flipping the sign and substituting into the coefficient extractor on $z$ we get

$$\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}.$$

Summing we get for the 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}.$$

Now we evaluate the residue for $1\le x\le n$ an integer. We have

$$\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 $$

and putting $\exp(z) = w$ so that $\exp(z) \; dz = dw$ we obtain

$$\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.$$

This is zero when $x-1\lt n-1$ or $x\lt n$ and it is one when $x=n.$ By construction the residue is a polynomial in $x$ of degree $n-1.$ We have the $n-1$ roots, they are at $x=1,2,\ldots,n-1$ so we know it is

$$Q (x-1)(x-2)\times\cdots\times (x-(n-1)).$$

But we also know that at $x=n$ it evaluates to one, so we must have $$Q (n-1)(n-2)\times\cdots\times 1 = 1$$ or $Q=1/(n-1)!.$ Restoring the two terms in front we finally obtain

$$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$$

which is precisely the Stirling number OGF, first kind, and we are done.

Answer 2

Not an answer but a long comment.

Nice proof, Marko Riedel. I would add that you can get to the end a little faster starting from 'On flipping the sign...' Use the Norlund poly to conclude $$[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)!}.$$

Then use the known fact that $$ \begin{bmatrix} n \\ k \\ \end{bmatrix} = \frac{(n-1)!}{(k-1)!} \,\frac{B_{n-k}^{(n)}(0)}{(n-k)!} $$