# On extensions of the Newton-Raphson iterative scheme to arbitrary orders

Gilbert Labelle†

LaCIM et Département de mathématiques, Université du Québec à Montréal (UQAM) case postale 8888, succursale Centre-Ville, Montréal (Québec) Canada H3C 3P8

**Abstract.** The classical quadratically convergent Newton-Raphson iterative scheme for successive approximations of a root of an equation $f(t) = 0$ has been extended in various ways by different authors, going from cubical convergence to convergence of arbitrary orders. We introduce two such extensions, using appropriate differential operators as well as combinatorial arguments. We conclude with some applications including special series expansions for functions of the root and enumeration of classes of tree-like structures according to their number of leaves.

**Résumé.** Le schéma itératif classique à convergence quadratique de Newton-Raphson pour engendrer des approximations successives d'une racine d'une équation $f(t) = 0$ a été étendu de plusieurs façons par divers auteurs, allant de la convergence cubique à des convergences d'ordres arbitraires. Nous introduisons deux telles extensions en utilisant des opérateurs différentiels appropriés ainsi que des arguments combinatoires. Nous terminons avec quelques applications incluant des développements en séries exprimant des fonctions de la racine et l'énumération de classes de structures arborescentes selon leur nombre de feuilles.

**Keywords:** Newton-Raphson iteration, order of convergence, combinatorial species, tree-like structures

## 1 Introduction

Let $(t_n)_{n \ge 0}$ be a sequence of real numbers converging to $a$. The convergence is said to be of order $p$ if

$$t_{n+1} - a = O((t_n - a)^p), \text{ as } n \to \infty. \quad (1)$$

This means that the convergence is very rapid, when $p \ge 2$, since the number of correct decimal digits in the approximation of $a$ is essentially multiplied by $p$ at each step. Now, let $U \subseteq \mathbb{R}$ be an open set and $f: U \to \mathbb{R}$ be twice differentiable. If the equation $f(t) = 0$ has a simple root $a \in U$, then the classical Newton-Raphson iterative scheme$^{(i)}$,

$$t_{n+1} = \mathcal{N}(t_n), \quad n = 0, 1, 2, \dots, \quad \text{with } \mathcal{N}(t) = t - \frac{f(t)}{f'(t)}, \quad (2)$$

<footnote>†With the support of NSERC (Canada)</footnote>

<footnote>(i) Also called the tangent method</footnote>
produces a quadratically convergent ($p = 2$) sequence of approximations $t_n \to a$, as $n \to \infty$, whenever the first approximation, $t_0$, is sufficiently near to $a$. For suitably regular functions, cubical convergence ($p = 3$), can be achieved using Householder's method (see Householder (1970)),

$$ \mathcal{N}(t) = t - \frac{f(t)}{f'(t)} \left( 1 + \frac{f(t)f''(t)}{2f'(t)^2} \right), \qquad (3) $$

or the method of the astronomer Halley (1656-1743),

$$ \mathcal{N}(t) = t - \frac{2f(t)f'(t)}{2f'(t)^2 - f(t)f''(t)}. \qquad (4) $$

More generally, to achieve convergence of order $k + 1$, $k \ge 3$, one can use the general Householder's method (see Householder (1970)),

$$ \mathcal{N}(t) = t + k \frac{(1/f)^{(k-1)}(t)}{(1/f)^{(k)}(t)}. \qquad (5) $$

Another way to achieve arbitrary order convergence is to make use of the method of indeterminate coefficients together with a Taylor expansion around the root (see Sebah and Gourdon (2001)). In Section 2, we use the inverse function theorem and differential operators to replace (5) by two explicit finite sums which also provide arbitrary order convergence. Section 3 is devoted to a combinatorial approach to these finite sums. We conclude, in Section 4, with some applications including special series expansions for functions of the root and enumeration of classes of tree-like structures according to their number of leaves.

## 2 Differential operators and higher order convergence

Assume that $f$ is of class $C^{k+1}$ around the simple root $a$. Then, by the inverse function theorem, there exists an open interval $V$ containing the root $a$ which is mapped bijectively by $f$ onto an open interval $W$ containing $0$. Moreover, the inverse function $f^{-1}> : W \to V$ is also of class $C^{k+1}$. Using these facts, we can express the root $a$ in the following way,

