De Moivre and Bell polynomials

Cormac O’Sullivan¹¹1Date: Mar 5, 2022.
   2010 Mathematics Subject Classification: 05A15, 05A16, 13F25.
   Support for this project was provided by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City
   University of New York.

Abstract

We survey a family of polynomials that are very useful in all kinds of power series manipulations, and appearing more frequently in the literature. Applications to formal power series, generating functions and asymptotic expansions are described, and we discuss the related work of De Moivre, Arbogast and Bell.

1 Introduction

Let $a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$ be a formal power series without a constant term and with coefficients in ${\mathbb{C}}$ . It could represent a function in some neighborhood of $x=0$ , but usually we don’t require convergence. The $k$ th power of this series may be expanded into another series

\mathopen{}\mathclose{{}\left(a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots}\right)^{k}=\sum_{n\in{\mathbb{Z}}}{\mathcal{A}}_{n,k}(a_{1},a_{2},a_{3},\dots)x^{n}\qquad\quad(k\in{\mathbb{Z}}_{\geqslant 0}),

(1.1)

and it can be seen that the new coefficients ${\mathcal{A}}_{n,k}(a_{1},a_{2},a_{3},\dots)$ can only be nonzero if $n\geqslant k$ , in which case they depend at most on $a_{1},a_{2},\dots,a_{m}$ for $m=n-k+1$ . The multinomial development

\mathopen{}\mathclose{{}\left(a_{1}x+a_{2}x^{2}+\cdots+a_{m}x^{m}}\right)^{k}=\sum_{j_{1}+j_{2}+\dots+j_{m}=k}\binom{k}{j_{1},j_{2},\dots,j_{m}}(a_{1}x)^{j_{1}}(a_{2}x^{2})^{j_{2}}\cdots(a_{m}x^{m})^{j_{m}}

shows that

{\mathcal{A}}_{n,k}(a_{1},a_{2},a_{3},\dots)=\sum_{\begin{subarray}{c}1j_{1}+2j_{2}+\dots+mj_{m}=n\\ j_{1}+j_{2}+\dots+j_{m}=k\end{subarray}}\binom{k}{j_{1},j_{2},\dots,j_{m}}a_{1}^{j_{1}}a_{2}^{j_{2}}\cdots a_{m}^{j_{m}}

(1.2)

where the sum is over all possible $j_{1}$ , $j_{2}$ , …, $j_{m}\in{\mathbb{Z}}_{\geqslant 0}$ and $0^{0}=1$ throughout.

Thus ${\mathcal{A}}_{n,k}$ is a simply described polynomial in $a_{1},a_{2},\dots,a_{n-k+1}$ . In the literature they are designated ‘partial ordinary Bell polynomials’, and related to the better-known partial Bell polynomials ${\mathcal{B}}_{n,k}$ . We will make the case that in fact the ${\mathcal{A}}_{n,k}$ polynomials are the more natural and useful version. Prior to Bell, Arbogast [Arb00] was already working with them in 1800. However, their earliest appearance seems to be in a 1697 paper of De Moivre [DM97]. There he says he was curious to see if he could generalize to (1.1) his friend Mr. Newton’s work with binomials. His solution is equivalent to (1.2), though uses an interesting recurrence to describe which products $a_{1}^{j_{1}}a_{2}^{j_{2}}\cdots a_{m}^{j_{m}}$ appear. This is discussed in section 6. See also [Sch68, Sect. 5.1] for historical context. We propose a new, more succinct name for these fundamental objects:

Definition 1.1.

For $n$ , $k\in{\mathbb{Z}}$ with $k\geqslant 0$ , define the De Moivre polynomial ${\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)$ by (1.1). If $n<k$ it is $0$ . If $n\geqslant k$ it is given by (1.2), making a polynomial in $a_{1},a_{2},\dots,a_{n-k+1}$ of homogeneous degree $k$ with positive integer coefficients and number of terms equalling the number of partitions of $n$ with $k$ parts; see (6.1).

In this article we aim to provide a convenient reference for these polynomials, while also describing some new results about them. The author has found them to be of great use in giving explicit forms for asymptotic expansions, and we will see examples of this in section 7. More generally, as shown in section 3, composing, inverting and taking powers of generating functions and power series becomes easy with the help of the De Moivre polynomials, giving clear expressions for the new coefficients. We find in section 6 that some familiar generating functions take on a new look with this treatment. Many applications are discussed; we may also mention [Pit06, Chap. 1], [Cha02, Chap. 11], for example, for further uses of De Moivre\Bell polynomials in probability and statistics and for relations among symmetric polynomials.

Before reviewing the basic properties of ${\mathcal{A}}_{n,k}$ in the next section, we complete this introduction by including more of the history of these ideas. Replacing the ordinary series in (1.1) with an exponential series, (in other words a Taylor series), defines the partial Bell polynomials:

\frac{1}{k!}\mathopen{}\mathclose{{}\left(a_{1}\frac{x}{1!}+a_{2}\frac{x^{2}}{2!}+a_{3}\frac{x^{3}}{3!}+\cdots}\right)^{k}=\sum_{n=0}^{\infty}{\mathcal{B}}_{n,k}(a_{1},a_{2},a_{3},\dots)\frac{x^{n}}{n!}\qquad\quad(k\in{\mathbb{Z}}_{\geqslant 0}).

(1.3)

(We are following Comtet’s terminology from [Com74, Chap. 3].) Hence we have the relation

{\mathcal{B}}_{n,k}(a_{1},a_{2},a_{3},\dots)=\frac{n!}{k!}{\mathcal{A}}_{n,k}(\frac{a_{1}}{1!},\frac{a_{2}}{2!},\frac{a_{3}}{3!},\dots).

(1.4)

The complete Bell polynomials are defined as

{\mathcal{Y}}_{n}(a_{1},a_{2},a_{3},\dots):=\sum_{k=0}^{n}{\mathcal{B}}_{n,k}(a_{1},a_{2},a_{3},\dots).

There is also a related Bell polynomial in one variable:

{\mathcal{B}}_{n}(x):=n![t^{n}]e^{x(e^{t}-1)}=\sum_{k=0}^{n}{\mathcal{B}}_{n,k}(1,1,1,\dots)x^{k}

where $[t^{n}]$ indicates the coefficient of $t^{n}$ in a series.

Bell introduced the complete polynomials ${\mathcal{Y}}_{n}$ in [Bel34] as a wide generalization of the Hermite and Appell polynomials. They are also related to the partition polynomials he was previously considering - see [O’S, Thm. 6.6]. Riordan studied ${\mathcal{Y}}_{n}$ and ${\mathcal{B}}_{n,k}$ in [Rio68], naming them Bell polynomials. Comtet emphasized that what he termed the ‘partial ordinary’ version should be used when dealing with ordinary series like $a_{0}+a_{1}x+a_{2}x^{2}+\cdots$ , (he used the notation $\hat{{\mathcal{B}}}_{n,k}$ but we prefer ${\mathcal{A}}_{n,k}$ to clearly differentiate the versions). However, all the formulas in [Com74, Chap. 3] involve the polynomials ${\mathcal{B}}_{n,k}$ and this might account for their dominance in the literature.

Research into the origins of Faà di Bruno’s formula in [Knu97, pp. 52, 481 - 483] and [Cra05, Joh02b] uncovered the work of Arbogast in [Arb00] where the formula in fact first appeared. Arbogast takes powers of polynomials in his method and gives the formula (1.2) in [Arb00, pp. 43-44]. For example, in a table on p. 29 of [Arb00], the entry

6\beta^{5}\zeta+15\beta^{4}(2{\gamma}\varepsilon+\delta^{2})+60\beta^{3}{\gamma}^{2}\delta+15\beta^{2}{\gamma}^{4}

(1.5)

associated to $x^{10}$ and $D^{6}$ is provided. In our notation this is ${\mathcal{A}}_{10,6}(\beta,\gamma,\delta,\varepsilon,\zeta,\dots)$ , or more clearly,

{\mathcal{A}}_{10,6}(a_{1},a_{2},a_{3},\dots)=6a_{1}^{5}a_{5}+30a_{1}^{4}a_{2}a_{4}+15a_{1}^{4}a_{3}^{2}+60a_{1}^{3}a_{2}^{2}a_{3}+15a_{1}^{2}a_{2}^{4}.

(1.6)

We explain what he was doing after Theorem 3.3.

Abraham De Moivre (1667-1754), though perhaps best known today for a trigonometric formula, was an important pioneer in areas such as probability and statistics, roots of equations, analytic geometry and infinite series. Born in France, he moved to England with other Huguenots to escape persecution, and there became part of the circle that included Newton, Halley and Stirling. The biography [BG07] gives more details about his life, and the papers [Sch68, Cra05, Gél] describe aspects of his mathematics, some of which we will touch on.

2 Basic properties of ${\mathcal{A}}_{n,k}$

The results in this section follow from the generating function (1.1) as exercises. Some of these and their partial Bell polynomial analogs appear in [Rio68, pp. 188 – 192] and [Com74, Sec. 3.3]. The following equalities (2.1) – (2.12) are identities in the ring ${\mathbb{Z}}[a_{1},a_{2},\dots]$ .

For small $k$ ,

$\displaystyle{\mathcal{A}}_{n,0}(a_{1},a_{2},\dots)$	$\displaystyle=\delta_{n,0},$	(2.1)
$\displaystyle{\mathcal{A}}_{n,1}(a_{1},a_{2},\dots)$	$\displaystyle=a_{n}\qquad\qquad(n\geqslant 1),$	(2.2)
$\displaystyle{\mathcal{A}}_{n,2}(a_{1},a_{2},\dots)$	$\displaystyle=\sum_{j=1}^{n-1}a_{j}a_{n-j}.$	(2.3)

The identities (2.2), (2.3) generalize to give a symmetric formula for ${\mathcal{A}}_{n,k}$ :

{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)=\sum_{n_{1}+n_{2}+\dots+n_{k}=n}a_{n_{1}}a_{n_{2}}\cdots a_{n_{k}}\qquad\qquad(k\geqslant 1),

(2.4)

where the sum in (2.4) is over all possible $n_{1}$ , $n_{2},\dots,n_{k}\in{\mathbb{Z}}_{\geqslant 1}$ . The two main recursion relations for ${\mathcal{A}}_{n,k}$ in $n$ and $k$ are given by

	$\displaystyle{\mathcal{A}}_{n+k,k}(a_{1},a_{2},a_{3},\dots)$	$\displaystyle=\sum_{j=0}^{k}\binom{k}{j}a_{1}^{k-j}{\mathcal{A}}_{n,j}(a_{2},a_{3},\dots),$		(2.5)
	$\displaystyle{\mathcal{A}}_{n,k+1}(a_{1},a_{2},a_{3},\dots)$	$\displaystyle=\sum_{j=k}^{n-1}a_{n-j}{\mathcal{A}}_{j,k}(a_{1},a_{2},a_{3},\dots).$		(2.6)

In fact (2.6) is the $\ell=1$ case of the following identity:

