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.

 

[blue_raver22]

Dear bkarpuz,

Thank you for your question. The orthogonality of Stirling numbers is a well-known result in combinatorics and has been proven in various sources. One reference that provides a proof for this identity is the book "Concrete Mathematics" by Graham, Knuth, and Patashnik. Another reference is the paper "Orthogonality of Stirling numbers and the Cauchy identity" by Gessel and Zhu.

To give a brief explanation, the identity you mentioned can be proved using the properties of Stirling numbers and the Cauchy identity. The first term in the identity, $\sum_{j=k}^{n}S(n,j)s(j,k)$, represents the number of ways to partition a set of $n$ elements into $k$ non-empty subsets and then further partition each of those subsets into $j$ non-empty subsets. The second term, $\sum_{j=k}^{n}s(n,j)S(j,k)$, represents the number of ways to first partition a set of $n$ elements into $j$ non-empty subsets and then further partition each of those subsets into $k$ non-empty subsets. The sum over all values of $j$ ensures that all possible combinations are accounted for.

By the Cauchy identity, these two expressions are equal to the Kronecker delta function, which is 1 when $n=k$ and 0 otherwise. This means that the only case where the two expressions are equal is when $n=k$, which proves the orthogonality of Stirling numbers.

I hope this helps. Good luck with your research.

Sincerely,