3
$\begingroup$

While computing conditional expectations of certain functionals of a Poisson white noise field (details are long and probably irrelevant), I've stumbled upon the need to use the following identity involving Stirling numbers of the second kind: $$ \ell{k\brace \ell} = \sum_{j=\ell}^k {k\choose j-1} (-1)^{k-j} {j\brace \ell}. $$ I used Manuel Kauers' Stirling package in order to produce a recurrence relation from which the identity can be easily proved. I still wonder, however, whether this is actually well-known, or there is some short proof...

$\endgroup$
1
  • 1
    $\begingroup$ Looks similar to identity $(6.17)$ from Graham, Knuth, Patashnik's book. $\endgroup$
    – Negan
    Dec 5 '17 at 16:42
5
$\begingroup$

You can give a short proof by interpreting the identity as an instance of inclusion-exclusion. The left hand side counts the number of ways of partitioning $S=\{1,2,\dots,k\}$ into $\ell$ parts and then picking one of the parts as the designated one.

Let $A_i$ denote the number of partitions of $S$ into $\ell$ parts where the designated part contains $i$. You can check that the left hand side is counting $|A_1\cup A_2\cup \cdots \cup A_k|$. For the right hand side notice that $$|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_r}|={k-r+1\brace \ell}$$ So by inclusion-exclusion we get $$|A_1\cup A_2\cup \cdots \cup A_k|=\sum_{r=1}^{k-l+1}(-1)^{r-1}\binom{k}{r}{k-r+1\brace \ell}$$ and reindexing by $j=k-r+1$ gives your identity.

$\endgroup$
5
$\begingroup$

The identity can be proved by equating coefficients of $z^k/k!$ in $$ l \frac{(e^z-1)^l}{l!}= (1-e^{-z}) \frac{d\ }{dz} \frac{(e^z-1)^l}{l!}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.