\sum_{j=0}^{n}{\mathcal{A}}_{j,k}(a_{1},a_{2},\dots)\cdot{\mathcal{A}}_{n-j,\ell}(a_{1},a_{2},\dots)={\mathcal{A}}_{n,k+\ell}(a_{1},a_{2},\dots).

(2.7)

Note that (2.5) is useful to compute ${\mathcal{A}}_{n+k,k}$ if $n$ is small, since the terms in the sum can only be nonzero for $j\leqslant n$ . For example, when $k\geqslant 1$ we have

	$\displaystyle{\mathcal{A}}_{k,k}(a_{1},a_{2},\dots)=a_{1}^{k},$		(2.8)
	$\displaystyle{\mathcal{A}}_{k+1,k}(a_{1},a_{2},\dots)=ka_{1}^{k-1}a_{2},$		(2.9)
	$\displaystyle{\mathcal{A}}_{k+2,k}(a_{1},a_{2},\dots)=\binom{k}{1}a_{1}^{k-1}a_{3}+\binom{k}{2}a_{1}^{k-2}a_{2}^{2},$		(2.10)
	$\displaystyle{\mathcal{A}}_{k+3,k}(a_{1},a_{2},\dots)=\binom{k}{1}a_{1}^{k-1}a_{4}+2\binom{k}{2}a_{1}^{k-2}a_{2}a_{3}+\binom{k}{3}a_{1}^{k-3}a_{2}^{3},$		(2.11)
	$\displaystyle{\mathcal{A}}_{k+4,k}(a_{1},a_{1},\dots)=\binom{k}{1}a_{1}^{k-1}a_{5}+\binom{k}{2}a_{1}^{k-2}\mathopen{}\mathclose{{}\left(a_{3}^{2}+2a_{2}a_{4}}\right)+3\binom{k}{3}a_{1}^{k-3}a_{2}^{2}a_{3}+\binom{k}{4}a_{1}^{k-4}a_{2}^{4}.$		(2.12)

De Moivre continued this list as far as ${\mathcal{A}}_{k+6,k}$ in [DM97, Fig. 5].

For a variable $z$ , the general binomial coefficients satisfy $\binom{z}{0}:=1$ and for positive integers $k$ ,

\binom{z}{k}:=\frac{z(z-1)\cdots(z-k+1)}{k!},\qquad\binom{-z}{k}=(-1)^{k}\binom{z+k-1}{k}.

(2.13)

Lemma 2.1.

For $n\geqslant k\geqslant 0$ , we have the following identities in ${\mathbb{Q}}[z]$ :

$\displaystyle{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(1,1,1,\dots}\right)$	$\displaystyle=\binom{n-1}{n-k},$	(2.14)
$\displaystyle{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\binom{z}{0},\binom{z}{1},\binom{z}{2},\dots}\right)$	$\displaystyle=\binom{kz}{n-k},$	(2.15)
$\displaystyle{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\binom{z}{0},\binom{z+1}{1},\binom{z+2}{2},\dots}\right)$	$\displaystyle=\binom{n+kz-1}{n-k}.$	(2.16)

Proof.

The equality (2.15) follows from the binomial theorem. Then (2.15) implies (2.16), using the right identity in (2.13). Lastly, (2.14) is a special case of (2.16). ∎

The next relations are often useful:

$\displaystyle{\mathcal{A}}_{n,k}(0,a_{1},a_{2},a_{3},\dots)$	$\displaystyle={\mathcal{A}}_{n-k,k}(a_{1},a_{2},a_{3},\dots),$	(2.17)
$\displaystyle{\mathcal{A}}_{n,k}(ca_{1},ca_{2},ca_{3},\dots)$	$\displaystyle=c^{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},a_{3},\dots),$	(2.18)
$\displaystyle{\mathcal{A}}_{n,k}(ca_{1},c^{2}a_{2},c^{3}a_{3},\dots)$	$\displaystyle=c^{n}{\mathcal{A}}_{n,k}(a_{1},a_{2},a_{3},\dots).$	(2.19)

Equalities (2.14) and (2.18) easily give:

Lemma 2.2.

Suppose the $a_{j}$ are complex numbers satisfying $|a_{j}|\leqslant Q$ . Then for $n\geqslant k\geqslant 0$ ,

\mathopen{}\mathclose{{}\left|{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)}\right|\leqslant\binom{n-1}{n-k}Q^{k}\leqslant 2^{n}Q^{k}.

Some further special values of ${\mathcal{A}}_{n,k}$ are described next, related to the exponential function and the logarithm. We have

{\mathcal{A}}_{m+k,k}\mathopen{}\mathclose{{}\left(\frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\dots}\right)=\frac{k^{m}}{m!}\qquad(m,k\geqslant 0).

(2.20)

Also, for $n,k\geqslant 0$ ,

	$\displaystyle(e^{t}-1)^{k}$	$\displaystyle=\sum_{n=0}^{\infty}\frac{k!}{n!}{\genfrac{\{}{\}}{0.0pt}{}{n}{k}}t^{n}$		$\displaystyle\implies\qquad$	$\displaystyle{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{1}{1!},\frac{1}{2!},\frac{1}{3!},\dots}\right)$	$\displaystyle=\frac{k!}{n!}{\genfrac{\{}{\}}{0.0pt}{}{n}{k}},$		(2.21)
	$\displaystyle(-\log(1-t))^{k}$	$\displaystyle=\sum_{n=0}^{\infty}\frac{k!}{n!}{\genfrac{[}{]}{0.0pt}{}{n}{k}}t^{n}$		$\displaystyle\implies\qquad$	$\displaystyle{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{1}{1},\frac{1}{2},\frac{1}{3},\dots}\right)$	$\displaystyle=\frac{k!}{n!}{\genfrac{[}{]}{0.0pt}{}{n}{k}}.$		(2.22)

The left identities of (2.21) and (2.22), (see [GKP94, (7.49), (7.50)]), may be taken as the definitions of the Stirling numbers, as in [Com74, p. 51], and all their properties developed from this starting point. Alternatively, the Stirling subset numbers ${\genfrac{\{}{\}}{0.0pt}{}{n}{k}}$ count the number of ways to partition $n$ elements into $k$ nonempty subsets, and the Stirling cycle numbers ${\genfrac{[}{]}{0.0pt}{}{n}{k}}$ count the number of ways to arrange $n$ elements into $k$ cycles. More advanced special values of ${\mathcal{A}}_{n,k}$ are shown in [O’S, Sect. 9.3].

We notice that the De Moivre polynomials in (2.21) appear with arguments shifted from the ones in (2.20). This type of shifting will also be seen in examples in sections 6 and 7. In the simplest case, adding or removing the first coefficient $a_{1}$ in ${\mathcal{A}}_{n,k}$ has a simple effect, by the binomial theorem:

Lemma 2.3.

For $k\geqslant 0$ ,

	$\displaystyle{\mathcal{A}}_{n,k}(a_{2},a_{3},\dots)$	$\displaystyle=\sum_{j=0}^{k}(-a_{1})^{k-j}\binom{k}{j}{\mathcal{A}}_{n+j,j}(a_{1},a_{2},\dots),$		(2.23)
	$\displaystyle{\mathcal{A}}_{n,k}(a_{1},a_{1},\dots)$	$\displaystyle=\sum_{j=0}^{k}a_{1}^{k-j}\binom{k}{j}{\mathcal{A}}_{n-k,j}(a_{2},a_{3},\dots).$		(2.24)

(The identity (2.24) is just (2.5) again.) Then applying (2.23) and (2.24) $r$ times leads to the following.

Proposition 2.4.

For $r,k\geqslant 0$ , ${\mathcal{A}}_{n,k}(a_{r+1},a_{r+2},\dots)$ equals

\sum_{j_{1}+j_{2}+\dots+j_{r+1}=k}\binom{k}{j_{1},j_{2},\dots,j_{r+1}}(-a_{1})^{j_{1}}(-a_{2})^{j_{2}}\cdots(-a_{r})^{j_{r}}{\mathcal{A}}_{n+J+rj_{r+1},j_{r+1}}(a_{1},a_{2},\dots)

(2.25)

and ${\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)$ equals

\sum_{j_{1}+j_{2}+\dots+j_{r+1}=k}\binom{k}{j_{1},j_{2},\dots,j_{r+1}}a_{1}^{j_{1}}a_{2}^{j_{2}}\cdots a_{r}^{j_{r}}{\mathcal{A}}_{n+J-rk,j_{r+1}}(a_{r+1},a_{r+2},\dots)

(2.26)

where $J$ means $(r-1)j_{1}+(r-2)j_{2}+\cdots+1j_{r-1}$ and the summations are over all $j_{1}$ , …, $j_{r+1}\in{\mathbb{Z}}_{\geqslant 0}$ with sum $k$ .

For example, taking $r=n-k+1$ and setting $a_{r+1}=a_{r+2}=\cdots=0$ in (2.26) recovers (1.2) since the only nonzero terms have $n+J-rk=j_{r+1}=0$ by (2.1).

3 Manipulating power series

Our power series coefficients $a_{j}$ may come from a ring $R$ . Though more general cases can be considered, a natural choice for $R$ is an integral domain containing ${\mathbb{Z}}$ (and so of characteristic $0$ ). Throughout this section we assume $R$ has these properties and hence $R[[x]]$ , the ring of formal power series over $R$ , is also an integral domain containing ${\mathbb{Z}}$ . See [GJ83, Chap. 1], [Com74, Sect. 1.12] or [FS09, Sect. A5] for more on formal power series rings. An important point is that, at each step, a new coefficient must depend only on finitely many others, as if we were working with polynomials; see the notions of summable and admissible in [GJ83, Chap. 1]. This is why the inner series in Proposition 3.1 cannot have a constant term, for example.

3.1 Series composition

Proposition 3.1.

Suppose that $f(x)=a_{1}x+a_{2}x^{2}+\cdots$ and $g(x)=b_{0}+b_{1}x+b_{2}x^{2}+\cdots$ are two power series in $R[[x]]$ . Then $g(f(x))=c_{0}+c_{1}x+c_{2}x^{2}+\cdots$ is in $R[[x]]$ with

\quad c_{n}=\sum_{k=0}^{n}b_{k}\cdot{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots).

(3.1)

Proof.

We have

g(f(x))=\sum_{k=0}^{\infty}b_{k}\cdot f(x)^{k}=\sum_{k=0}^{\infty}b_{k}\sum_{n=k}^{\infty}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)x^{n},

and switching the order of summation gives (3.1). ∎

