TAOCP 4.7 Exercise 9

For the reversion of $z = t - t^2,$ Algorithm T is applied to the general form $U_1 z + U_2 z^2 + \cdots = t + V_2 t^2 + V_3 t^3 + \cdots,$ so here $U_1 = 1,\quad U_n = 0 \ (n \ge 2), \qquad V_2 = -1,...

taocpmathematicsalgorithmsvolume-1simple

Section 4.7: Manipulation of Power Series

Exercise 9. [11] Find the values of $T_{mn}$ computed by Algorithm T as it determines the first five coefficients in the reversion of $z = t - t^2$.

Verified: yes
Solve time: 2m10s

Solution

For the reversion of

$z = t - t^2,$

Algorithm T is applied to the general form

$U_1 z + U_2 z^2 + \cdots = t + V_2 t^2 + V_3 t^3 + \cdots,$

so here

$U_1 = 1,\quad U_n = 0 \ (n \ge 2), \qquad V_2 = -1,\quad V_n = 0 \ (n \ne 2).$

The quantities $T_{mn}$ are defined by Algorithm T through the expansion property (16),

$t^m = \sum_{n=m}^{\infty} T_{mn} z^n,$

so $T_{mn}$ is the coefficient of $z^n$ in $t^m$ after reversion.

From the known reversion,

$t = z + z^2 + 2z^3 + 5z^4 + 14z^5 + \cdots,$

we write

$t = \sum_{n \ge 1} a_n z^n,\quad a_1=1,\ a_2=1,\ a_3=2,\ a_4=5,\ a_5=14.$

Then $T_{mn}$ is the coefficient of $z^n$ in $t^m$, hence the $m$-fold convolution of the sequence $(a_n)$.

Case $m=1$

$T_{1n} = a_n,$

so

$T_{11}=1,\quad T_{12}=1,\quad T_{13}=2,\quad T_{14}=5,\quad T_{15}=14.$

Case $m=2$

$T_{2n} = \sum_{i+j=n} a_i a_j.$

For $n=2$:

$T_{22} = a_1 a_1 = 1.$

For $n=3$:

$T_{23} = a_1 a_2 + a_2 a_1 = 2.$

For $n=4$:

$T_{24} = a_1 a_3 + a_2 a_2 + a_3 a_1 = 2 + 1 + 2 = 5.$

For $n=5$:

$T_{25} = a_1 a_4 + a_2 a_3 + a_3 a_2 + a_4 a_1 = 5 + 2 + 2 + 5 = 14.$

Case $m=3$

$T_{3n} = \sum_{i+j+k=n} a_i a_j a_k.$

For $n=3$:

$T_{33} = a_1 a_1 a_1 = 1.$

For $n=4$, compositions of $4$ into $3$ positive parts are permutations of $(1,1,2)$:

$T_{34} = 3 \cdot a_1 a_1 a_2 = 3 \cdot 1 = 3.$

For $n=5$, compositions of $5$ into $3$ positive parts are $(1,1,3)$ and $(1,2,2)$:

For $(1,1,3)$ there are $3$ permutations:

$3 \cdot a_1 a_1 a_3 = 3 \cdot 2 = 6.$

For $(1,2,2)$ there are $3$ permutations:

$3 \cdot a_1 a_2 a_2 = 3 \cdot 1 = 3.$

Hence

$T_{35} = 6 + 3 = 9.$

Case $m=4$

$T_{4n} = \sum_{i+j+k+\ell=n} a_i a_j a_k a_\ell.$

For $n=4$:

$T_{44} = a_1^4 = 1.$

For $n=5$, the only composition into four positive parts is a permutation of $(1,1,1,2)$, with $4$ permutations:

$T_{45} = 4 \cdot a_1^3 a_2 = 4 \cdot 1 = 4.$

Case $m=5$

For $n=5$, only $(1,1,1,1,1)$ contributes:

$T_{55} = a_1^5 = 1.$

Values of $T_{mn}$ for $1 \le m,n \le 5$

The computed triangular array is

$$ \begin{array}{c|ccccc} T_{mn} & n=1 & 2 & 3 & 4 & 5 \ \hline m=1 & 1 & 1 & 2 & 5 & 14 \ m=2 & 0 & 1 & 2 & 5 & 14 \ m=3 & 0 & 0 & 1 & 3 & 9 \ m=4 & 0 & 0 & 0 & 1 & 4 \ m=5 & 0 & 0 & 0 & 0 & 1 \ \end{array} $$

This completes the determination of all values $T_{mn}$ produced by Algorithm T for the first five coefficients of the reversion of $z = t - t^2$.

∎