# Another combinatorial determinant

(May 18, 1999)  

The following result, a special case of a theorem of Mina , was recently given an elegant proof by Wilf .

###### Theorem 1.

Let $`f=1+a_1x+a_2x^2+\mathrm{}`$ be a formal power series, and define a matrix $`c`$ by

$$c_{i,j}=[x^j]f^i(i,j0).$$

(Here $`[x^j]f`$ denotes the coefficient of $`x^j`$ in $`f`$.) Then

$$det\left((c_{i,j})_{i,j=0}^n\right)=a_1^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$

The purpose of this paper is to show that this result remains essentially unchanged if we take powers in the sense of composition, instead of multiplication.

###### Theorem 2.

Let $`f=x+b_1x^2+b_2x^3+\mathrm{}`$ be a formal power series, and define $`f^{(0)}=x`$ and $`f^{(i)}=f(f^{(i1)})`$ for $`i>0`$. Define a matrix $`c`$ by

$$c_{i,j}=[x^{j+1}]f^{(i)}(i,j0).$$

Then

$$det\left((c_{i,j})_{i,j=0}^n\right)=1!2!\mathrm{}n!b_1^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$

In fact, we prove both of these theorems at once, by formulating and proving a common generalization. In both theorems, each row of the matrix is obtained from the previous row by applying a certain transformation of power series: in Theorem 1, the transformation is

$$tt(1+a_1x+a_2x^2+\mathrm{}),$$

while in Theorem 2, the transformation is

$$tt+b_1t^2+b_2t^3+\mathrm{}.$$

This suggests that more generally, we should consider transformations of the form

$$tf(t)=\underset{m=1}{\overset{\mathrm{}}{}}\underset{n=0}{\overset{\mathrm{}}{}}b_{m,n}t^mx^n.$$

###### Theorem 3.

Let $`f(t)=_{m=1}^{\mathrm{}}_{n=0}^{\mathrm{}}b_{m,n}t^mx^n`$ be a formal power series in two variables $`t`$ and $`x`$, and assume $`b_{1,0}=1`$. Define $`f^{(0)}(t)=t`$ and $`f^{(i)}(t)=f(f^{(i1)}(t))`$ for $`i>0`$. Define a matrix $`c`$ by

$$c_{i,j}=[x^{j+1}]f^{(i)}(x)(i,j0).$$

Then

$$det\left((c_{i,j})_{i,j=0}^n\right)=\underset{k=1}{\overset{n}{}}\left(\underset{m=0}{\overset{k}{}}m!\left\{\genfrac{}{}{0.0pt}{}{k+1}{m+1}\right\}b_{2,0}^mb_{1,1}^{km}\right)(n=0,1,2,\mathrm{}),$$

where $`\left\{\genfrac{}{}{0.0pt}{}{x}{y}\right\}`$ is the Stirling number of the second kind (the number of partitions of $`x`$ labeled objects into $`y`$ nonempty sets).

###### Proof.

Following , we prove that the matrix

$$b_{i,j}=(1)^{i+j}\left(\genfrac{}{}{0pt}{}{i}{j}\right)(i,j0)$$

has the property that $`bc`$ is upper triangular. Put

$$g_i(t)=\underset{k}{}(1)^{i+k}\left(\genfrac{}{}{0pt}{}{i}{k}\right)f^{(k)}(t);$$

then $`(bc)_{i,j}=[x^j]g_i(x)`$, and the theorem will follow from the fact that

$$g_i(t)=\underset{j=0}{\overset{i}{}}j!\left\{\genfrac{}{}{0.0pt}{}{i+1}{j+1}\right\}b_{2,0}^jb_{1,1}^{ij}t^{j+1}x^{ij}+\text{higher-order terms},$$

which we prove by induction on $`i`$ (the case $`i=0`$ being true by definition). If we write $`g_{i1}(t)=_{m,n}k_{m,n}t^{m+1}x^n`$ (so in particular, $`k_{m,n}=0`$ for $`m+n<i1`$ and $`k_{m,n}=m!\left\{\genfrac{}{}{0.0pt}{}{m+n+1}{m+1}\right\}b_{2,0}^mb_{1,1}^n`$ for $`m+n=i1`$), then

$`g_i(t)`$ $`=g_{i1}(f(t))g_{i1}(f(t))`$   
$`={\displaystyle \underset{m,n}{}}k_{m,n}x^n(f(t)^{m+1}t^{m+1})`$   
$`={\displaystyle \underset{m,n}{}}k_{m,n}x^nt^{m+1}[(m+1)(f(t)/t1)\left({\displaystyle \genfrac{}{}{0pt}{}{m+1}{2}}\right)(f(t)/t1)^2+\mathrm{}]`$   
$`={\displaystyle \underset{m+n=i1}{}}(m+1)k_{m,n}t^{m+1}x^n(b_{2,0}t+b_{1,1}x)+\text{higher-order terms}`$   
$`={\displaystyle \underset{m+n=i}{}}t^{m+1}x^n[(m+1)b_{1,1}k_{m,n1}+mb_{2,0}k_{m1,n}]+\text{higher-order terms}`$   
$`={\displaystyle \underset{m+n=i}{}}t^{m+1}x^nm!b_{2,0}^mb_{1,1}^n\left(\left\{{\displaystyle \genfrac{}{}{0.0pt}{}{i}{m}}\right\}+(m+1)\left\{{\displaystyle \genfrac{}{}{0.0pt}{}{i}{m+1}}\right\}\right)+\text{higher-order terms}`$   
$`={\displaystyle \underset{m+n=i}{}}t^{m+1}x^nm!b_{2,0}^mb_{1,1}^n\left\{{\displaystyle \genfrac{}{}{0.0pt}{}{i+1}{m}}\right\}+\text{higher-order terms},`$   
as desired. ∎

It should be pointed out that the full version of Mina’s theorem, which states that

$$det\left\{\left(\frac{d^j}{dx^j}f(x)^i\right)_{i,j=0}^n\right\}=1!2!\mathrm{}n!f^{}(x)^{n(n+1)/2},$$

does not appear to admit an analogous generalization. The difficulty seems to be that while Mina’s theorem follows from applying Theorem 1 to the Taylor expansion of $`f(x)/f(t)`$ at $`t`$ for each $`t`$, Theorem 2 can only be applied to the Taylor expansion of $`f`$ at its fixed points.