TAOCP 1.2.6 Exercise 55

Let P=\bigl(\binom{n}{k}\bigr)_{n,k\ge 0} be Pascal's triangle regarded as an infinite lower-triangular matrix.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 55. [M21] Considering each of Stirling's triangles as matrices, determine their inverses.

Verified: yes
Solve time: 1m33s

Solution

Let

$$ P=\bigl(\binom{n}{k}\bigr)_{n,k\ge 0} $$

be Pascal's triangle regarded as an infinite lower-triangular matrix. Exercise 54 asks for the inverse of $P$, namely

$$ P^{-1}=\bigl((-1)^{,n-k}\binom{n}{k}\bigr)_{n,k\ge0}. \tag{1} $$

The two Stirling triangles are the matrices

$$ S=\bigl[{n\atop k}\bigr]{n,k\ge0}, \qquad s=\bigl[{n\atop k}\bigr]{!!*,,n,k\ge0}, $$

where $\bigl[{n\atop k}\bigr]$ denotes the Stirling numbers of the second kind and $\bigl[{n\atop k}\bigr]_{!*}$ denotes the Stirling numbers of the first kind with signs. By their defining expansions,

$$ x^n=\sum_{k=0}^{n}\bigl[{n\atop k}\bigr]_{!*},x^{\underline{k}}, \tag{2} $$

and

$$ x^{\underline{n}} =\sum_{k=0}^{n}\bigl{n\atop k}\bigr^{,n-k}x^k . \tag{3} $$

Equation (2) expresses the ordinary powers $x^n$ in terms of the falling-factorial basis $x^{\underline{k}}$. Equation (3) expresses the falling-factorial basis in terms of the ordinary powers.

Substituting (3) into (2) gives

$$ x^n = \sum_{k=0}^{n} \bigl[{n\atop k}\bigr]{!*} \sum{m=0}^{k} \bigl[{k\atop m}\bigr] (-1)^{,k-m}x^m. $$

Interchanging the order of summation,

$$ x^n = \sum_{m=0}^{n} \left( \sum_{k=m}^{n} \bigl[{n\atop k}\bigr]_{!*} \bigl[{k\atop m}\bigr] (-1)^{,k-m} \right) x^m. $$

Since the coefficients of $x^m$ in $x^n$ are $\delta_{nm}$, where $\delta_{nm}$ is the Kronecker delta,

$$ \sum_{k=m}^{n} \bigl[{n\atop k}\bigr]{!*} \bigl[{k\atop m}\bigr] (-1)^{,k-m} = \delta{nm}. \tag{4} $$

Equation (4) states exactly that the matrix

$$ \Bigl(\bigl[{n\atop k}\bigr]_{!*}\Bigr) $$

is the inverse of the matrix

$$ \Bigl((-1)^{,n-k}\bigl[{n\atop k}\bigr]\Bigr). $$

Hence

$$ \boxed{ \left(\bigl[{n\atop k}\bigr]\right)^{-1} = \left((-1)^{,n-k}\bigl[{n\atop k}\bigr]_{!*}\right). } \tag{5} $$

Applying the same argument in the opposite order, substituting (2) into (3), yields

$$ \sum_{k=m}^{n} (-1)^{,n-k} \bigl[{n\atop k}\bigr] \bigl[{k\atop m}\bigr]{!*} = \delta{nm}, $$

which states that

$$ \boxed{ \left(\bigl[{n\atop k}\bigr]_{!*}\right)^{-1} = \left((-1)^{,n-k}\bigl[{n\atop k}\bigr]\right). } \tag{6} $$

Therefore the inverses of the two Stirling triangles are obtained by changing the sign of every entry whose row and column indices have opposite parity:

$$ \boxed{ \left(\text{Stirling numbers of the second kind}\right)^{-1} = \left((-1)^{,n-k} \text{Stirling numbers of the first kind}\right), } $$

$$ \boxed{ \left(\text{Stirling numbers of the first kind}\right)^{-1} = \left((-1)^{,n-k} \text{Stirling numbers of the second kind}\right). } $$

This completes the proof.

∎