Orthogonality of stirling numbers

[bkarpuz]

Dear MHB members,

denote by $s_{n,k}$ and $S_{n,k}$ Stirling numbers of the first-kind and of the second-kind, respectively.
I need to see the proof of the identity $\sum_{j=k}^{n}S(n,j)s(j,k)=\sum_{j=k}^{n}s(n,j)S(j,k)=\delta _{{n,k}}$.
Please let me know if you know a reference in this direction.

Many thanks.
bkarpuz

 

[PaulRS]

As stated, the result is not true, it should be: \[\sum_{j=k}^n (-1)^{n-j} S(n,j) s(j,k) = \sum_{j=k}^n (-1)^{n-j} s(n,j) S(j,k) =\delta_{n,k}\]

First we note that \[\displaystyle\sum_{n\geq 0} S(n,k) \displaystyle\frac{x^n}{n!} = \frac{1}{k!}\cdot\left(\frac{x^1}{1!} + \frac{x^2}{2!}+...\right)^k = \frac{1}{k!}\cdot\left(e^x - 1\right)^k (*)\]

Thus we write \[ A(x) := \displaystyle\sum_{n} \left( \displaystyle\frac{x^n}{n!} \cdot \sum_{j} (-1)^{n-j} S(n,j) s(j,k) \right) = \sum_j \left( \sum_n S(n,j) \cdot \displaystyle\frac{(-x)^n}{n!} \right) \cdot s(j,k) \cdot (-1)^j = \sum_j \frac{\left(1 - e^{-x}\right)^j}{j!} \cdot s(j,k)\]

And on the other hand \[ \sum_{j,k} s(j,k)\cdot \frac{x^j}{j!}\cdot y^k = \exp\left(y\cdot \log\left(\frac{1}{1-x}\right)\right) (**)\]

Thus \[ \sum_j s(j,k) \cdot \frac{x^j}{j!} = \frac{1}{k!}\cdot \log^k\left(\frac{1}{1-x}\right)\]

And \[A(x) = \sum_j \frac{\left(1 - e^{-x}\right)^j}{j!} \cdot s(j,k) = \frac{1}{k!}\cdot \log^k\left(\frac{1}{1-(1 - e^{-x})}\right) = \frac{x^k}{k!} \]

Which indeed implies $\sum_{j=k}^n (-1)^{n-j} S(n,j) s(j,k) =\delta_{n,k}$. $\square$ ( I will leave the other identity to you (Wink) )

For (*), note that the coefficient of $x^n$ in $\frac{1}{k!}\cdot\left(\frac{x^1}{1!} + \frac{x^2}{2!}+...\right)^k $ is actually $ \frac{1}{k!}\cdot \sum_{d_1+...+d_k = n ; d_i > 0} \frac{1}{d_1!\cdot d_2!\cdot ... d_k!} $ , and so if we multiply it by $n!$ we get $ \frac{1}{k!}\cdot \sum_{d_1+...+d_k = n ; d_i > 0} \frac{n!}{d_1!\cdot d_2!\cdot ... d_k!} $ which should ring a bell.

Indeed $\frac{n!}{d_1!\cdot d_2!\cdot ... d_k!}$ is the number of permutations with repetitions, in which you have $n$ elements, $d_1$ of type $1$, etc... so we are actually putting $n$ elements into $k$ (non-empty) boxes. But since what we want are partitions, we don't really care about the renaming of those "boxes", thus the $\frac{1}{k!}$ and $(*)$ is proved.

Now for $(**)$ note that $ \exp\left(y\cdot \log\left(\frac{1}{1-x}\right)\right) = \exp\left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right) = \displaystyle\sum_{k=0}^{\infty}{\frac{1}{k!}\cdot \left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right)^k}$. And here by a similar idea, the coefficient of $x^a y^k$ in $\frac{1}{k!}\cdot \left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right)^k$ corresponds to the number of permutations of $a$ elements into $k$ cycles (remember $(n-1)!$ is the number of cyclic permutations of $n$ elements) , but divided by $a!$.

Some references :

• Analytic Combinatorics by Flajolet and Sedgewick. Page 736 of the book ( page 752 of the pdf available online). States $(*)$ and $(**)$
• Generatingfunctionology by Herbert Wilf. Page 174 exercise 12 is related (in fact you the reader is expected to discover your identities), and $(**)$ appears in page 87 as a result of the theory developed in that chapter.

Both references are freely available online! :D

 

[bkarpuz]

As stated, the result is not true, it should be: \[\sum_{j=k}^n (-1)^{n-j} S(n,j) s(j,k) = \sum_{j=k}^n (-1)^{n-j} s(n,j) S(j,k) =\delta_{n,k}\]

Thank you very much PaulRS for your reply.
But if you seach in google DLMF: §26.8 Set Partitions: Stirling Numbers and see Equation 26.8 therein,
you will find the formula I have mentioned above. Also I have multiplied the table of Stirling numbers with n=k=4, and I got the identity matrix.
I believe there is a straight computation of that formula.

Best regards.
bkarpuz

 

[PaulRS]

Thank you very much PaulRS for your reply.
But if you seach in google DLMF: §26.8 Set Partitions: Stirling Numbers and see Equation 26.8 therein,
you will find the formula I have mentioned above. Also I have multiplied the table of Stirling numbers with n=k=4, and I got the identity matrix.
I believe there is a straight computation of that formula.

Best regards.
bkarpuz

Ah, I see, you are using a signed version of Stirling numbers! so actually $s_{mine}(n,k) = (-1)^{n-k} \cdot s_{yours} (n,k)$ and we agree. (Rofl)

I was using $s(n,k) = \left [ \begin{matrix}
n \\ k

\end{matrix} \right ] $ the number of permutations of $n$ elements with exactly $k$ cycles.

Minor modifications to the proof above get you to your identity.