Though this result is for formal power series, it applies very widely. A commonly occurring situation has $f(x)$ and $g(x)$ holomorphic in neighborhoods of $0$ with $f(0)=0$ . Then $g(f(x)$ is also holomorphic in a neighborhood of $0$ and its Taylor coefficients may be computed using Proposition 3.1.

Three important cases are as follows. Suppose that the integral domain $R$ contains ${\mathbb{Q}}$ . Applying Proposition 3.1 with $g(x)=(1+x)^{\alpha}$ , $e^{\alpha x}$ and $\log(1+\alpha x)$ gives

$\displaystyle[x^{n}](1+f(x))^{\alpha}$	$\displaystyle=\sum_{k=0}^{n}\binom{\alpha}{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots),$	(3.2)
$\displaystyle[x^{n}]e^{\alpha f(x)}$	$\displaystyle=\sum_{k=0}^{n}\frac{\alpha^{k}}{k!}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots),$	(3.3)
$\displaystyle[x^{n}]\log(1+\alpha f(x))$	$\displaystyle=\sum_{k=1}^{n}(-1)^{k-1}\frac{\alpha^{k}}{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots).$	(3.4)

The polynomials in $a_{1},a_{2},\dots$ on the right sides of (3.2), (3.3) and (3.4) are essentially the potential, complete exponential and logarithmic polynomials, respectively, of [Com74, Sections 3.3, 3.5]. Recalling (2.13), the right sides of (3.2), (3.3) and (3.4) are also degree $n$ polynomials in $\alpha$ . Therefore the series $(1+f(x))^{\alpha}$ , $e^{\alpha f(x)}$ and $\log(1+\alpha f(x))$ make sense for arbitrary $\alpha$ , giving elements of $R[\alpha][[x]]$ . Further, if $f(x)$ is holomorphic in a neighborhood of $0$ , then so are the compositions $g(f(x))$ , with (3.2), (3.3), (3.4) (times $n!$ ) giving their Taylor coefficients.

For an example we will need later, consider

\log\mathopen{}\mathclose{{}\left(1+\frac{\log(1+x)}{u}}\right)=\sum_{n=1}^{\infty}\ell_{n}(u)x^{n},

(3.5)

and we would like to know how $\ell_{n}(u)$ depends on $u$ . Stepping through the proof of Proposition 3.1 shows

	$\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k\cdot u^{k}}\log^{k}(1+x)$	$\displaystyle=\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k\cdot u^{k}}\sum_{n=k}^{\infty}{\mathcal{A}}_{n,k}(1,-{\textstyle\frac{1}{2}},{\textstyle\frac{1}{3}},\dots)x^{n}$
		$\displaystyle=\sum_{n=1}^{\infty}x^{n}\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k\cdot u^{k}}{\mathcal{A}}_{n,k}(1,-{\textstyle\frac{1}{2}},{\textstyle\frac{1}{3}},\dots).$

It is already clear that $\ell_{n}(u)$ is a polynomial of degree $n$ in $1/u$ with no constant term. With (2.18), (2.19) and (2.22) we obtain the simplification

\ell_{n}(u)=(-1)^{n+1}\sum_{k=1}^{n}\frac{(k-1)!}{n!}{\genfrac{[}{]}{0.0pt}{}{n}{k}}u^{-k}.

(3.6)

A very common case that follows from (3.2) should be highlighted:

Proposition 3.2.

Let $R$ be an integral domain containing ${\mathbb{Z}}$ with $a_{0}+a_{1}x+a_{2}x^{2}+\cdots$ in $R[[x]]$ . Then for $m\in{\mathbb{Z}}$ ,

\mathopen{}\mathclose{{}\left(a_{0}+a_{1}x+a_{2}x^{2}+\cdots}\right)^{m}=\sum_{n=0}^{\infty}\mathopen{}\mathclose{{}\left[\sum_{k=0}^{n}\binom{m}{k}a_{0}^{m-k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)}\right]x^{n}

(3.7)

is in $R[[x]]$ , (provided $a_{0}$ is invertible in $R$ if $m<0$ ), and in particular, the multiplicative inverse of the series is given by

\mathopen{}\mathclose{{}\left(a_{0}+a_{1}x+a_{2}x^{2}+\cdots}\right)^{-1}=\sum_{n=0}^{\infty}\mathopen{}\mathclose{{}\left[\sum_{k=0}^{n}(-1)^{k}a_{0}^{-k-1}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)}\right]x^{n}.

(3.8)

3.2 Arbogast’s formula

See [Cra05] and [Joh02b] for the early history of the next famous result which is usually named for Faà di Bruno. It is essentially equivalent to Proposition 3.1.

Theorem 3.3 (Arbogast’s formula).

For $n$ times differentiable functions $f$ and $g$ ,

\frac{1}{n!}\frac{d^{n}}{dx^{n}}g(f(x))=\sum_{k=0}^{n}\frac{g^{(k)}(f(x))}{k!}\cdot{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{f^{\prime}(x)}{1!},\frac{f^{\prime\prime}(x)}{2!},\dots}\right).

(3.9)

Proof.

Use induction to establish that (3.9) must be true for some polynomial $P_{n,k}$ instead of ${\mathcal{A}}_{n,k}$ . To identify $P_{n,k}$ set $f(x)=a_{1}x+a_{2}x^{2}+\cdots$ , $g(x)=b_{0}+b_{1}x+b_{2}x^{2}+\cdots$ and $g(f(x))=c_{0}+c_{1}x+c_{2}x^{2}+\cdots$ . Then evaluating at $x=0$ finds

c_{n}=\sum_{k=0}^{n}b_{k}\cdot P_{n,k}\mathopen{}\mathclose{{}\left(a_{1},a_{2},\dots}\right).

Comparing this with (3.1) now shows that $P_{n,k}\equiv{\mathcal{A}}_{n,k}$ , since the coefficients $a_{i}$ and $b_{j}$ are arbitrary. ∎

Arbogast had a similar point of view in [Arb00]. He considered $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots$ and gave the formula

\frac{1}{n!}\mathopen{}\mathclose{{}\left.\frac{d^{n}}{dx^{n}}g(f(x))}\right|_{x=0}=\sum_{k=0}^{n}\frac{g^{(k)}(a_{0})}{k!}\cdot{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(a_{1},a_{2},\dots}\right),

(3.10)

computing (3.10) explicitly in tables for $1\leqslant n\leqslant 10$ . For example, see Figure 1 of [Cra05], reproduced from [Arb00, p. 29], where ${\mathcal{A}}_{10,k}(\beta,\gamma,\delta,\varepsilon,\zeta,\nu,\theta,\iota,\kappa,\lambda,\dots)$ is given correctly for $1\leqslant k\leqslant 10$ .

In the notation of Proposition 3.1, a further composition $h(g(f(x)))$ would require ${\mathcal{A}}_{n,r}(c_{0},c_{1},\dots)$ . Computing this using (3.1) looks hopelessly complicated, with De Moivre polynomials inside De Moivre polynomials, but in fact a slight extension of a lemma of Charalambides, [Cha02, Lemma 11.1], gives a simple formula.

Proposition 3.4.

With the assumptions of Proposition 3.1,

{\mathcal{A}}_{n+r,r}(c_{0},c_{1},\dots)=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)\cdot{\mathcal{A}}_{k+r,r}(b_{0},b_{1},\dots).

(3.11)

Proof.

Write $y=f(x)$ so that

(y\cdot g(y))^{r}=\sum_{k=r}^{\infty}{\mathcal{A}}_{k,r}(b_{0},b_{1},\dots)y^{k},

and hence

	$\displaystyle g(y)^{r}$	$\displaystyle=\sum_{k=0}^{\infty}{\mathcal{A}}_{k+r,r}(b_{0},b_{1},\dots)y^{k}$
		$\displaystyle=\sum_{k=0}^{\infty}{\mathcal{A}}_{k+r,r}(b_{0},b_{1},\dots)\sum_{n=k}^{\infty}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)x^{n}$
		$\displaystyle=\sum_{n=0}^{\infty}x^{n}\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)\cdot{\mathcal{A}}_{k+r,r}(b_{0},b_{1},\dots).$

To finishes the proof, note that

{\mathcal{A}}_{n+r,r}(c_{0},c_{1},\dots)=[x^{n+r}](c_{0}x+c_{1}x^{2}+\cdots)^{r}=[x^{n}]g(y)^{r}.\qed

(Use (2.17) to simplify this result if $b_{0}=c_{0}=0$ .) Now we see that Proposition 3.1 is just the $r=1$ case of Proposition 3.4. Also (3.11) suggests the following natural extension of Arbogast’s formula to $r$ th powers of a composition. It is probably contained in the large literature on Arbogast’s formula, but we have not found it.

Theorem 3.5.

Let $n$ and $r$ be nonnegative integers. For $n$ times differentiable functions $f$ and $g$ ,

\frac{1}{n!}\frac{d^{n}}{dx^{n}}g(f(x))^{r}=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{f^{\prime}(x)}{1!},\frac{f^{\prime\prime}(x)}{2!},\dots}\right)\cdot{\mathcal{A}}_{k+r,r}\mathopen{}\mathclose{{}\left(\frac{g(f(x))}{0!},\frac{g^{\prime}(f(x))}{1!},\dots}\right).

(3.12)

Proof.

Let $G(x):=g(x)^{r}$ . Applying Proposition 3.1 finds

\frac{1}{n!}\frac{d^{n}}{dx^{n}}G(f(x))=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{f^{\prime}(x)}{1!},\frac{f^{\prime\prime}(x)}{2!},\dots}\right)\cdot\frac{G^{(k)}(f(x))}{k!}.

(3.13)

With $G(x)=h(g(x))$ for $h(x):=x^{r}$ , another application gives

	$\displaystyle\frac{G^{(k)}(y)}{k!}$	$\displaystyle=\sum_{j=0}^{k}\frac{h^{(j)}(g(y))}{j!}\cdot{\mathcal{A}}_{k,j}\mathopen{}\mathclose{{}\left(\frac{g^{\prime}(y)}{1!},\frac{g^{\prime\prime}(y)}{2!},\dots}\right)$
		$\displaystyle=\sum_{j=0}^{k}\binom{r}{j}g(y)^{r-j}\cdot{\mathcal{A}}_{k,j}\mathopen{}\mathclose{{}\left(\frac{g^{\prime}(y)}{1!},\frac{g^{\prime\prime}(y)}{2!},\dots}\right).$		(3.14)

Since $\binom{r}{j}=0$ for $j>r$ and ${\mathcal{A}}_{k,j}=0$ for $j>k$ , we may change the upper limit of summation in (3.14) from $k$ to $r$ . Then by (2.5),

\frac{G^{(k)}(y)}{k!}={\mathcal{A}}_{k+r,r}\mathopen{}\mathclose{{}\left(g(y),\frac{g^{\prime}(y)}{1!},\dots}\right),

and the desired formula follows. ∎

Lastly we mention that it is natural to generalize (1.1) to power series of more than one variable and then consider their compositions. This results in De Moivre polynomials with elaborate indexing; see the recent paper [Sch] and its contained references for details.

3.3 Compositional inverses

We call $g$ a compositional inverse of $f$ if $g(f(x))=x=f(g(x))$ . The usual proof of the following standard result becomes especially clear by employing De Moivre polynomials.

Proposition 3.6.

The series $f(x)=a_{1}x+a_{2}x^{2}+\cdots$ in $R[[x]]$ has a compositional inverse in $R[[x]]$ if and only if $a_{1}$ is invertible in $R$ . This inverse of $f(x)$ is unique.

