TAOCP 4.7 Exercise 19

Section 4.7: Manipulation of Power Series

Exercise 19. [**] [M25] Continuing exercise 17, express all the numbers $v_{nk}$ in terms of the numbers $v_n = v_{n1} = n!, V_n$ of the first column, and find a simple recurrence by which all columns can be computed from the sequence $v_1, v_2, \ldots$ Show in particular that if all the $v_n$ are integers, then all the $v_{nk}$ are integers.

Verified: yes
Solve time: 8m05s

Let

$$ F(z,u)=\sum_{n\ge0}\frac{V(z)^n}{n!}u^n =e^{uV(z)}. $$

Since

$$ V(z)=\sum_{m\ge1}v_m\frac{z^m}{m!}, \qquad v_m=m!,V_m, $$

we have

$$ F(z,u) =\exp!\left(u\sum_{m\ge1}v_m\frac{z^m}{m!}\right). $$

But

$$ \frac{V(z)^n}{n!} =\sum_{k\ge0}v_{nk}z^k, $$

hence

$$ F(z,u) =\sum_{k\ge0}\left(\sum_{n\ge0}v_{nk}u^n\right)z^k . $$

Comparing this with the standard exponential generating function for the complete Bell polynomials gives

$$ \sum_{n\ge0}v_{nk}u^n =\frac1{k!},B_k(uv_1,uv_2,\ldots,uv_k). $$

Therefore every $v_{nk}$ is a polynomial in the first-column entries $v_1,v_2,\ldots,v_k$ with integer coefficients. Explicitly,

$$ v_{nk} = \sum_{\substack{j_1+j_2+\cdots=n\ j_1+2j_2+3j_3+\cdots=k}} \prod_{m\ge1} \frac{v_m^{,j_m}}{j_m!,(m!)^{j_m}}. $$

A simple recurrence is obtained by differentiating $F(z,u)$ with respect to $z$:

$$ \frac{\partial F}{\partial z} = uV'(z)F. $$

Comparing coefficients of $u^nz^{k-1}$ yields

$$ k,v_{nk} = \sum_{m=1}^{k} \frac{v_m}{(m-1)!},v_{n-1,k-m}, \qquad n\ge1,\ k\ge1, $$

with initial values

$$ v_{00}=1,\qquad v_{0k}=0\ (k>0). $$

Thus every column $k$ is obtained recursively from the sequence $v_1,v_2,\ldots,v_k$ and the previously computed columns. Since the recurrence uses only addition and multiplication by the integers $v_m/(m-1)!$, and since the explicit Bell-polynomial formula has integer coefficients, induction on $k$ shows that all $v_{nk}$ are integers whenever all $v_n$ are integers.

$$ \boxed{\text{All }v_{nk}\text{ are polynomial expressions in }v_1,v_2,\ldots,v_k,\text{ and hence are integers if all }v_n\text{ are integers.}} $$