$$ a = f^{-1>}(0) = f^{-1>}(f(t) - f(t)) = f^{-1>}(f(t) + u)|_{u:=-f(t)}, \qquad (6) $$

whenever $t$ is sufficiently near of $a$. Now, fix such a $t$ and consider the function

$$ \Phi_t(u) = f^{-1>}(f(t) + u). \qquad (7) $$

Then, by Taylor's expansion with remainder, we have, for every small value of $u$,

$$ \Phi_t(u) = \sum_{\nu=0}^{k} \Phi_t^{(\nu)}(0) \frac{u^k}{k!} + \Phi_t^{(k+1)}(\theta u) \frac{u^{k+1}}{(k+1)!}, \quad 0 \le \theta \le 1. \qquad (8) $$

The Taylor's coefficients can be computed very easily in terms of $f$ as follows:
**Lemma 2.1** Let $D = d/dt$, then for $\nu \le k + 1$,

$$ \Phi_t^{(\nu)}(0) = \left(\frac{1}{f'(t)}D\right)^{\nu} t. \qquad (9) $$

**Proof:** Of course, $\Phi_t^{(\nu)}(0) = (f^{-1})^{(\nu)}(f(t))$. Applying the operator $D$ on both sides, we get by the chain-rule,

$$ D\Phi_t^{(\nu)}(0) = D(f^{-1})^{(\nu)}(f(t)) = (f^{-1})^{(\nu+1)}(f(t))f'(t) = f'(t)\Phi_t^{(\nu+1)}(0). \qquad (10) $$

Hence, $\Phi_t^{(\nu+1)}(0) = (\frac{1}{f'(t)}D)\Phi_t^{(\nu)}(0)$ and we conclude using the fact that, for $\nu = 0$, $\Phi_t(0) = (f^{-1})^{(\nu)}(f(t)) = t$. $\square$

Since $a = \Phi_t(u)|_{u=-f(t)}$ and $f(t)^{k+1} \sim f'(a)^{k+1} \cdot (t-a)^{k+1}$, as $t \to a$, we finally obtain,

**Proposition 2.2** Let $f$ be of class $C^{k+1}$ around the simple root $a$ and let

$$ \mathcal{N}(t) = \sum_{\nu=0}^{k} (-1)^{\nu} \frac{f(t)^{\nu}}{\nu!} \left(\frac{1}{f'(t)}D\right)^{\nu} t. \qquad (11) $$

Then $\mathcal{N}(t) - a = O((t - a)^{k+1})$ and, for every $t_0$ sufficiently near to $a$, the sequence $(t_n)_{n \ge 0}$, defined by $t_{n+1} = \mathcal{N}(t_n)$, converges to $a$ to the order $k + 1$. More precisely,

$$ t_{n+1} - a \sim C \cdot (t_n - a)^{k+1}, \quad n \to \infty, \qquad (12) $$

where

$$ C = (-1)^{k+1} \left[ \frac{f'(t)^{k+1}}{(k+1)!} \left( \frac{1}{f'(t)} D \right)^{k+1} t \right]_{t=a} . \qquad (13) $$

Note that for $k = 1$ (resp. $k = 2$), (11) corresponds to the Newton-Raphson (resp. Householder) iterative step. However, for $k \ge 3$, (11) and the general Householder's iterative step (5) are completely different. For example, for $k = 3$, (5) is given by

$$ \mathcal{N}(t) = t - f(t) \left( \frac{f'(t)^2 - f(t)f''(t)/2}{f'(t)^3 - f(t)f'(t)f''(t) + f'''(t)f(t)^2/6} \right), \qquad (14) $$

while (11) has the form

$$ \mathcal{N}(t) = t - \frac{f(t)}{f'(t)} \left( 1 + \frac{f(t)f''(t)}{2!f'(t)^2} + \frac{f(t)^2(3f''(t)^2 - f'(t)f'''(t))}{3!f'(t)^4} \right). \qquad (15) $$

The iteration step (11) can also be written the following equivalent way,

$$ \mathcal{N}(t) = \sum_{\nu=0}^{k} (-1)^{\nu} \left( \frac{\frac{f(t)}{f'(t)}D}{\nu} \right)^{\nu} t, \qquad (16) $$
where the binomial coefficient is interpreted as the polynomial $\binom{z}{\nu} = \frac{z(z-1)(z-2)\cdots(z-\nu+1)}{\nu!}$. This can be seen as follows : let

$$ \theta_{\nu}(t) = (-1)^{\nu} \frac{f(t)^{\nu}}{\nu!} \left( \frac{1}{f'(t)} D \right)^{\nu} t, \qquad (17) $$

and apply the operator $\frac{1}{f'(t)}D$ on both sides of the equality,

$$ \nu!(-f(t))^{-\nu}\theta_{\nu}(t) = \left(\frac{1}{f'(t)}D\right)^{\nu}t. \qquad (18) $$

Multiplying both sides of the resulting equality by $(-f(t))^{\nu+1}$, one gets after some computation,

$$ \theta_{\nu+1}(t) = -\frac{1}{\nu+1} \left( \frac{f(t)}{f'(t)} D - \nu \right) \theta_{\nu}(t), \qquad (19) $$

from which (16) follows immediately.

**Corollary 2.3** Let $f$ be analytic around the simple root $a$. Then, for every $g$, analytic around $a$, the following identities hold,

$$ g(a) = \sum_{\nu=0}^{\infty} (-1)^{\nu} \frac{f(t)^{\nu}}{\nu!} \left( \frac{1}{f'(t)} D \right)^{\nu} g(t) \qquad (20) $$

$$ = \sum_{\nu=0}^{\infty} (-1)^{\nu} \left( \frac{f(t)}{f'(t)} \right)^{\nu} D g(t), \qquad (21) $$

whenever $t$ belongs to a suitably small neighborhood of $a$.

**Proof:** (Sketch) Use the analytical version of the inverse function theorem, apply Taylor expansion to the function $\Psi_t(u) = g \circ f^{-1}(f(t) + u)$, in ascending powers of $u$, and use the fact that $g(a) = \Psi_t(u)|_{u=-f(t)}$ for every $t$ sufficiently near to $a$. $\square$

It is interesting to note that the function defined by the right members of (20-21) is a constant function in a neighborhood of $a$. Examples of this phenomenon and of Proposition 2.2 will be given in Section 4.

## 3 A combinatorial approach

Recall that a combinatorial species in the sense of Joyal is essentially a class of combinatorial structures which is closed under arbitrary relabellings of their underlying sets (ii). Given a combinatorial species, $R$, the species, $A = A(X)$, of $R$-enriched rooted trees is recursively defined by the combinatorial equation,

$$ A = XR(A), \qquad (22) $$

where $X$ denotes the species of singletons. Figure 1 describes an $A$-structure, where the black dots denote $X$-singletons and each circular arc, centered at a black dot, denotes an $R$-structure put on the (possibly empty) set of its children.

<footnote>(ii) Technically speaking, a species is an endofunctor of the category of finite sets with bijections. See Joyal (1981) and Bergeron et al. (1998)</footnote>
Fig. 1: An R-enriched rooted tree

The species of R-enriched rooted trees was introduced by the author (see Labelle (1981)) in order to give a combinatorial proof of Lagrange inversion. Equivalently, considering X as a combinatorial parameter, the species, A = A(X), can be seen as the solution of the combinatorial equation

$$
F(T) = 0, \quad \text{where} \quad F(T) = T - XR(T). \tag{23}
$$

Later, Décoste, Labelle, and Leroux (see Décoste et al. (1982)) used R-enriched rooted trees to give a
combinatorial proof of the classical (order 2) Newton-Raphson iterative scheme (2). They also sketched a
combinatorial model for higher order iterations but their approach was non explicit and computationally
unsatisfactory. The purpose of the present section is to give a combinatorial proof of the general (arbitrary
order) Newton-Raphson iterative scheme (11) and of the full expansion (20).

Let $D = d/dT$ denote the usual combinatorial differentiation operator with respect to singletons of sort $T$. Since $-F(T) = XR(T) - T$ and $DF(T) = F'(T) = 1 - XR'(T)$, the analytical iterative scheme (11) suggests the following combinatorial iterative scheme, $T \mapsto \mathcal{N}(T)$, where

$$
\mathcal{N}(T) = \sum_{\nu=0}^{k} \frac{1}{\mathcal{G}_{\nu}} (XR(T) - T)^{\nu} \left( \frac{1}{1 - XR'(T)} D \right)^{\nu} T, \quad (24)
$$

and where $\mathcal{G}_\nu$ denotes the symmetric group of order $\nu$. In other words, the right-hand side of (24) should be a finite sum of quotient species under some actions of the symmetric groups $\mathcal{G}_\nu$, $\nu = 0, 1, \dots, k$, into which the successive approximations of $A$ should be substituted for $T$.

The first approximation $T_0$ should be of the form $T_0 = \alpha$, where $\alpha = A|_{\le m}$ denotes the species of $R$-enriched rooted trees restricted to small sets, say of cardinalities $\le m$, the value of $m$ being fixed. Following the terminology of Décoste et al. (1982), $\alpha$-structures will be called light $R$-enriched rooted trees. An $A$-structure which is not light is called heavy. Convergence of order $k+1$ is interpreted combinatorially as follows:

$$
\alpha = A|_{\le m} \Rightarrow \mathcal{N}(\alpha)|_{\le (k+1)(m+1)} = A|_{\le (k+1)(m+1)}. \quad (25)
$$

In other words, if $\alpha$ coincides with the species $A$ on sets of cardinality $\le m$ then $\mathcal{N}(\alpha)$ will coincide with the species $A$ on sets of cardinality $\le (k+1)(m+1)$. In order to make this statement more precise, we introduce the auxiliary concepts.

Given $m$, the species, $B = B(X)$, of *m-broccolis*, is defined by $B = XR(\alpha) - \alpha$. In other words, a *m-broccoli* is an heavy *A-structure* consisting of a root (of sort *X*) followed by an *R-assembly* of light *R-enriched rooted trees*, see Figure 2, where $m = 6$.

Using the terminology of Labelle (1985), the differential operator ,

$$
\mathcal{D} = \frac{1}{1 - XR'(T)} D, \tag{26}
$$
<figure><img src="image_1.png" /><figcaption>Fig. 2: A *m*-broccoli for *m* = 6</figcaption></figure>

can be called an *eclosion* operator. Since $1/(1 - XR'(T))$ is the species of lists of $XR'(T)$-structures, the eclosion operator $\mathcal{D}$ transforms any species $K = K(X, T)$ to another species $\mathcal{DK} = \mathcal{DK}(X, T)$ as shown in Figure 3, where the *T*-singletons are represented by black triangles.

<figure><img src="image_2.png" /><figcaption>Fig. 3: The eclosion operator $\mathcal{D}$ applied to a species $K$</figcaption></figure>

Now consider an *R*-enriched rooted tree $\tau$ on a set (of *X*-singletons) of cardinality $\le (k+1)(m+1)$. Let $\nu$ be the number of broccolis contained in $\tau$. Then $0 \le \nu \le k$, since each broccoli contains at least $m+1$ points. Number arbitrarily these broccolis from 1 to $\nu$ as in Figure 4 (where $m=6$, $\nu=3$).

Detach next the numbered broccolis and put them as a list $b_1, b_2, \dots, b_\nu$ as in Figure 5. This shows that for $0 \le \nu \le k$, the species $A^{[\nu]}$ of *R*-enriched rooted trees having exactly $\nu$ broccolis numbered 1 to $\nu$ coincides with the species

$$ \left[ (XR(T) - T)^\nu \left( \frac{1}{1 - XR'(T)} D \right)^\nu T \right]_{T:=\alpha} \qquad (27) $$

on sets of cardinality $\le (k+1)(m+1)$.

Finally, since the symmetric group $S_\nu$ acts faithfully on the $A^{[\nu]}$-structures by simply renumbering the broccolis, we can erase the numbering by considering the quotient species of $A^{[\nu]}/S_\nu$. Summarizing, we can state the following combinatorial version of the Newton-Raphson scheme of arbitrary orders.
<figure><img src="image_3.png" /><figcaption>Fig. 4: Numbering the broccolis</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 5: $[(XR(\alpha) - \alpha)^3 D^3 T]_{T:=\alpha}$-structure</figcaption></figure>
**Proposition 3.1** Let $m \ge 0$ be a fixed integer, $D = d/dT$, and consider a species $\alpha$ coinciding with the species $A = XR(A)$ of R-enriched rooted trees on sets up to cardinality $m$. Then, the species

$$ \mathcal{N}(\alpha) = \sum_{\nu=0}^{k} \frac{1}{\mathfrak{G}_{\nu}} (XR(\alpha) - \alpha)^{\nu} \left[ \left( \frac{1}{1 - XR'(T)} D \right)^{\nu} T \right]_{T:=\alpha}, \qquad (28) $$

coincides with the species $A$ on sets up to cardinality $(k+1)(m+1)$.

<figure><img src="image_5.png" /></figure>

The following combinatorial analogue of (20) also holds. The proof is similar and left to the reader.

**Corollary 3.2** Let $m \ge 0$ be a fixed integer, $D = d/dT$, and consider a species $\alpha$ coinciding with the species $A = XR(A)$ of R-enriched rooted trees on sets up to cardinality $m$. Then, for any species $G$ we have the following expansion

$$ G(A) = \sum_{\nu=0}^{\infty} \frac{1}{\mathfrak{G}_{\nu}} (XR(\alpha) - \alpha)^{\nu} \left[ \left( \frac{1}{1 - XR'(T)} D \right)^{\nu} G(T) \right]_{T:=\alpha}. \qquad (29) $$

<figure><img src="image_6.png" /></figure>

Note that since there is no $A$-structure on the empty set, we can take, in particular, $m = 0$ and $\alpha = 0$ (the empty species), in Corollary 3.2. In this case, broccolis are (R-enriched) leaves in expansion (29). Special instances of Proposition 3.1 and of Corollary 3.2 will be given in the next section.

# 4 Examples and applications

## 4.1 Analytical examples

The analytical iterative scheme (11) and the corresponding full expansions (20-21) can be illustrated in a variety of ways. We now give three typical such illustrations.

*   **Root extraction.** Let $0 \ne n \in \mathbb{Z}$, $0 < c \in \mathbb{R}$, and consider the equation $t^n - c = 0$, whose solution is $a = c^{1/n}$. Then, for $t$ near $c^{1/n}$, the $(k+1)^{th}$ order iteration step (11) takes the form,

$$ \mathcal{N}(t) = \sum_{\nu=0}^{k} (-1)^{\nu} \binom{1}{\nu} t \left(1 - \frac{c}{t^n}\right)^{\nu}. \qquad (30) $$

Of course, when $k = 1$, this reduces to the classical $\mathcal{N}(t) = (t+c/t)/2$, if $n = 2$, and to $\mathcal{N}(t) = t(2-ct)$, if $n = -1$. It is worthwhile to note that, taking $g(t) = t^m$ and $t$ near $c^{1/n}$, (20) becomes

$$ c^{m/n} = \sum_{\nu=0}^{\infty} (-1)^{\nu} \binom{m}{\nu} t^{m} \left(1 - \frac{c}{t^{n}}\right)^{\nu}, \qquad (31) $$

in which the right-hand-side corresponds to the full expansion, in ascending powers of $(1 - c/t^n)$, of the trivial identity $c^{m/n} = t^m (1 - (1 - c/t^n))^{\frac{m}{n}}$.
• *Computing logarithms.* Let $0 < c \in \mathbb{R}$ and consider the equation $e^t - c = 0$, whose solution is $a = \ln(c)$. This time, for $t$ near $\ln(c)$, the $(k+1)^{\text{th}}$ order iteration step (11) takes the form,

$$ \mathcal{N}(t) = t - \sum_{\nu=1}^{k} \frac{(1 - c e^{-t})^{\nu}}{\nu}, \qquad (32) $$

and for any analytic function $g$ around $\ln(c)$, (20) becomes,

$$ g(\ln(c)) = \sum_{\nu=0}^{\infty} (c e^{-t} - 1)^{\nu} \binom{D}{\nu} g(t). \qquad (33) $$

In particular, if $g(t) = t$, this last equality corresponds to the full expansion, in ascending powers of $(1 - c e^{-t})$, of the trivial identity, $\ln(c) = t + \ln(1 - (1 - c e^{-t}))$.

• *Approximating* $\pi$. Consider the simple root $a = \pi$ of the equation $\sin(t) = 0$. It turns out that the form (16) of the iteration step is easier to manipulate in this case. Note first that $(f(t)/f'(t))D = \tan(t)D$. It is then easy to check by induction that, for $\nu > 0$,

$$ \binom{\tan(t)D}{\nu}t = \text{a polynomial function of } \tan(t) \text{ with constant coefficients.} \qquad (34) $$

Collecting alike powers of $\tan(t)$ in (16), massive cancellation produces the following $(2p + 1)^{\text{th}}$ order iterative scheme, $t_{n+1} = \mathcal{N}(t_n)$, for successive approximations of $\pi$, where,

$$ \mathcal{N}(t) = t - \tan(t) + \frac{\tan(t)^3}{3} - \frac{\tan(t)^5}{5} + \cdots + (-1)^{2p-1} \frac{\tan(t)^{2p-1}}{2p-1}, \qquad (35) $$

and $\frac{3}{4}\pi < t_0 < \frac{5}{4}\pi$ (one can take $t_0 = 3$, for example). Moreover, for analytic $g$ near $\pi$, (20) becomes,

$$ g(\pi) = \sum_{\nu=0}^{\infty} (-1)^{\nu} \binom{\tan(t)D}{\nu} g(t), \qquad (36) $$

whenever $t$ is sufficiently near to $\pi$. In particular, if $g(t) = t$, this last equality corresponds to the full expansion, in ascending powers of $\tan(t)$, of the trivial identity, $\pi = t - \arctan(\tan(t))$, $\frac{3}{4}\pi < t \le \frac{5}{4}\pi$.

## 4.2 Combinatorial applications

It is well-known that the classical classes of rooted-trees are special instances of $R$-enriched rooted trees. For example, if $1, X, L, E, E_n, C$, respectively denote the species of *the empty set*, of *singletons*, of *lists*, of *sets*, of *n-sets*, of *oriented cycles*, then,

* the class of *ordinary* (Cayley) rooted trees corresponds to the species $R = E$,

* the class of *topological* rooted trees corresponds to the species $R = E - X$,

* the class of *binary* rooted trees corresponds to the species $R = 1 + X^2$,

* the class of *unary-binary* rooted trees corresponds to the species $R = 1 + X + X^2$,

* the class of *unoriented binary* rooted trees corresponds to the species $R = 1 + E_2$,
* the class of unoriented unary-binary rooted trees corresponds to the species $R = 1 + X + E_2$,

* the class of ordered rooted trees corresponds to the species $R = L$,

* the class of mobiles (see Bergeron et al. (1998)) corresponds to the species $R = 1 + C$,

etc.

For each choice of the species $R$, the iteration step (28) produces a combinatorial computational scheme of order $k + 1$ for successive approximations of the species $A = XR(A)$ of $R$-enriched rooted trees. For example, taking $R = 1 + X + E_2$, then, $R'(X) = 1 + X$, and (28) becomes,

$$ \mathcal{N}(\alpha) = \sum_{\nu=0}^{k} \frac{1}{\mathfrak{G}_{\nu}} (X(1+\alpha + E_2(\alpha)) - \alpha)^{\nu} \left[ \left( \frac{1}{1-X(1+T)} D \right)^{\nu} T \right]_{T:=\alpha}, \quad (37) $$

where $D = d/dT$ and $\alpha$ is the species of light A-structures, namely, the class of unoriented unary-binary rooted trees that are living on sets of cardinality $\le m$. Moreover, for arbitrary $R$, taking $m = 0$ and $\alpha = 0$ in (29), the 0-broccolis become $XR(0)$-structures (enriched singletons) and we get the following two new full expansions involving the species $A$ of $R$-enriched rooted trees according to their number $\nu$ of leaves:

$$ A = \sum_{\nu=0}^{\infty} \frac{1}{\mathfrak{G}_{\nu}} X^{\nu} \left[ \left( \frac{R(0)}{1-XR'(T)} D \right)^{\nu} T \right]_{T:=0}, \quad (38) $$

$$ G(A) = \sum_{\nu=0}^{\infty} \frac{1}{\mathfrak{G}_{\nu}} X^{\nu} \left[ \left( \frac{R(0)}{1-XR'(T)} D \right)^{\nu} G(T) \right]_{T:=0}. \quad (39) $$

For example, taking $R = E$, the species or ordinary (Cayley) rooted trees can be written in the form

$$ A = \sum_{\nu=0}^{\infty} \frac{1}{\mathfrak{G}_{\nu}} X^{\nu} \left[ \left( \frac{1}{1-XE(T)} D \right)^{\nu} T \right]_{T:=0}, \quad (40) $$

and taking, for $G$, the species of permutations, $S$, the species of endofunctions, $End = S(A)$, can be written in the form

$$ \mathrm{End} = \sum_{\nu=0}^{\infty} \frac{1}{\mathfrak{G}_{\nu}} X^{\nu} \left[ \left( \frac{1}{1-XE(T)} D \right)^{\nu} S(T) \right]_{T:=0}. \quad (41) $$

We have the following result concerning the enumeration of $G(A)$-structures according to their number of leaves ($= 0$-broccolis).

**Corollary 4.1** Let $R(x) = \sum_{n=0}^{\infty} r_n x^n / n!$ and $G(x) = \sum_{n=0}^{\infty} g_n x^n / n!$ be the exponential generating series of the species $R$ and $G$. Let $\gamma_{n,\nu}$ be the number of $G$-assemblies of $R$-enriched rooted trees on $[n]$ having exactly $\nu$ leaves. Then, for $\nu \ge 1$,

$$ \sum_{n=0}^{\infty} \gamma_{n,\nu} x^n / n! = \frac{r_0^{\nu} x^{\nu}}{\nu!(1-r_1 x)^{2\nu-1}} p_{\nu}(x), \quad (42) $$
where $p_{\nu}(x) = \omega_{\nu}(x, 0)$ is a polynomial, with $\omega_{1}(x, t) = G'(t)$, and for $\nu > 1$,

$$ \omega_{\nu}(x, t) = \left( (1 - xR'(t)) \frac{\partial}{\partial t} + (2\nu - 3)xR''(t) \right) \omega_{\nu-1}(x, t). \quad (43) $$

**Proof:** Take the underlying power series of (39), and use induction on $\nu$. $\square$

<figure><img src="image_7.png" /></figure>

This provides a uniform algorithm for the computation of the sequences $(\gamma_{n,\nu})_{n \ge 0}$ which is easily implementable in computer algebra systems. If $r_0$ and $r_1$ are formal variables, they can be interpreted as "leafs" and "nodes having one child" counters, respectively. Moreover, since (42) is always a rational function of $x$, exact and asymptotic expressions for $\gamma_{n,\nu}$ are easily obtained using partial fractions expansions. For special choices of $R$ and $G$, recurrence (43) can often be simplified, as the following examples show.

• **Counting ordinary rooted trees having $\nu$ leaves.** Taking $R = E$ and $G = X$, one finds that $\omega_{\nu}(x, t) = p_{\nu}(xe^{t})$. Consequently, the exponential generating series of the species of ordinary rooted trees having exactly $\nu$ leaves is given by the rational function, $x^{\nu}(1-x)^{-2\nu+1}p_{\nu}(x)/\nu!$, where,

$$ p_1(x) = 1, \quad p_{\nu}(x) = x \left( (1-x)p'_{\nu-1}(x) + (2\nu-3)p_{\nu-1}(x) \right), \quad \nu > 1. \quad (44) $$

For small values of $\nu$, the resulting sequences $(\gamma_{n,\nu})_{n \ge 0}$ can be found in Sloane (2009).

• **Counting mobiles having $\nu$ leaves.** Taking $R = 1 + C$ and $G = X$, one finds that $\omega_{\nu}(x, t) = Q_{\nu}(x, t)/(1-t)^{2(\nu-1)}$, where $Q_{\nu}(x, t)$ is a polynomial in $x$ and $t$. Consequently, the exponential generating series of the species of mobiles having exactly $\nu$ leaves is given by the rational function, $x^{\nu}(1-x)^{-2\nu+1}q_{\nu}(x)/\nu!$, where, $q_{\nu}(x) = Q_{\nu}(x, 0)$, $Q_{1}(x, t) = 1$, and for $\nu > 1$,

$$ Q_{\nu}(x, t) = \left( (1-t)(1-t-x) \frac{\partial}{\partial t} + x + (2\nu-4)(1-t) \right) Q_{\nu-1}(x, t). \quad (45) $$

Again, for small values of $\nu$, the resulting sequences $(\gamma_{n,\nu})_{n \ge 0}$ can be found in Sloane (2009).

• **Counting topological rooted trees having $\nu$ leaves.** Taking $R = E - X$ and $G = X$, one finds that $\omega_{\nu}(x, t) = P_{\nu}(x, xe^{t})$, where $P_{\nu}(x, y)$ is a polynomial in $x$ and $y$. Since, in this case, $r_1 = 0$, the exponential generating series of the species of topological rooted trees having exactly $\nu$ leaves is a polynomial function of the form, $x^{\nu}p_{\nu}(x)/\nu!$, where, $p_{\nu}(x) = P_{\nu}(x, x)$, $P_1(x, y) = 1$, and for $\nu > 1$,

$$ P_{\nu}(x, y) = \left( (1 + x - y)y \frac{\partial}{\partial y} + (2\nu - 3)y \right) P_{\nu-1}(x, y). \quad (46) $$

• **Counting endofunctions according to their number of leaves.** As mentioned before, taking $R = E$ and $G = S$, the species $G(A) = S(A)$ coincides with the species, End, of endofunctions. In this case, being a leaf of an endofunction $\phi$ is the same as being a leaf of a rooted tree in the $S$-assembly of rooted trees corresponding to $\phi$. Equivalently, a leaf of an endofunction $\phi$ is a periodic element having a 1-element fiber or an element having an empty fiber. In this case, it turns out that $\omega_{\nu}(x, t) = K_{\nu}(xe^{t}, t)/(1-t)^{\nu+1}$,
where $K_ν(x, t)$ is a polynomial in $x$ and $t$. The corresponding exponential generating series of the species of endofunctions having exactly $ν$ leaves is given by the rational function, $x^ν(1-x)^{-2ν+1}ε_ν(x)/ν!$, where, $ε_ν(x) = K_ν(x, 0)$, $K_1(x, t) = 1$, and for $ν > 1$,

$$K_ν(x, t) = \left( (1-x)(1-t) \left( x \frac{\partial}{\partial x} + \frac{\partial}{\partial t} \right) + \nu + (\nu-3)x - (2\nu-3)xt \right) K_{\nu-1}(x, t). \quad (47)$$

## Acknowledgements

The author would like to thank Jérôme Tremblay who programmed all the figures directly within the LATEX language and for his general technical help during the preparation of this document.

## References

F. Bergeron, G. Labelle, and P. Leroux. *Combinatorial Species and Tree-Like Structures*. Cambridge University Press, 1998.

H. Décoste, G. Labelle, and P. Leroux. Une approche combinatoire pour l'itération de Newton-Raphson. *Advances in Applied Mathematics*, 3:407-416, 1982.

A. S. Householder. *The Numerical Treatment of a Single Nonlinear Equation*. McGraw-Hill, New-York, 1970.

A. Joyal. Une théorie combinatoire des séries formelles. *Advances in Mathematics*, 42:1-82, 1981.

G. Labelle. Une nouvelle démonstration combinatoire des formules d'inversion de Lagrange. *Advances in Mathematics*, 42:217-247, 1981.

G. Labelle. Eclosions combinatoires appliquées à l'inversion multidimensionnelle des séries formelles. *Journal of Combinatorial Theory, Series A*, 39:52-82, 1985.

P. Sebah and X. Gourdon. Newton's method and high order iterations, 2001. URL http://numbers.computation.free.fr/Constants/constants.html.

N. Sloane. The On-Line Encyclopedia of Integer Sequences, 2009. URL http://www.research.att.com/~njas/sequences.