Proof.

Suppose $a_{1}$ is invertible. To find the compositional inverse, we assume it has the form $g(x)=b_{1}x+b_{2}x^{2}+\cdots$ and try to solve for the coefficients using (3.1). We want

1=c_{1}=b_{1}\cdot{\mathcal{A}}_{1,1}(a_{1},a_{2},\dots)=b_{1}a_{1}

and so $b_{1}=1/a_{1}\in R$ . If we assume that we have found $b_{1}$ , $b_{2},\dots,b_{m-1}$ in $R$ already, then $b_{m}$ is the solution to

0=c_{m}=\sum_{k=1}^{m-1}b_{k}\cdot{\mathcal{A}}_{m,k}(a_{1},a_{2},\dots)+b_{m}\cdot{\mathcal{A}}_{m,m}(a_{1},a_{2},\dots).

(3.15)

With (2.8), ${\mathcal{A}}_{m,m}(a_{1},a_{2},\dots)=a_{1}^{m}$ . Since this is again invertible, we see that $b_{m}\in R$ . By induction we obtain $g$ in $R[[x]]$ so that $g(f(x))=x$ . Repeating this argument for $g$ shows that there exists $h$ in $R[[x]]$ with $h(g(x))=x$ . Then

f(g(x))=h(g(f(g(x))))=h(g(x))=x.

Therefore $g$ is a compositional inverse of $f$ . Uniqueness is proved in the usual way for inverses.

In the other direction, if $f$ has a compositional inverse $g(x)=b_{1}x+b_{2}x^{2}+\cdots$ in $R[[x]]$ then we must have $a_{1}b_{1}=1$ and so $a_{1}$ is invertible. ∎

The relation (3.15) gives a recursive procedure to find the coefficients of the inverse. There is a more direct way to find them though, using Lagrange inversion.

Theorem 3.7 (Lagrange inversion for ${R[[x]]}$ ).

Suppose $f(x)$ and $g(x)$ are compositional inverses in $R[[x]]$ , with neither having a constant term. Then

m[x^{m}]g(x)^{r}=r[x^{m-r}](x/f(x))^{m}\qquad(m,r\in{\mathbb{Z}}_{\geqslant 1}).

(3.16)

See [GJ83, Sec. 1.2] or [Ges16] for this result and generalizations. A simple proof involves formal Laurent series and their residues, meaning the coefficients of $x^{-1}$ . Note that the right side of (3.16) is in $R[[x]]$ by Proposition 3.2, and using its expansion gives:

Corollary 3.8.

Suppose $f(x)=a_{1}x+a_{2}x^{2}+\cdots$ in $R[[x]]$ has compositional inverse $b_{1}x+b_{2}x^{2}+\cdots$ . Then for positive integers $m$ , $r$ ,

	$\displaystyle b_{m}=\frac{1}{m}\sum_{k=0}^{m-1}\binom{-m}{k}a_{1}^{-m-k}{\mathcal{A}}_{m-1,k}(a_{2},a_{3},\dots),$		(3.17)
	$\displaystyle{\mathcal{A}}_{m,r}(b_{1},b_{2},\dots)=\frac{r}{m}\sum_{k=0}^{m-r}\binom{-m}{k}a_{1}^{-m-k}{\mathcal{A}}_{m-r,k}(a_{2},a_{3},\dots).$		(3.18)

Recall that $R$ does not necessarily contain ${\mathbb{Q}}$ . The $1/m$ terms on the right of (3.17) and (3.18) must cancel an $m$ factor so that these are statements in $R$ . We see this cancellation explicitly in section 4.

The next result follows from (3.17), in the same way that Theorem 3.3 followed from Proposition 3.1, and easily extends to derivatives of $g(x)^{r}$ . See [Joh02a] for another approach and references.

Corollary 3.9.

Let $f(x)$ be an $m\geqslant 1$ times differentiable function with compositional inverse $g(x)$ . Then $g(x)$ is $m$ times differentiable and

\frac{1}{m!}\frac{d^{m}}{dx^{m}}g(x)=\frac{1}{m}\sum_{k=0}^{m-1}\binom{-m}{k}\frac{1}{f^{\prime}(g(x))^{m+k}}{\mathcal{A}}_{m-1,k}\mathopen{}\mathclose{{}\left(\frac{f^{\prime\prime}(g(x))}{2!},\frac{f^{\prime\prime\prime}(g(x))}{3!},\dots}\right).

(3.19)

A different kind of inversion was needed in [GWLL21, Eqs. (11), (14)]:

Proposition 3.10.

Let $a_{1},a_{2},\dots$ be a sequence of complex numbers and set

b_{n}(t):=\sum_{k=1}^{n}\frac{t^{k}}{k!}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)\qquad(n\geqslant 1).

Then these relations may be inverted:

a_{n}=\frac{1}{t}\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}{\mathcal{A}}_{n,k}(b_{1}(t),b_{2}(t),\dots)\qquad(n\geqslant 1).

(3.20)

Proof.

By Proposition 3.1, $\exp(t(a_{1}x+a_{2}x^{2}+\cdots))=1+b_{1}(t)x+b_{2}(t)x^{2}+\cdots$ . Then take the log of both sides to obtain (3.20). ∎

Of course, $\exp(x)$ and $\log(x)$ above may be replaced by other pairs of inverse functions; see (6.5) and (6.6) for a different pair. More complicated inversions of this type appear in [BGW19].

4 Greatest common divisor of the coefficients of ${\mathcal{A}}_{n,k}(x_{1},x_{2},\dots)$

It follows from Corollary 3.8, when $a_{1}=1$ and $R={\mathbb{Z}}$ , that for integers $n,m,k\geqslant 1$ we must have

\frac{n}{m}\binom{m}{k}{\mathcal{A}}_{n,k}(x_{1},x_{2},\dots)\in{\mathbb{Z}}[x_{1},x_{2},\dots].

(4.1)

For example, with $n=9$ and $k=4$ this means that all the coefficients of ${\mathcal{A}}_{9,4}$ must be divisible by $4$ . The next result, combined with (4.3) below, may be used to prove (4.1) directly.

Theorem 4.1.

For $n\geqslant k\geqslant 1$ , the $\gcd$ of the coefficients of ${\mathcal{A}}_{n,k}$ is $k/\gcd(n,k)$ .

Proof.

Let $\Delta$ be the $\gcd$ of the coefficients of ${\mathcal{A}}_{n,k}$ . We may assume that $n>k$ as the theorem is clearly true when $n=k$ by (2.8). Recall that the coefficients of ${\mathcal{A}}_{n,k}$ are the multinomial coefficients

\binom{k}{j_{1},j_{2},\dots,j_{m}}\quad\text{with}\quad 1j_{1}+2j_{2}+\dots+mj_{m}=n.

(4.2)

Taking $j_{1}=k-1$ and $j_{n-k+1}=1$ gives the coefficient $k$ and so $\Delta\mid k$ . Our next goal is to show that $(k/\gcd(n,k))\mid\Delta$ .

The elegant argument in [GS95] for binomial coefficients adapts nicely to multinomial coefficients as follows. It is evident that when

C:=\binom{k}{j_{1},j_{2},\dots,j_{m}}\quad\text{we have}\quad\frac{j_{r}}{k}C=\binom{k-1}{j_{1},\dots,j_{r}-1,\dots,j_{m}}

for $1\leqslant r\leqslant m$ with $j_{r}\neq 0$ . Therefore $C_{r}:=j_{r}C/k$ is always an integer for $j_{r}\geqslant 0$ and so

	$\displaystyle k\cdot\gcd\mathopen{}\mathclose{{}\left(C,C_{1},C_{2},\dots,C_{m}}\right)$	$\displaystyle=\gcd\mathopen{}\mathclose{{}\left(kC,kC_{1},kC_{2},\dots,kC_{m}}\right)$
		$\displaystyle=\gcd\mathopen{}\mathclose{{}\left(kC,j_{1}C,j_{2}C,\dots,j_{m}C}\right)$
		$\displaystyle=C\gcd(k,j_{1},j_{2},\dots,j_{m}).$

Hence, for any multinomial coefficient,

\frac{k}{\gcd(k,j_{1},j_{2},\dots,j_{m})}\quad\text{divides}\quad\binom{k}{j_{1},j_{2},\dots,j_{m}}.

(4.3)

Now $\gcd(j_{1},j_{2},\dots,j_{m})\mid n$ by the right side of (4.2) and it follows that $k/\gcd(n,k)$ divides all the coefficients of ${\mathcal{A}}_{n,k}$ .

So far we have demonstrated that $(k/\gcd(n,k))\mid\Delta$ and $\Delta\mid k$ . The next lemma will let us find coefficients that ensure $\Delta\mid(k/\gcd(n,k))$ .

Lemma 4.2.

Let $\alpha$ and $\beta$ be positive integers. Then

\gcd\mathopen{}\mathclose{{}\left(\binom{\alpha\beta}{d_{1}},\binom{\alpha\beta}{d_{2}},\dots,\binom{\alpha\beta}{d_{r}}}\right)\quad\text{divides}\quad\alpha

(4.4)

where $d_{1},d_{2},\dots,d_{r}$ are all the divisors of $\beta$ .

Proof.

For $p$ any prime, let $\nu_{p}$ denote the $p$ -adic valuation. Set $x:=\nu_{p}(\alpha)$ , $y:=\nu_{p}(\beta)$ so that $\alpha=\alpha^{\prime}p^{x}$ and $\beta=\beta^{\prime}p^{y}$ for $\alpha^{\prime}$ , $\beta^{\prime}$ prime to $p$ . We want to establish

\nu_{p}\mathopen{}\mathclose{{}\left(\binom{\alpha\beta}{p^{y}}}\right)=x,

(4.5)

since that will show that the largest power of $p$ dividing the left side of (4.4) is the power of $p$ that divides $\alpha$ .

Use the notation $s_{p}(n)$ to mean the sum of the base $p$ digits of $n$ . Legendre’s well-known formula implies, as in [SMA09, Eq. (1.6)],

\nu_{p}\mathopen{}\mathclose{{}\left(\binom{\alpha\beta}{p^{y}}}\right)=\frac{s_{p}(p^{y})+s_{p}(\alpha\beta-p^{y})-s_{p}(\alpha\beta)}{p-1}.

The numerator on the right equals

s_{p}(p^{y})+s_{p}((\alpha^{\prime}\beta^{\prime}p^{x}-1)p^{y})-s_{p}(\alpha^{\prime}\beta^{\prime}p^{x+y})=1+s_{p}(\alpha^{\prime}\beta^{\prime}p^{x}-1)-s_{p}(\alpha^{\prime}\beta^{\prime}).

If $\alpha^{\prime}\beta^{\prime}$ has the base $p$ representation $c_{1}c_{2}\cdots c_{k}$ then $c_{k}\neq 0$ and $\alpha^{\prime}\beta^{\prime}p^{x}$ has the same digits with $x$ zeros added on the right. Clearly $\alpha^{\prime}\beta^{\prime}p^{x}-1$ will have the representation

c_{1}c_{2}\cdots(c_{k}-1)(p-1)\cdots(p-1),

so that $s_{p}(\alpha^{\prime}\beta^{\prime}p^{x}-1)=s_{p}(\alpha^{\prime}\beta^{\prime})-1+x(p-1)$ . Then (4.5) follows and the lemma is proved. ∎

Now let $d$ be any divisor of $\gcd(n,k)$ . We consider coefficients in (4.2) where only two numbers $j_{1}$ and $j_{r}$ are nonzero, choosing $r:=(n-k)/d+1>1$ . Check that $j_{1}=k-d$ and $j_{r}=d$ gives $1j_{1}+rj_{r}=n$ and so

\binom{k}{d}\quad\text{for}\quad d\mid\gcd(n,k)

(4.6)

is a coefficient of ${\mathcal{A}}_{n,k}$ . Apply Lemma 4.2 with $\alpha=k/\gcd(n,k)$ and $\beta=\gcd(n,k)$ to see that the $\gcd$ of the coefficients of the form (4.6) must divide $k/\gcd(n,k)$ . Therefore $\Delta\mid(k/\gcd(n,k))$ as we wanted. This finishes the proof of Theorem 4.1. ∎

By comparison, the $\gcd$ s of the coefficients of the partial Bell polynomials are much larger. It may be shown for example that ${\mathcal{B}}_{k+3,k}$ has $\gcd$ equalling $\binom{k+3}{4}$ .

5 Determinant formulas

Define the $n\times n$ matrix

\mathcal{M}_{n}(t):=\mathopen{}\mathclose{{}\left(\begin{matrix}a_{1}t&1&&\\ a_{2}t&a_{1}t&1&\\ \vdots&&\ddots&\\ a_{n}t&a_{n-1}t&\dots&a_{1}t\end{matrix}}\right),

with ones above the main diagonal and zeros above those. The next result is a slightly simplified version of [EJ, Thm. 3.1].

Proposition 5.1.

We have

\sum_{k=0}^{n}(-1)^{n+k}t^{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)=\det\mathcal{M}_{n}(t).

(5.1)

Proof.

By (2.18), $t^{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)={\mathcal{A}}_{n,k}(a_{1}t,a_{2}t,\dots)$ and so it is enough to prove (5.1) for $t=1$ . An induction proof is possible since repeatedly expanding the determinant along the top row gives

\det\mathcal{M}_{n}(1)=a_{1}\det\mathcal{M}_{n-1}(1)-a_{2}\det\mathcal{M}_{n-2}(1)+\cdots+(-1)^{n-1}a_{n}.

A more illuminating proof uses (3.8). For $u_{n}:=\sum_{k=0}^{n}(-1)^{k}{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)$ we obtain

(1+a_{1}x+a_{2}x^{2}+\cdots)(1+u_{1}x+u_{2}x^{2}+\cdots)=1.

Therefore

\mathopen{}\mathclose{{}\left(\begin{matrix}1&&&&\\ a_{1}&1&&&\\ a_{2}&a_{1}&1&&\\ \vdots&&\ddots&&\\ a_{n-1}&a_{n-2}&\dots&a_{1}&1\end{matrix}}\right)\mathopen{}\mathclose{{}\left(\begin{matrix}u_{1}\\ u_{2}\\ u_{3}\\ \vdots\\ u_{n}\end{matrix}}\right)=\mathopen{}\mathclose{{}\left(\begin{matrix}-a_{1}\\ -a_{2}\\ -a_{3}\\ \vdots\\ -a_{n}\end{matrix}}\right)

(5.2)

and, by Cramer’s rule, $u_{n}=\det U_{n}/\det U$ where $U$ is the matrix on the left of (5.2) and $U_{n}$ is $U$ with its $n$ th column replaced by the column on the right side of (5.2). Moving this $n$ th column of $U_{n}$ to the left side and changing its sign introduces a $(-1)^{n}$ factor. ∎

The ${\mathcal{A}}_{n,k}$ polynomials can be isolated in (5.1) since clearly

{\mathcal{A}}_{n,k}(a_{1},a_{2},\dots)=(-1)^{n+k}[t^{k}]\det\mathcal{M}_{n}(t).

We may also give exponential and logarithmic versions of Proposition 5.1. Define the matrices

\mathcal{N}_{n}(t):=\mathopen{}\mathclose{{}\left(\begin{matrix}a_{1}t&1&&&\\ a_{2}t&a_{1}t&2&&\\ a_{3}t&a_{2}t&a_{1}t&3&\\ \vdots&&&\ddots&\\ a_{n}t&a_{n-1}t&\dots&a_{2}t&a_{1}t\end{matrix}}\right),\qquad\mathcal{O}_{n}(t):=\mathopen{}\mathclose{{}\left(\begin{matrix}a_{1}t&1&&&\\ 2a_{2}t&a_{1}t&1&&\\ 3a_{3}t&a_{2}t&a_{1}t&1&\\ \vdots&&&\ddots&\\ na_{n}t&a_{n-1}t&\dots&a_{2}t&a_{1}t\end{matrix}}\right),

which are the same as $\mathcal{M}_{n}(t)$ except for multiplying by a factor $j$ on row $j$ , above the main diagonal in $\mathcal{N}_{n}(t)$ and in the first column for $\mathcal{O}_{n}(t)$ .

Proposition 5.2.

We have

	$\displaystyle\sum_{k=0}^{n}(-1)^{n+k}\frac{t^{k}}{k!}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{a_{1}}{1},\frac{a_{2}}{2},\dots}\right)$	$\displaystyle=\frac{1}{n!}\det\mathcal{N}_{n}(t),$		(5.3)
	$\displaystyle\sum_{k=0}^{n}(-1)^{n+k}\frac{t^{k}}{k}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(a_{1},a_{2},\dots}\right)$	$\displaystyle=\frac{1}{n}\det\mathcal{O}_{n}(t).$		(5.4)

Proof.

To prove (5.3) we use (3.3) and it is convenient to set $\alpha_{j}:=-a_{j}/j$ and $f(x)=\alpha_{1}x+\alpha_{2}x^{2}+\cdots$ . For $v_{n}:=\sum_{k=0}^{n}\frac{1}{k!}{\mathcal{A}}_{n,k}(\alpha_{1},\alpha_{2},\dots)$ we obtain

e^{f(x)}=\sum_{n=0}^{\infty}v_{n}x^{n},\qquad e^{f(x)}f^{\prime}(x)=\sum_{n=1}^{\infty}n\cdot v_{n}x^{n-1}.

It follows that

(1+v_{1}x+v_{2}x^{2}+\cdots)(\alpha_{1}+2\alpha_{2}x+3\alpha_{3}x^{2}+\cdots)=(v_{1}+2v_{2}x+3v_{3}x^{2}+\cdots),

and hence

\mathopen{}\mathclose{{}\left(\begin{matrix}1&&&&\\ a_{1}&2&&&\\ a_{2}&a_{1}&3&&\\ \vdots&&\ddots&&\\ a_{n-1}&a_{n-2}&\dots&a_{1}&n\end{matrix}}\right)\mathopen{}\mathclose{{}\left(\begin{matrix}v_{1}\\ v_{2}\\ v_{3}\\ \vdots\\ v_{n}\end{matrix}}\right)=\mathopen{}\mathclose{{}\left(\begin{matrix}-a_{1}\\ -a_{2}\\ -a_{3}\\ \vdots\\ -a_{n}\end{matrix}}\right).

(5.5)

The proof of (5.3) is now completed using the same steps as in Proposition 5.1. The proof of (5.4) is similar, based on (3.4). ∎

6 Generating functions

Some generating functions that lead to interesting De Moivre expressions are shown next. See for example [Com74, Sect. 1.14] and [GKP94, Chapters 6, 7] for more on generating functions.

6.1 Partitions

A partition of a positive integer $n$ is a non-increasing sequence of positive integers that sum to $n$ . If $p_{k}(n)$ denotes the number of partitions of $n$ with at most $k$ parts, then clearly

p_{k}(n)=\sum_{\begin{subarray}{c}1j_{1}+2j_{2}+\dots+nj_{n}=n\\ j_{1}+j_{2}+\dots+j_{n}\leqslant k\end{subarray}}1

(6.1)

where the sum is over all possible $j_{1}$ , $j_{2}$ , …, $j_{n}\in{\mathbb{Z}}_{\geqslant 0}$ and $j_{r}$ indicates the number of parts of size $r$ . Comparing (6.1) with (1.1) confirms the statement in Definition 1.1 that the number of terms in ${\mathcal{A}}_{n,k}$ is the number of partitions of $n$ with exactly $k$ parts. This is $p_{k}(n)-p_{k-1}(n)$ and equals $p_{k}(n-k)$ as seen from the generating function

\sum_{n=0}^{\infty}p_{k}(n)q^{n}=\prod_{j=1}^{k}\frac{1}{1-q^{j}}.

(6.2)

Perhaps the most elegant formulas for $p_{k}(n)$ use Sylvester’s theory of waves from 1857 and quasipolynomials, as described in [O’S18]. With (3.8) we can produce the less enlightening

p_{4}(n)=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(1,1,0,0,-2,0,0,1,1,-1,\dots),

for example, where the rest of the sequence consists of zeros.

Let $p(n)$ denote the number of unrestricted partitions of $n$ . Their generating function is (6.2) with $k=\infty$ . As we saw above, the number of terms in ${\mathcal{A}}_{m+k,k}$ is $p_{k}(m)$ . This equals $p(m)$ for $k\geqslant m$ and the terms correspond to solutions of $1j_{2}+2j_{3}+\cdots+mj_{m+1}=m$ in (1.2). De Moivre’s description in [DM97] essentially gives what must be one of the earliest recursive constructions of the partitions of an integer $m$ : they are $1$ followed by the partitions of $m-1$ , then $2$ followed by the partitions of $m-2$ with smallest part at least $2$ , then $3$ followed by the partitions of $m-3$ with smallest part at least $3$ , and so on as far as $\lfloor m/2\rfloor$ . Lastly include $m$ .

To find a first expression for $p(n)$ we may use Euler’s pentagonal number theorem,

\prod_{j=1}^{\infty}(1-q^{j})=\sum_{r\in{\mathbb{Z}}}(-1)^{r}q^{r(3r-1)/2}=\sum_{m=0}^{\infty}c_{m}q^{m},

with $c_{m}=(-1)^{r}$ if $m=r(3r-1)/2$ for some $r\in{\mathbb{Z}}$ and $c_{m}=0$ otherwise. Therefore, employing (3.8) again,

p(n)=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(-c_{1},-c_{2},-c_{3},\dots)=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(1,1,0,0,-1,0,-1,\dots).

Ramanujan’s tau function has the related generating function

\sum_{n=1}^{\infty}\tau(n)q^{n}=q\prod_{j=1}^{\infty}(1-q^{j})^{24}

(6.3)

where the right side of (6.3) is a modular form when $q=e^{2\pi iz}$ , (a weight $12$ cusp form for $\mathrm{SL}_{2}({\mathbb{Z}})$ ). Then easily,

\tau(n)={\mathcal{A}}_{n+23,24}(c_{0},c_{1},c_{2},\dots)={\mathcal{A}}_{n+23,24}(1,-1,-1,0,0,1,0,\dots)

(6.4)

and Theorem 4.1 implies that $\tau(n)$ is divisible by $24/\gcd(n+23,24)$ . The congruence properties of $\tau(n)$ and $p(n)$ have been of great interest, and Lehmer’s 1947 question as to whether $\tau(n)$ is ever zero remains unanswered. By (3.2) we also have the relations

	$\displaystyle\tau(n)$	$\displaystyle=\sum_{k=0}^{n-1}\binom{-24}{k}{\mathcal{A}}_{n-1,k}(p(1),p(2),p(3),\dots),$		(6.5)
	$\displaystyle p(n)$	$\displaystyle=\sum_{k=0}^{n}\binom{-1/24}{k}{\mathcal{A}}_{n,k}(\tau(2),\tau(3),\tau(4),\dots).$		(6.6)

Set $\sigma(n):=\sum_{d|n}d$ , the sum of the divisors of $n$ . For another example, take the log of the right side of (6.2) when $k=\infty$ , expand this into a series and then exponentiate to produce

p(n)=\sum_{k=0}^{n}\frac{1}{k!}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{\sigma(1)}{1},\frac{\sigma(2)}{2},\frac{\sigma(3)}{3},\dots}\right),

(6.7)

which may also be inverted. The identity (6.7) comes from [Rio68, p. 185], and for further identities along these lines see [Jha].

The authors in [BKO04, Thm. 3] develop a universal recursion for the Fourier coefficients of modular forms. The required polynomials are in fact De Moivre polynomials, and as a special case (see their remark after the theorem) we find:

\tau(n+1)=-\frac{24\sigma(n)}{n}+\sum_{k=2}^{n}\frac{(-1)^{k}}{k}{\mathcal{A}}_{n,k}(\tau(2),\tau(3),\dots)\qquad(n\geqslant 1).

(6.8)

The form of (6.8) now suggests it has an easy proof: take the log of both sides of (6.3) and expand each series.

6.2 Orthogonal polynomials

Bell in [Bel34] was initially interested in generalizing the Hermite polynomials $H_{n}(x)$ . They may be expressed as $n![t^{n}]\exp(2xt-t^{2})$ and in Bell’s original polynomials equal ${\mathcal{Y}}_{n}(2x,-2,0,0,\dots)$ . In our notation

H_{n}(x)=\sum_{k=0}^{n}\frac{n!}{k!}{\mathcal{A}}_{n,k}(2x,-1,0,0,\dots).

(6.9)

Some other classical orthogonal polynomials have similar descriptions, as seen in [Cha02, pp. 449 - 452]. For example, the Gegenbauer polynomials may be defined with $C^{(\lambda)}_{n}(x):=[t^{n}](1-2tx+t^{2})^{-\lambda}$ giving

C^{(\lambda)}_{n}(x)=\sum_{k=0}^{n}\binom{k+\lambda-1}{k}{\mathcal{A}}_{n,k}(2x,-1,0,0,\dots)

(6.10)

by (3.2). Special cases are the Legendre polynomials $P_{n}(x)$ with $\lambda=1/2$ , the Chebyshev polynomials of the second kind $U_{n}(x)$ with $\lambda=1$ , and the usual Chebyshev polynomials $T_{n}(x)$ which may found as a limit when $\lambda\to 0$ . More explicitly, use $T_{n}(x)=[t^{n}](1-tx)/(1-2tx+t^{2})$ to see that

T_{n}(x)=\sum_{k=0}^{n}\Bigl{[}{\mathcal{A}}_{n,k}(2x,-1,0,0,\dots)-x\cdot{\mathcal{A}}_{n-1,k}(2x,-1,0,0,\dots)\Bigr{]}.

(6.11)

The Fibonacci numbers $F_{n}$ equal $[t^{n}]t/(1-t-t^{2})$ and fit the same pattern with

F_{n+1}=\sum_{k=0}^{n}{\mathcal{A}}_{n,k}(1,1,0,0,\dots).

(6.12)

The identity

{\mathcal{A}}_{n,k}(x,y,0,0,\dots)=\binom{k}{n-k}x^{2k-n}y^{n-k}\qquad(n\geqslant k)

(6.13)

may also be employed in (6.9) – (6.12). For example, using (6.13) in (6.11) yields

T_{n}(x)=\sum_{k=1}^{n}(-1)^{n-k}\frac{n}{2k}\binom{k}{n-k}(2x)^{2k-n}\qquad(n\geqslant 1).

(6.14)

In view of the usual definition of $T_{n}$ by $T_{n}(\cos\theta)=\cos n\theta$ , and De Moivre’s formula for the $n$ th power of a complex number, it is not surprising that the polynomial (6.14) already appears in the work of De Moivre, predating Chebyshev’s introduction of $T_{n}(x)$ by over 100 years. Consult [Sch68, p. 246] and [Gir] for further details.

6.3 Bernoulli numbers and polynomials

The Bernoulli numbers are usually defined by $B_{n}:=n![t^{n}]t/(e^{t}-1)$ . Another application of (3.8) yields

B_{n}=n!\sum_{k=0}^{n}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(-\frac{1}{2!},-\frac{1}{3!},-\frac{1}{4!},\dots}\right).

(6.15)

Stern gave further similar expressions for $B_{n}$ in [Ste43], employing the elaborate notation ${}_{\mathfrak{p}}^{n}\overset{k}{C^{\prime}}$ for ${\mathcal{A}}_{n,k}$ . Using the well-known power series for $\tan$ and $\arctan$ in Corollary 3.8 also gives the alternative

2^{n+2}(2^{n+2}-1)\frac{B_{n+2}}{n+2}=n!\sum_{k=0}^{n}\binom{n+k}{k}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(0,-\frac{1}{3},0,-\frac{1}{5},0,\dots}\right).

(6.16)

Extending (6.15) to the Bernoulli polynomials $B_{n}(x):=n![t^{n}]te^{tx}/(e^{t}-1)$ results in

B_{n}(x)=n!\sum_{k=0}^{n}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{(-x)^{2}-(1-x)^{2}}{2!},\frac{(-x)^{3}-(1-x)^{3}}{3!},\dots}\right).

(6.17)

It may be seen from (6.17) that $B_{n}(x)$ is a polynomial in $x$ of degree $n$ and satisfies $B_{n}(1-x)=(-1)^{n}B_{n}(x)$ by (2.19).

The Nörlund polynomials $B_{n}^{(x)}:=n![t^{n}](t/(e^{t}-1))^{x}$ generalize the Bernoulli numbers in another direction. Equation (3.2) finds

B_{n}^{(x)}=n!\sum_{k=0}^{n}\binom{-x}{k}{\mathcal{A}}_{n,k}\mathopen{}\mathclose{{}\left(\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\dots}\right),

(6.18)

making it more obvious by (2.13) that $B_{n}^{(x)}$ is also a degree $n$ polynomial in $x$ . Another expression is proved in [ST88, Eq. 15]:

B_{n}^{(x)}=\sum_{k=0}^{n}\binom{-x}{k}\binom{x+n}{n-k}\binom{n+k}{k}^{-1}{\genfrac{\{}{\}}{0.0pt}{}{n+k}{k}}.

(6.19)

6.4 Cyclotomic polynomials

Ramanujan sums and cyclotomic polynomials may be expressed in terms of the Möbius function $\mu$ with

r_{j}(m)=\sum_{d\mid(m,j)}\mu(m/d)\cdot d,\qquad\Phi_{n}(x)=\prod_{d\mid n}\mathopen{}\mathclose{{}\left(1-x^{d}}\right)^{\mu(n/d)}\quad(n\geqslant 2),

respectively. The authors in [HPM21, Thm. 4.2] write Lehmer’s 1966 formula for $\Phi_{n}(x)$ in an appealing way using Bell polynomials. It is even more transparent without the unnecessary factorials:

\Phi_{n}(x)=\sum_{m=0}^{\infty}\mathopen{}\mathclose{{}\left[\sum_{k=0}^{m}\frac{1}{k!}{\mathcal{A}}_{m,k}\mathopen{}\mathclose{{}\left(-\frac{r_{1}(n)}{1},-\frac{r_{2}(n)}{2},-\frac{r_{3}(n)}{3},\dots}\right)}\right]x^{m},

(6.20)

for $n\geqslant 2$ , and the easy proof is similar to that of (6.7).

7 Asymptotic expansions

In this final section we discuss examples where the De Moivre polynomials play a useful role in describing the behavior of functions and sequences as a parameter goes to infinity.

7.1 Partition asymptotics

Hardy and Ramanujan famously gave the first asymptotic expansion for the partition function $p(n)$ in 1918. Rademacher later showed how a small alteration turned this into a rapidly converging series: [Rad73, Eq. (128.1)]. A simpler, though less accurate, expansion for $p(n)$ takes the form

p(n)=\frac{1}{4\sqrt{3}n}e^{\pi\sqrt{2n/3}}\mathopen{}\mathclose{{}\left(1+\frac{{C}_{1}}{n^{1/2}}+\frac{{C}_{2}}{n^{2/2}}+\cdots+\frac{{C}_{R-1}}{n^{(R-1)/2}}+O\mathopen{}\mathclose{{}\left(\frac{1}{n^{R/2}}}\right)}\right)

(7.1)

showing the main term along with smaller corrections. The constants ${C}_{r}$ are quite complicated, but we may give them a reasonable description. First define

	$\displaystyle\alpha_{j}(x)$	$\displaystyle:=\begin{cases}24^{-j/2}&\text{ for $j$ even}\\ \displaystyle-24^{(1-j)/2}\frac{1}{x}\binom{j/2}{(j-1)/2}&\text{ for $j$ odd},\end{cases}$		(7.2)
	$\displaystyle\beta_{\ell}(x)$	$\displaystyle:=\sum_{\ell/2\leqslant m\leqslant\ell}(-24)^{-m}\frac{x^{2m-\ell}}{(2m-\ell)!}{\mathcal{A}}_{m,2m-\ell}\mathopen{}\mathclose{{}\left(\binom{1/2}{1},\binom{1/2}{2},\binom{1/2}{3},\dots}\right).$		(7.3)

Proposition 7.1.

Fix $R\geqslant 1$ . Let ${C}_{r}$ be defined by $\sum_{j=0}^{r}\alpha_{j}(x)\cdot\beta_{r-j}(x)$ with $x=\pi\sqrt{2/3}$ . For these values, (7.1) is true as $n\to\infty$ with an implied constant depending only on $R$ .

Proof.

Using the first term in his expansion, Rademacher shows

p(n)=\frac{1}{4\sqrt{3}n\cdot\kappa_{n}}\mathopen{}\mathclose{{}\left(1-\frac{1}{x\sqrt{n\cdot\kappa_{n}}}}\right)e^{x\sqrt{n\cdot\kappa_{n}}}\mathopen{}\mathclose{{}\left(1+O(e^{-x\sqrt{n}/2})}\right)

(7.4)

for $\kappa_{n}:=1-1/(24n)$ in [Rad73, p. 278]. Put $z:=-1/(24n)$ and write this main term as

\frac{e^{x\sqrt{n}}}{4\sqrt{3}n}\cdot\frac{1}{1+z}\mathopen{}\mathclose{{}\left(1-\frac{1}{x\sqrt{n(1+z)}}}\right)\cdot e^{x\sqrt{n}(\sqrt{1+z}-1)}.

Treating $z$ as an independent complex variable, the middle factors are analytic for $|z|<1$ and have a Taylor expansion. Using the usual bounds on the remainder shows

\frac{1}{1+z}\mathopen{}\mathclose{{}\left(1-\frac{1}{x\sqrt{n(1+z)}}}\right)=\sum_{j=0}^{J-1}a_{j}(\sqrt{n})\cdot z^{j}+O(|z|^{J})\qquad(|z|\leqslant 1/2).

By the binomial theorem we find $a_{j}(\sqrt{n})=(-1)^{j}-\binom{-3/2}{j}/(x\sqrt{n})$ and hence, with (7.2),

\frac{1}{\kappa_{n}}\mathopen{}\mathclose{{}\left(1-\frac{1}{x\sqrt{n\cdot\kappa_{n}}}}\right)=\sum_{j=0}^{J-1}\alpha_{j}(x)\cdot n^{-j/2}+O(n^{-J/2}).

(7.5)

Similarly to (7.5),

e^{x\sqrt{n}(\sqrt{1+z}-1)}=\sum_{\ell=0}^{L-1}b_{\ell}(\sqrt{n})\cdot z^{\ell}+O(|z|^{L})\qquad(|z|\leqslant 1/\sqrt{n}).

Then the expansions

	$\displaystyle e^{x\sqrt{n}(\sqrt{1+z}-1)}$	$\displaystyle=\exp\biggl{(}x\sqrt{n}\sum_{j=1}^{\infty}\binom{1/2}{j}z^{j}\biggr{)}$
		$\displaystyle=\sum_{k=0}^{\infty}\frac{(x\sqrt{n})^{k}}{k!}\sum_{m=k}^{\infty}{\mathcal{A}}_{m,k}\mathopen{}\mathclose{{}\left(\binom{1/2}{1},\binom{1/2}{2},\binom{1/2}{3},\dots}\right)z^{m}$

imply that

b_{\ell}(\sqrt{n})=\sum_{k=0}^{\ell}\frac{(x\sqrt{n})^{k}}{k!}{\mathcal{A}}_{\ell,k}\mathopen{}\mathclose{{}\left(\binom{1/2}{1},\binom{1/2}{2},\binom{1/2}{3},\dots}\right).

After rearranging we finally obtain, with (7.3),

e^{x\sqrt{n}(\sqrt{\kappa_{n}}-1)}=\sum_{\ell=0}^{L-1}\beta_{\ell}(x)\cdot n^{-\ell/2}+O(n^{-L/2}).

(7.6)

Use (7.5) and (7.6) in (7.4) to complete the proof. ∎

For example,

{C}_{1}=-\frac{72+\pi^{2}}{24\sqrt{6}\pi}\approx-0.443288,\qquad{C}_{2}=\frac{432+\pi^{2}}{6912}\approx 0.0639279.

We see from (7.2), (7.3) that $C_{r}$ is $1/\pi$ times a polynomial in $\pi$ of degree $r+1$ , and so we cannot expect much simplification. Of course (7.4) is more accurate than (7.1), and including more terms of Rademacher’s series is better still. The numbers $p(n)$ are examples of Fourier coefficients of weakly holomorphic modular forms and Rademacher type series exist for all of these. In the next examples though, and many other situations, expansions of the form (7.1) are the best available.

7.2 Laplace’s method

A simple example of Laplace’s method, (and where it overlaps with the saddle-point method), is the following. Suppose that $f(z)$ and $g(z)$ are holomorphic functions on a domain containing the interval $[-1,1]$ and real-valued on this interval. The integral

I(n):=\int_{-1}^{1}e^{n\cdot f(z)}g(z)\,dz

(7.7)

can be accurately estimated for large $n\in{\mathbb{R}}$ if $f^{\prime}(z)$ has a simple zero at $z=0$ (called the saddle-point) and $f(z)<f(0)$ for all non-zero $z\in[-1,1]$ . In that case, the integral becomes highly concentrated at $0$ and as $n\to\infty$ ,

I(n)=e^{n\cdot f(0)}\mathopen{}\mathclose{{}\left(\sum_{r=0}^{R-1}\frac{{\Gamma}(r+1/2)\cdot\Psi_{2r}(f,g)}{n^{r+1/2}}+O\mathopen{}\mathclose{{}\left(\frac{1}{n^{R+1/2}}}\right)}\right)

(7.8)

for certain constants $\Psi_{2r}(f,g)$ . If we write the expansions of $f$ and $g$ at $0$ as

f(z)-f(0)=-\sum_{m=0}^{\infty}a_{m}z^{m+2},\qquad g(z)=\sum_{m=0}^{\infty}b_{m}z^{m}

then we have

\Psi_{s}(f,g)=a_{0}^{-(s+1)/2}\sum_{m=0}^{s}b_{s-m}\sum_{k=0}^{m}\binom{-(s+1)/2}{k}{\mathcal{A}}_{m,k}\mathopen{}\mathclose{{}\left(\frac{a_{1}}{a_{0}},\frac{a_{2}}{a_{0}},\dots}\right).

(7.9)

Laplace found the main term of (7.8) with $r=0$ and $\Psi_{0}(f,g)=a_{0}^{-1/2}b_{0}$ in the 18th century. Perron in [Per17] proved (7.8) rigorously, giving a formula for the constants $\Psi_{2r}(f,g)$ in terms of a derivative. It is then easy to obtain (7.9) with (3.2). See [Nem13] for a discussion of this, and the weaker conditions on $f$ and $g$ that are possible in Laplace’s method. The general forms of (7.8) and (7.9) in Perron’s saddle-point method are also described in Corollary 5.1 and Proposition 7.2 of [O’S19].

For an important application to the gamma function write

{\Gamma}(n+1)=\int_{0}^{\infty}e^{-t}t^{n}\,dt=n^{n+1}\int_{-1}^{\infty}e^{n(\log(1+z)-1-z)}\,dz.

Corollary 7.2 (Stirling’s approximation).

As real $n\to\infty$

{\Gamma}(n+1)=\sqrt{2\pi n}\mathopen{}\mathclose{{}\left(\frac{n}{e}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\frac{{\gamma}_{1}}{n}+\frac{{\gamma}_{2}}{n^{2}}+\cdots+\frac{{\gamma}_{k}}{n^{k}}+O\mathopen{}\mathclose{{}\left(\frac{1}{n^{k+1}}}\right)}\right).

(7.10)

From (7.9) after simplifying, we obtain the coefficients

{\gamma}_{m}=\sum_{j=0}^{2m}\frac{(2m+2j-1)!!}{(-1)^{j}j!}{\mathcal{A}}_{2m,j}\mathopen{}\mathclose{{}\left(\frac{1}{3},\frac{1}{4},\frac{1}{5},\cdots}\right),

(7.11)

as in [Per17, Sect. 5], [O’S19, Sect. 8.1], where $(2k-1)!!$ means the product of the odd numbers less than $2k$ and equals $(2k)!/(2^{k}k!)$ for $k\geqslant 0$ . Stirling’s series for $\log{\Gamma}(n)$ , see [AAR99, Eq. (1.4.5)], is

\log{\Gamma}(n+1)=\log\mathopen{}\mathclose{{}\left(\sqrt{2\pi n}\mathopen{}\mathclose{{}\left(\frac{n}{e}}\right)^{n}}\right)+\frac{B_{2}}{2\cdot 1\cdot n}+\frac{B_{4}}{4\cdot 3\cdot n^{3}}+\cdots+\frac{B_{2k}}{2k(2k-1)n^{2k-1}}+O\mathopen{}\mathclose{{}\left(\frac{1}{n^{2k+1}}}\right),

(7.12)

and may be exponentiated to produce another expression for ${\gamma}_{m}$ :

{\gamma}_{m}=\sum_{j=0}^{m}\frac{1}{j!}{\mathcal{A}}_{m,j}\mathopen{}\mathclose{{}\left(\frac{B_{2}}{2\cdot 1},0,\frac{B_{4}}{4\cdot 3},0,\cdots}\right).

(7.13)

Replacing the Bernoulli numbers in (7.13) with Riemann zeta values, [AAR99, Eq. (1.3.4)], gives the equivalent equality

{\gamma}_{m}=\sum_{j=0}^{m}\frac{1}{j!}{\mathcal{A}}_{m,j}\mathopen{}\mathclose{{}\left(\frac{\zeta(-1)}{-1},\frac{\zeta(-2)}{-2},\frac{\zeta(-3)}{-3},\cdots}\right),

(7.14)

and this has a pleasing symmetry with

{\Gamma}(z+1)=\sum_{m=0}^{\infty}\mathopen{}\mathclose{{}\left[\sum_{j=0}^{m}\frac{1}{j!}{\mathcal{A}}_{m,j}\mathopen{}\mathclose{{}\left({\gamma},\frac{\zeta(2)}{2},\frac{\zeta(3)}{3},\cdots}\right)}\right](-z)^{m},

(7.15)

where ${\gamma}$ is Euler’s constant. We have convergence in (7.15) for $|z|<1$ and it is proved by taking the log of the Weierstrass product for $1/{\Gamma}(z)$ , expanding this into a series, and then exponentiating. Further formulas for ${\gamma}_{m}$ appear in [Com74, p. 267] and [Nem13, Sect. 3]. See [Gél], [Sch68, Sect. 5.3] for the history of Stirling’s series. The common form (7.12) we use today, involving Bernoulli numbers, is due to De Moivre who simplified Stirling’s treatment.

The reciprocal of the gamma function has a similar asymptotic expansion:

\frac{1}{{\Gamma}(n+1)}=\frac{1}{\sqrt{2\pi n}}\mathopen{}\mathclose{{}\left(\frac{e}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1-\frac{{\gamma}_{1}}{n}+\frac{{\gamma}_{2}}{n^{2}}-\cdots+(-1)^{k}\frac{{\gamma}_{k}}{n^{k}}+O\mathopen{}\mathclose{{}\left(\frac{1}{n^{k+1}}}\right)}\right),

(7.16)

and the fact that the same coefficients appear is a consequence of (7.12) containing only odd powers. Of course, since ${\Gamma}(n+1)=n!$ for $n\in{\mathbb{Z}}_{\geqslant 0}$ , the results (7.10) and (7.16) may be used to estimate binomial coefficients or other factorial expressions as their entries go to infinity. See [Boy94] for a generalization of Corollary 7.2 with $n$ replaced by $z\in{\mathbb{C}}$ and $|z|\to\infty$ with $|\arg z|<\pi/2$ .

7.3 A further example

The integral

I_{\alpha}(n):=\int_{1}^{\infty}(\log z)^{n}e^{-\alpha z}\,dz\qquad(\alpha>0),

(7.17)

requires more involved methods than (7.7) to find its behavior as $n\to\infty$ . Since $\log\log z$ does not have a local maximum, we look for a saddle-point $z_{0}$ for the whole integrand. To locate it, recall the Lambert $W$ function. For $x\geqslant 0$ it may be defined as the inverse to $x\mapsto xe^{x}$ so that $W(xe^{x})=x$ . Then $W(x)$ is non-negative and increasing for $x\geqslant 0$ , satisfying $W(x)\leqslant\log x$ when $x\geqslant e$ . An easy calculation finds

z_{0}=e^{W(n/\alpha)}=\frac{n/\alpha}{W(n/\alpha)}.

In this case we may still use Laplace’s method according to the general procedures in [FS09, Sect. B6]. Part of the series (3.5) has to be exponentiated and the polynomials ${\mathcal{A}}_{n,k}$ keep track of all the components. Recalling (3.6), define the rational functions

a_{r}(v):=\sum_{j=0}^{2r}\frac{(2r+2j-1)!!}{j!}\mathopen{}\mathclose{{}\left(\frac{v^{2}}{v+1}}\right)^{j+r}{\mathcal{A}}_{2r,j}(\ell_{3}(v),\ell_{4}(v),\dots).

The next result is proved in [O’S21, Sect. 4].

Theorem 7.3.

Suppose $\alpha>0$ and set $u:=W(n/\alpha)$ . Then as $n\to\infty$ we have

I_{\alpha}(n)=\frac{\sqrt{2\pi}u}{\sqrt{(1+u)n}}\mathopen{}\mathclose{{}\left(\frac{u}{e^{1/u}}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\sum_{r=1}^{R-1}\frac{a_{r}(u)}{n^{r}}+O\mathopen{}\mathclose{{}\left(\frac{(\log n)^{R}}{n^{R}}}\right)}\right)

(7.18)

where the implied constant depends only on $R\geqslant 1$ and $\alpha$ . Also $a_{r}(u)\ll(\log n)^{r}$ .

A more general result allows suitable functions $f(z)$ to be included in the integrand in (7.17) and this is used to prove the asymptotic expansion of the $n$ th Taylor coefficient of a normalized version of the Riemann zeta function $\zeta(s)$ at the central symmetric point $s=1/2$ as $n\to\infty$ . See [O’S21, Thm. 1.5], giving an explicit version of [GORZ19, Thm. 9] by expressing the expansion coefficients in terms of De Moivre polynomials.

References

[AAR99] George E. Andrews, Richard Askey, and Ranjan Roy. Special functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999.
[Arb00] L. F. A. Arbogast. Du calcul des dérivations. Levrault, Strasbourg, 1800.
[Bel34] E. T. Bell. Exponential polynomials. Ann. of Math. (2), 35(2):258–277, 1934.
[BG07] David R. Bellhouse and Christian Genest. Maty’s biography of Abraham De Moivre, translated, annotated and augmented. Statist. Sci., 22(1):109–136, 2007.
[BGW19] Daniel Birmajer, Juan B. Gil, and Michael D. Weiner. A family of Bell transformations. Discrete Math., 342(1):38–54, 2019.
[BKO04] Jan H. Bruinier, Winfried Kohnen, and Ken Ono. The arithmetic of the values of modular functions and the divisors of modular forms. Compos. Math., 140(3):552–566, 2004.
[Boy94] W. G. C. Boyd. Gamma function asymptotics by an extension of the method of steepest descents. Proc. Roy. Soc. London Ser. A, 447(1931):609–630, 1994.
[Cha02] Charalambos A. Charalambides. Enumerative combinatorics. CRC Press Series on Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2002.
[Com74] Louis Comtet. Advanced combinatorics. D. Reidel Publishing Co., Dordrecht, enlarged edition, 1974. The art of finite and infinite expansions.
[Cra05] Alex D. D. Craik. Prehistory of Faà di Bruno’s formula. Amer. Math. Monthly, 112(2):119–130, 2005.
[DM97] Abraham De Moivre. A method of raising an infinite multinomial to any given power, or extracting any given root of the same. Philos. Trans. R. Soc. London, 19(230):619––625, 1697. Also in Miscellanea analytica de seriebus et quadraturis, J. Tonson & J. Watts, London, 1730.
[EJ] Mark Elin and Fiana Jacobzon. Families of inverse functions: coefficient bodies and the Fekete–Szegö problem. arXiv:2012.07153.
[FS09] Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009.
[Gél] Jacques Gélinas. Original proofs of Stirling’s series for log(n!). arXiv: 1701.06689.
[Ges16] Ira M. Gessel. Lagrange inversion. J. Combin. Theory Ser. A, 144:212–249, 2016.
[Gir] Kurt Girstmair. Chebyshev polynomials and Galois groups of De Moivre polynomials. arXiv:2007.14183.
[GJ83] I. P. Goulden and D. M. Jackson. Combinatorial enumeration. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota, Wiley-Interscience Series in Discrete Mathematics.
[GKP94] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete mathematics. Addison-Wesley Publishing Company, Reading, MA, second edition, 1994. A foundation for computer science.
[GORZ19] Michael Griffin, Ken Ono, Larry Rolen, and Don Zagier. Jensen polynomials for the Riemann zeta function and other sequences. Proc. Natl. Acad. Sci. USA, 116(23):11103–11110, 2019.
[GS95] H. W. Gould and Paula Schlesinger. Extensions of the Hermite G.C.D. theorems for binomial coefficients. Fibonacci Quart., 33(5):386–391, 1995.
[GWLL21] Leonardo Rydin Gorjäo, Dirk Witthaut, Klaus Lehnertz, and Pedro G. Lind. Arbitrary-order finite-time corrections for the Kramers-Moyal operator. Entropy, 23(3):Paper No. 517, pp. 15, 2021.
[HPM21] Andrés Herrera-Poyatos and Pieter Moree. Coefficients and higher order derivatives of cyclotomic polynomials: old and new. Expo. Math., 39(3):309–343, 2021.
[Jha] Sumit Kumar Jha. Formulas for the number of $k$ -colored partitions and the number of plane partitions of $n$ in terms of the Bell polynomials. arXiv:2009.04889.
[Joh02a] Warren P. Johnson. Combinatorics of higher derivatives of inverses. Amer. Math. Monthly, 109(3):273–277, 2002.
[Joh02b] Warren P. Johnson. The curious history of Faà di Bruno’s formula. Amer. Math. Monthly, 109(3):217–234, 2002.
[Knu97] Donald E. Knuth. The art of computer programming. Vol. 1. Addison-Wesley, Reading, MA, 1997. Fundamental algorithms, Third edition.
[Nem13] Gergö Nemes. An explicit formula for the coefficients in Laplace’s method. Constr. Approx., 38(3):471–487, 2013.
[O’S] Cormac O’Sullivan. Symmetric functions and a natural framework for combinatorial and number theoretic sequences. arXiv.
[O’S18] Cormac O’Sullivan. Partitions and Sylvester waves. Ramanujan J., 47(2):339–381, 2018.
[O’S19] Cormac O’Sullivan. Revisiting the saddle-point method of Perron. Pacific J. Math., 298(1):157–199, 2019.
[O’S21] Cormac O’Sullivan. Zeros of Jensen polynomials and asymptotics for the Riemann xi function. Res. Math. Sci., 8(3):Paper No. 46, 27, 2021.
[Per17] Oskar Perron. Über die näherungsweise Berechnung von Funktionen großer Zahlen. Sitzungsber. Bayr. Akad. Wissensch. (Münch. Ber.), pages 191–219, 1917.
[Pit06] J. Pitman. Combinatorial stochastic processes, volume 1875 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002.
[Rad73] Hans Rademacher. Topics in analytic number theory. Springer-Verlag, New York, 1973. Edited by E. Grosswald, J. Lehner and M. Newman, Die Grundlehren der mathematischen Wissenschaften, Band 169.
[Rio68] John Riordan. Combinatorial identities. John Wiley & Sons, Inc., New York-London-Sydney, 1968.
[Sch] Aidan Schumann. Multivariate Bell polynomials and derivatives of composed functions. arXiv: 1903.03899.
[Sch68] Ivo Schneider. Der Mathematiker Abraham de Moivre (1667–1754). Arch. History Exact Sci., 5(3-4):177–317, 1968.
[SMA09] Armin Straub, Victor H. Moll, and Tewodros Amdeberhan. The $p$ -adic valuation of $k$ -central binomial coefficients. Acta Arith., 140(1):31–42, 2009.
[ST88] H. M. Srivastava and Pavel G. Todorov. An explicit formula for the generalized Bernoulli polynomials. J. Math. Anal. Appl., 130(2):509–513, 1988.
[Ste43] Moritz A. Stern. Ueber die Coëfficienten der Secantenreihe. J. Reine Angew. Math., 26:88–91, 1843.

Dept. of Math, The CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016-4309, U.S.A.

E-mail address: [email protected]

De Moivre and Bell polynomials

Abstract

1 Introduction

Definition 1.1.

2 Basic properties of 𝒜n,k{\mathcal{A}}_{n,k}

Lemma 2.1.

Proof.

Lemma 2.2.

Lemma 2.3.

Proposition 2.4.

3 Manipulating power series

3.1 Series composition

Proposition 3.1.

Proof.

Proposition 3.2.

3.2 Arbogast’s formula

Theorem 3.3 (Arbogast’s formula).

Proof.

Proposition 3.4.

Proof.

Theorem 3.5.

Proof.

3.3 Compositional inverses

Proposition 3.6.

Proof.

Theorem 3.7 (Lagrange inversion for R​[[x]]{R[[x]]}).

Corollary 3.8.

Corollary 3.9.

Proposition 3.10.

Proof.

4 Greatest common divisor of the coefficients of 𝒜n,k​(x1,x2,…){\mathcal{A}}_{n,k}(x_{1},x_{2},\dots)

Theorem 4.1.

Proof.

Lemma 4.2.

Proof.

5 Determinant formulas

Proposition 5.1.

Proof.

Proposition 5.2.

Proof.

6 Generating functions

6.1 Partitions

6.2 Orthogonal polynomials

6.3 Bernoulli numbers and polynomials

6.4 Cyclotomic polynomials

7 Asymptotic expansions

7.1 Partition asymptotics

Proposition 7.1.

Proof.

7.2 Laplace’s method

Corollary 7.2 (Stirling’s approximation).

7.3 A further example

Theorem 7.3.

References

2 Basic properties of ${\mathcal{A}}_{n,k}$

Theorem 3.7 (Lagrange inversion for ${R[[x]]}$ ).

4 Greatest common divisor of the coefficients of ${\mathcal{A}}_{n,k}(x_{1},x_{2},\dots)$