On the Central Antecedents of Integer (and Other) Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

With each power series g(x) with g(0) ≠ 0, we associate a power series G(x) such that [x^{n}]G(x)^{n} = [x^{n}]g(x). We give examples for well-known integer sequences, including the Catalan numbers and generalized Catalan numbers, and explore the antecedents of rational sequences, including the Bernoulli numbers and the harmonic numbers.

1 Introduction

The central coefficients of common number triangles have been objects of study over the history of mathematics. The best known such sequence is the sequence \binom{2n}{n} \underline{A000984}, the central coefficient sequence of Pascal’s triangle. It has many important properties. Germane to this note is the following property. We have

\binom{2n}{n} = [x^{n}]\frac{1}{\sqrt{1 − 4x}} = [x^{n}](1 + 2x + x^{2})^{n}.

We say that the sequence 1, 2, 1, 0, 0, 0, … is a central antecedent of the sequence \binom{2n}{n}. In a similar way, the sequence 1, 1, 1, 0, 0, 0, … is the central antecedent of the central trinomial numbers t_{n} \underline{A002426} that begin 1, 1, 3, 7, 19, 51, 141, 393, 1107, . . .. In this case, we have

[x^{n}]\frac{1}{\sqrt{1 − 2x − 3x^{2}}} = [x^{n}](1 + x + x^{2})^{n}.

By analogy, we say that (1 + x)^{2} = 1 + 2x + x^{2} is the central antecedent of \frac{1}{\sqrt{1−4x}}, and that 1 + x + x^{2} is the central antecedent of \frac{1}{\sqrt{1−2x−3x^{2}}} .

In general, if two generating functions are related by [x^{n}]g(x) = [x^{n}]G(x)^{n}, we shall say that G(x) is a central antecedent of g(x). If under these circumstances we have b_{n} = [x^{n}]G(x), we shall say that the sequence b_{n} is a central antecedent sequence of the sequence a_{n} = [x^{n}]g(x).

In the sequel, we shall identify integer sequences by their sequence number in the On-Line Encyclopedia of Integer Sequences [12, 13].

Another perspective on the above is given by the following diagonalization formula [9]. Given two power series

g(x) = g_{0} + g_{1}x + g_{2}x^{2} + …,

and

f(x) = f_{0} + f_{1}x + f_{2}x^{2} + …,

we have

[x^{n}]g(x)f(x)^{n} = [x^{n}] [\frac{g(w)}{1 − xf′(w)}|w = xf(w)] .

The terms [x^{n}]g(x)f(x)^{n} then correspond to the diagonal terms of the matrix whose (n, k)- term is given by

[x^{n}]g(x)f(x)^{k}.

We now note that

[x^{n}]g(x)f(x)^{n} = [x^{2n}]g(x)(xf(x))^{n},

thus expressing the terms [x^{n}]g(x)f(x)^{n} as the “central” terms of the lower-triangular matrix with (n, k)-term [x^{n}]g(x)(xf(x))^{k}. We have opted to use the term “central” in this context, although, as pointed out by a reviewer, the term “diagonal” could have been used with equal justification.

We note that in the diagonalization formula above, we have the condition w = xf(w) which defines the power series w(x). In fact, we have

w = xf(w) ⟹ \frac{w}{f(w)} = x ⟹ w(x) = Rev (\frac{x}{f}) (x),

where Rev F (x) denotes the compositional inverse of F (x), often denoted by F̄(x) or F^{⟨−1⟩}(x). Thus we have

[x^{n}]g(x)f(x)^{n} = [x^{n}]\frac{g(Rev (\frac{x}{f}))}{1 − xf′ (Rev (\frac{x}{f}))}.

Example 1. We let g(x) = \frac{1}{\sqrt{1−4x}}, and f(x) = \frac{1}{1−x}. The matrix with (n, k)-term [x^{n}]g(x)f(x)^{k} begins

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 5 & 8 & 11 & 14 & 17 & 20 \\ 6 & 21 & 45 & 78 & 120 & 171 & 231 \\ 20 & 83 & 218 & 452 & 812 & 1325 & 2018 \\ 70 & 319 & 973 & 2329 & 4765 & 8740 & 14794 \\ 252 & 1209 & 4128 & 11115 & 25410 & 51630 & 96012 \\ 924 & 4551 & 16935 & 50280 & 126510 & 281400 & 569436 \end{matrix} ) ,

while the lower-triangular matrix with (n, k)-term [x^{n}]g(x)(xf(x))^{k} begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 & 0 & 0 \\ 20 & 21 & 8 & 1 & 0 & 0 & 0 \\ 70 & 83 & 45 & 11 & 1 & 0 & 0 \\ 252 & 319 & 218 & 78 & 14 & 1 & 0 \\ 924 & 1209 & 973 & 452 & 120 & 17 & 1 \end{matrix} ) .

We have f′(x) = \frac{3}{(1−3x)^{2}} and Rev (\frac{x}{f(x)}) = \frac{1−\sqrt{1−12x}}{6}. Then we find that

[x^{n}]g(x)f(x)^{n} = [x^{2n}]g(x)(xf(x))^{n} = [x^{n}]\frac{\sqrt{3}(1 − 12x + \sqrt{1 − 12x})}{2(1 − 12x)\sqrt{1 + 2\sqrt{1 − 12x}}}.

We infer that the sequence that begins 1, 5, 45, 452, 4765, 51630, … has generating function

\frac{\sqrt{3}(1 − 12x + \sqrt{1 − 12x})}{2(1 − 12x)\sqrt{1 + 2\sqrt{1 − 12x}}}.

Historically, the coefficients \binom{2n}{n} are called the central binomial coefficients because they appear as the central numbers of Pascal’s triangle when this is displayed as a pyramid.

1

1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1

2 An example from Henrici

Henrici [6] gives the example of the use of Lagrange inversion to derive g(x) from G(x) in the case of the trinomial numbers t_{n} = [x^{n}](1 + x + x^{2})^{n}. The version of Lagrange inversion used for this takes the following form.

Proposition 2. [6, Corollary 1.9c p. 59] For S ∈ 𝕂[[x]] and P ∈ x𝕂[[x]], with Q = P^{⟨−1⟩}, we have

(S ∘ Q)Q′ = ∑_{n=0}^{n} res(SP^{−n−1})x^{n}.

Here, the coefficient a_{1} of x^{−1} in a Laurent series L = ∑_{k=0}^{∞} a_{k}x^{k} is called the residue of L, denoted by res(L). The notation Q = P^{⟨−1⟩} means that Q is the compositional inverse of P. The field K is assumed to be of characteristic zero. We then have

[x^{n}](1 + x + x^{2})^{n} = res[x^{−n−1}(1 + x + x^{2})^{n}] = res(SP^{−n−1}),

where

S(x) = \frac{1}{1 + x + x^{2}} , and P (x) = \frac{x}{1 + x + x^{2}} .

From this we infer that

\frac{1 + Q + Q^{2}}{Q} = x,

which we may solve for Q to get

Q = \frac{2x}{1 − x + \sqrt{1 − 2x − 3x^{2}}} .

Then

(S ∘ Q)(x) = S(Q(x)) = \frac{1}{1 + Q + Q^{2}} = \frac{x}{Q} = \frac{1 − x + \sqrt{1 − 2x − 3x^{2}}}{2} .

Thus we have

(S ∘ Q)Q′ = \frac{1 − x + \sqrt{1 − 2x − 3x^{2}}}{2} · \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}\sqrt{1 − 2x − 3x^{2}}} = \frac{1}{\sqrt{1 − 2x − 3x^{2}}} .

This then gives an example of going from G(x) to g(x). In this note, the emphasis will be on going in the other direction.

3 The main results

We shall use the techniques of Lagrange inversion [8] and the method of coefficients [9]. We need the following version of Lagrange inversion in the sequel [7, 8, 14]. We use the notation Rev(P) = P^{⟨−1⟩}, the compositional inverse of P.

Theorem 3. (Lagrange-Bürmann inversion). Suppose that a formal power series w = w(t) is implicitly defined by the relation w = tϕ(w), where ϕ(t) is a formal power series such that ϕ(0) ≠ 0. Then, for any formal power series F (t),

[t^{n}]F (w(t)) = \frac{1}{n}[t^{n−1}]F′(t)(ϕ(t))^{n}.

A consequence of this is that if v(x) = ∑_{n≥0} v_{n}x^{n} is a power series with v_{0} = 0, v_{1} ≠ 0, we have

[x^{n}]F (Rev(v)) = \frac{1}{n}[x^{n−1}]F′(x) (\frac{x}{v})^{n} .

Proposition 4. We have

[x^{n}] (1 + x\frac{d}{dx} ln (\frac{1}{x} Rev(f(x)))) = [x^{n}] (\frac{x}{f(x)})^{n} .

Proof. We have

[x^{n}] (1 + x\frac{d}{dx} ln (\frac{1}{x} Rev(f(x)))) = 0 + [x^{n−1}]\frac{d}{dx} ln (\frac{1}{x} Rev(f(x)))

= n[x^{n}] ln (\frac{1}{x} Rev(f(x)))

= n[x^{n}] (ln (Rev(f(x))) − ln(x))

= n · \frac{1}{n}[x^{n−1}]\frac{1}{x} (\frac{x}{f(x)})^{n} − \frac{n}{n}[x^{n−1}]\frac{1}{x}(1)^{n}

= [x^{n}] (\frac{x}{f(x)})^{n} − [x^{n}].1

= [x^{n}] (\frac{x}{f(x)})^{n} .

Corollary 5. If [x^{n}]g(x) = [x^{n}]G(x)^{n}, then we have

g(x) = 1 + x\frac{d}{dx} ln (\frac{1}{x} Rev (\frac{x}{G(x)})) .

Theorem 6. Let g(x) be a power series with g(0) ≠ 0. Then the central antecedent G(x) of g(x), which satisfies [x^{n}]G(x)^{n} = [x^{n}]g(x), is given by

G(x) = \frac{x}{Rev (xe^{∫{x \atop 0} \frac{g(t)−1}{t}} dt)}.

Example 7. We take the example of \binom{2n}{n} = [x^{n}]\frac{1}{\sqrt{1−4x}}. We have the following steps.

1. Set g(x) = \frac{1}{\sqrt{1−4x}}.

2. Form \frac{g(x)−1}{x} = \frac{1−\sqrt{1−4x}}{x\sqrt{1−4x}}.

3. Carry out the integration ∫_{0}^{x} \frac{g(t)−1}{t} dt = −2 ln (\frac{1+\sqrt{1−4x}}{2}).

4. Calculate xe^{−2 ln( \frac{1+\sqrt{1−4x}}{2} )} = \frac{1−2x−\sqrt{1−4x}}{2x} = c(x) − 1.

5. Revert \frac{1−2x−\sqrt{1−4x}}{2x} to get \frac{x}{(1+x)^{2}} .

6. Calculate G(x) = \frac{x}{\frac{x}{(1+x)^{2}}} = (1 + x)^{2}. In this list, we have used

c(x) = \frac{1 − \sqrt{1 − 4x}}{2x}

which is the generating function of the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} \underline{A000108}. It is instructive to visualize the sequences encountered in this list of operations. Thus we have

1. 1, 2, 6, 20, 70, 252, 924, 3432, . . ..

2. 2, 6, 20, 70, 252, 924, 3432, . . ..

3. 0, 2, 3, \frac{20}{3}, \frac{35}{2}, \frac{252}{5}, 154, . . ..

4. 1, 2, 5, 14, 42, 132, 429, . . ..

5. 0, 1, −2, 3, −4, 5, −6, 7, . . ..

6. 1, 2, 1, 0, 0, 0, . . .. We conclude that

\binom{2n}{n} = [x^{n}]\frac{1}{\sqrt{1 − 4x}} = [x^{n}](1 + x)^{2n}.

Example 8. We now take the example of g(x) = \frac{1}{\sqrt{1−2x−3x^{2}}} , the generating function of the central trinomial coefficients t_{n} [10]. We have the following list of operations.

1. Set g(x) = \frac{1}{\sqrt{1−2x−3x^{2}}} .

2. Form \frac{g(x)−1}{x} = \frac{1−\sqrt{1−2x−3x^{2}}}{x\sqrt{1−2x−3x^{2}}} .

3. Carry out the integration ∫_{0}^{x} \frac{g(t)−1}{t} dt = ln (\frac{−1+x+\sqrt{1−2x−3x^{2}}}{2} ) − 2 ln(x) − πi sgn(x).

4. Calculate xe^{ln(^{\frac{−1+x+\sqrt{1−2x−3x^{2}}}{2}} )−2 ln(x)−πi sgn(x)} = \frac{1−x−\sqrt{1−2x−3x^{2}}}{2x} = xm(x).

5. Revert xm(x) to get \frac{x}{1+x+x^{2}} .

6. Calculate G(x) = \frac{x}{\frac{x}{1+x+x^{2}}} = 1 + x + x^{2}. In this list, we have

m(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} .

This is the generating function of the Motzkin numbers M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}.

We conclude that

t_{n} = [x^{n}]\frac{1}{\sqrt{1 − 2x − 3x^{2}}} = [x^{n}](1 + x + x^{2})^{n}.

4 The central antecedent of 1, r, r, r, …

In this section, we shall explore the antecedent of the sequence

1, r, r, r, …

with generating function 1 + rx/(1 − x). Proposition 9. The central antecedent of the sequence 1, r, r, r, … has generating function

\frac{1}{∑{∞ \atop n=0} \frac{(−1)^{n}\binom{(n+1)r}{n}x^{n}}{n+1}} .

Proof. Let g(x) = 1 + \frac{rx}{1−x}. Then

\frac{g(x) − 1}{x} = \frac{r}{1 − x}.

We have

∫_{0}^{x} \frac{r}{1 − t} dt = −r ln(x − 1) + πir.

Then

e^{∫_{0}^{x} \frac{r}{1−t} dt} = \frac{1}{(1 − x)^{r}} .

The reversion of \frac{x}{(1−x)^{r}} is now given by x ∑_{n=0}^{∞} \frac{(−1)^{n}\binom{(n+1)r}{n}x^{n}}{n+1} . The statement of the proposition now results from this.

5 The antecedent of \frac{1+(a−b)x}{(1+ax)^{2}}

We let

g(x) = \frac{1 + (a − b)x}{(1 + ax)^{2}}.

In order to find the central antecedent of g(x), we have the following list of operations. 1. Set g(x) = \frac{1+(a−b)x}{(1+ax)^{2}}.

2. Form \frac{g(x)−1}{x} = −\frac{a+b+a^{2}x}{(1+ax)^{2}}.

3. Carry out the integration ∫_{0}^{x} \frac{g(t)−1}{t} dt = − ln(1 + ax) − \frac{bx}{1+ax}.

4. Calculate xe^{− ln(1+ax)− \frac{bx}{1+ax}} = \frac{xe^{\frac{bx}{1+ax}}}{1+ax}.

5. Revert \frac{xe^{\frac{bx}{1+ax}}}{1+ax} to get \frac{−xW (−x)}{−axW (−x)−bx}.

6. Calculate G(x) = _{\frac{x}{\frac{−xW (−x)}{−axW (−x)−bx}}} = −ax − \frac{bx}{W (−x)}. Here, W (x) is the Lambert function [2], given by the reversion of xe^{x} (we use the principal branch W_{0}). We then have the following proposition. Proposition 10. We have

[x^{n}]\frac{1 + (a − b)x}{(1 + ax)^{2}} = [x^{n}] (−ax − \frac{bx}{W (−x)})^{n} .

Example 11. When a = b = −1, we have g(x) = \frac{1}{(1−x)^{2}} , the generating function of the counting numbers 1, 2, 3, … \underline{A000027}. Thus we have

n + 1 = [x^{n}]\frac{1}{(1 − x)^{2}} = [x^{n}] (x + \frac{x}{W (−x)})^{n} .

More generally, we have

rn + 1 = [x^{n}]\frac{1 + (r − 1)x}{(1 − x)^{2}} = [x^{n}] (x + \frac{rx}{W (−x)})^{n} .

6 The case G(x) = 1 + ax + bx^{2}

Proposition 12. We have

[x^{n}](1 + ax + bx^{2})^{n} = [x^{n}]\frac{1}{\sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}} .

Proof. We let G(x) = 1 + ax + bx^{2}. Then

\frac{1}{x} Rev \frac{x}{G(x)} = \frac{1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}}{2bx^{2}} .

It follows that

g(x) = 1 + x\frac{d}{dx} ln (\frac{1}{x} Rev (\frac{x}{G(x)})) = \frac{1}{\sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}} .

The sequences u_{n} = [x^{n}](1 + ax + bx^{2})^{n} = [x^{n}]\frac{1}{\sqrt{1−2ax+(a^{2}−4b)x^{2}}} are well documented in the literature, as they have many interesting properties [10]. For instance,

1. They have exponential generating function I_{0}(2\sqrt{b}x)e^{ax}

2. They are moment sequences with u_{n} = \frac{1}{π} ∫_{a−2\sqrt{b}}^{a+2\sqrt{b}} \frac{x^{n}}{\sqrt{−x^{2}+2ax−a^{2}+4b}} dx

3. The generating function g(x) has the following continued fraction expression

g(x) = \frac{1}{1 − ax − \frac{2bx^{2}}{1 − ax − \frac{bx^{2}}{1 − ax − \frac{bx^{2}}{1 − ax − ⋯}}}}.

7 The Catalan numbers

We have the following result concerning the central antecedent for the Catalan numbers. Proposition 13. We have

C_{n} = [x^{n}] (2x − xW (−x) − \frac{x}{W (−x)})^{n} .

Proof. We proceed with the following steps.

1. Set g(x) = c(x) = \frac{1−\sqrt{1−4x}}{2x}.

2. Form \frac{g(x)−1}{x} = \frac{c(x)−1}{x} = c(x)^{2}.

3. Carry out the integration ∫_{0}^{x} c(t)^{2} dt = −2 ln (\frac{1+\sqrt{1−4x}}{2}) + \frac{\sqrt{1−4x}+2x−1}{2x}.

4. Calculate exp (−2 ln (\frac{1+\sqrt{1−4x}}{2}) + \frac{\sqrt{1−4x}+2x−1}{2x}) = e^{− \frac{1−2x−\sqrt{1−4x}}{2x}} \frac{1−2x−\sqrt{1−4x}}{2x}.

5. Revert xe^{− \frac{1−2x−\sqrt{1−4x}}{2x}} \frac{1−2x−\sqrt{1−4x}}{2x} to get \frac{x}{G(x)}.

We can also write this result as

C_{n} = [x^{n}] (\frac{−x(1 − W (−x))^{2}}{W (−x)} )^{n} .

We have

C_{n} = [x^{n}] (1 + x + \frac{x^{2}}{2} + \frac{x^{3}}{3} + \frac{3x^{4}}{8} + \frac{8x^{5}}{15} + \frac{125x^{6}}{144} + ⋯)^{n} .

We note that we have

\binom{2n + 1}{n + 1} = [x^{n}] (\frac{x(1 + W (−x))^{2}}{W (−x)} )^{n} .

Compare this with

n + 1 = [x^{n}] (\frac{x(1 + W (−x))}{W (−x)})^{n} ,

while

1 − n = [x^{n}] (\frac{x(1 − W (−x))}{W (−x)})^{n} .

It is possible to generalize this result in two directions. The first is to replace the specific quadratic (1 − W (−x))^{2} by the more general quadratic 1 − aW (−x) − bW (−x)^{2}. We find that the terms

[x^{n}] (\frac{−x(1 − aW (−x) − bW (−x)^{2})}{W (−x)})^{n} ,

which begin

1, a − 1, a^{2} − 2a − 2b, a^{3} − 3a^{2} − 6ab + 3b, a^{4} − 4a^{3} − 12a^{2}b + 12ab + 6b^{2}, …,

can be represented by

( 1  0  0  0  0 0 ; −1  1  0  0  0 0 ; −2b −2 1  0  0 0 ; 3b −6b −3  1  0 0 ; 6b^{2} 12b −12b −4 1 0 ; −10b^{2} 30b^{2} 30b −20b −5 1 ; ⋮ ) ( 1 ; a ; a^{2} ; a^{3} ; a^{4} ; a^{5} ; ⋮ ) .

The matrix is the exponential Riordan array [1] [I_{0}(2i\sqrt{b}x) − \frac{I_{1}(2i\sqrt{b}x)}{i\sqrt{b}}, x] and so we have

[x^{n}] (\frac{−x(1 − aW (−x) − bW (−x)^{2})}{W (−x)})^{n} = n![x^{n}] (I_{0}(2i\sqrt{b}x) − \frac{I_{1}(2i\sqrt{b}x)}{i\sqrt{b}}) e^{ax},

or equivalently

[x^{n}] (\frac{−x(1 − aW (−x) − bW (−x)^{2})}{W (−x)})^{n} = [x^{n}]\frac{1 − (a − 2b)x − \sqrt{1 − 2ax + (a^{2} + 4b)x^{2}}}{2bx\sqrt{1 − 2ax + (a^{2} + 4b)x^{2}}} .

The general term of the sequence 1, a − 1, a^{2} − 2a − 2b, a^{3} − 3a^{2} − 6ab + 3b, … is given by

∑_{k=0}^{n} \binom{n}{k}\binom{n − k}{⌊\frac{n−k}{2}⌋}b^{⌊ \frac{n−k}{2} ⌋}(−1)^{\binom{n−k+1}{2}}a^{k}.

For instance, the Motzkin sums \underline{A005043} that begin

1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, …,

are given by a = 1, b = −1 and hence the terms of this sequence are given by

[x^{n}] (\frac{−x(1 − W (−x) + W (−x)^{2})}{W (−x)})^{n} .

Similarly the binomial transform of the Catalan numbers \underline{A007317}, which begins

1, 2, 5, 15, 51, 188, 731, 2950, 12235, …,

has its general term given by

[x^{n}] (\frac{−x(1 − 3W (−x) + W (−x)^{2})}{W (−x)})^{n} .

The other direction for generalization is to modify (1 − W (−x))^{2} to (1 − W (−x))^{m}. We then have the following conjecture.

Conjecture 14. We have

[x^{n}]g_{m}(x) = [x^{n}] (\frac{−x(1 − W (−x))^{m}}{W (−x)} )^{n} ,

where g_{m}(x) is the generating function of the central coefficients \frac{(m−2)n+1}{(m−1)n+1} \binom{mn}{n} of the Riordan array (c(x), xc(x)^{m−2}).

For m = 0, …, 5 we get the sequences

\begin{matrix}1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & −1 & −2 & −3 & −4 & −5 & −6 & −7 & −8 & −9 \\ 1 & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & 16796 \\ 1 & 2 & 9 & 48 & 275 & 1638 & 9996 & 62016 & 389367 & 2466750 & 15737865 \\ 1 & 3 & 20 & 154 & 1260 & 10659 & 92092 & 807300 & 7152444 & 63882940 & 574221648 \\ 1 & 4 & 35 & 350 & 3705 & 40480 & 451269 & 5101360 & 58261125 & 670609940 & 7766844470 \end{matrix}

The sequence \frac{(m−2)n+1}{(m−1)n+1} \binom{mn}{n} counts standard Young tableaux of shape [(m − 1)n, n]. Note that we also have

[x^{n}]g_{m}(x) = [x^{n}]c(x)^{(m−2)n+1}.

The number array above is essentially \underline{A214776}.

8 Divisors and partitions

We define the sequence σ_{n}^{∗} as follows.

σ_{n}^{∗} = 0^{n} + ∑_{d=0}^{n}[d|n]d.

Here, we have used the Iverson notation [5] [P] = 1 if the statement P is true, otherwise the value is 0. The sequence σ_{n}^{∗} (essentially \underline{A000203}) begins

1, 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, ….

Setting g(x) = ∑_{n=0}^{∞} σ_{n}^{∗}x^{n}, we have

g(x) = 1 − \frac{x\frac{d}{dx} ∏_{k=1}^{∞}(1 − x^{k})}{∏_{k=1}^{∞}(1 − x^{k})}.

Thus we have

\frac{g(x) − 1}{x} = \frac{\frac{d}{dx} ∏_{k=1}^{∞}(1 − x^{k})}{∏_{k=1}^{∞}(1 − x^{k})}.

We then have

e^{∫{x \atop 0} \frac{g(t)−1}{t} dt} = π(x) = ∏_{k=1}^{∞} \frac{1}{1 − x^{k}} .

This is the generating function of the partition numbers π(x) = ∑_{n=0}^{∞} p_{n}x^{n} \underline{A000041}. Thus we have the following proposition.

Proposition 15. Let

σ_{n}^{∗} = 0^{n} + ∑_{d=0}^{n}[d|n]d,

and let π(x) = ∑_{n=0}^{∞} p_{n}x^{n} where p_{n} are the partition numbers. Then we have

σ_{n}^{∗} = [x^{n}] (1 − \frac{x\frac{d}{dx} ∏_{k=1}^{∞}(1 − x^{k})}{∏_{k=1}^{∞}(1 − x^{k})}) = [x^{n}] (\frac{x}{Rev(xπ(x))})^{n} .

Numerically, we have

σ_{n}^{∗} = [x^{n}](1 − x + 2x^{3} − 3x^{4} + 5x^{6} − 21x^{8} + 14x^{9} + 117x^{10} + ⋯)^{n}.

The central antecedent sequence of the partition numbers begins

1, 1, \frac{1}{2}, −\frac{1}{3}, \frac{1}{8}, −\frac{2}{15}, \frac{71}{144}, −\frac{11}{10}, \frac{9583}{5760}, ….

9 The J. C. P. Miller recurrence

The J. C. P. Miller recurrence [6, 3, 15] gives a method to calculate the coefficients of the power series f(x)^{n} knowing the coefficients of f(x). Thus assume that

f(x)^{n} = ∑_{k=0}^{Nn} c_{k}x^{k}

where f(x) = ∑_{k=0}^{N} a_{k}x^{k}, where N could be ∞ and a_{0} ≠ 0, then we have

c_{0} = a_{0}^{n}, c_{k} = \frac{1}{ka_{0}} ∑_{j=1}^{N}((n + 1)j − k)a_{j}c_{n−j}.

We reproduce the proof by Zeilberger [3, 15]. The term c_{k} is the coefficient of x^{0} in the Laurent series expansion of \frac{f(x)^{n}}{x^{k}}. For any Laurent series g(x), the coefficient of x^{0} in x\frac{d}{dx}g(x) is zero. Thus

0 = [x^{0}]x \frac{d}{dx} \frac{f(x)^{n+1}}{x^{k}}

= [x^{0}] ((−k(a_{0} + a_{1}x + ⋯ + a_{N} x^{N}) \frac{f(x)^{n}}{x^{k}} + (n + 1)(a_{1} + 2a_{2}x + ⋯ + Na_{N} x^{N−1}) \frac{f(x)^{n}}{x^{k−1}} )

= [x^{0}] (−k (a_{0} \frac{f(x)^{n}}{x^{k}} + a_{1} \frac{f(x)^{n}}{x^{k−1}} + ⋯ + a_{N} \frac{f(x)^{n}}{x^{k−N}} ) + (n + 1) (a_{1} \frac{f(x)^{n}}{x^{k−1}} + 2a_{2} \frac{f(x)^{n}}{x^{k−2}} + ⋯ + Na_{N} \frac{f(x)^{n}}{x^{k−N}} ))

= −k(a_{0}c_{k} + a_{1}c_{k−1} + ⋯ + a_{N} c_{k−N}) + (n + 1)(a_{1}c_{k−1} + 2a_{2}c_{k−2} + ⋯ + Na_{N} c_{k−N}).

The recurrence follows from this. We can use this recurrence to iteratively calculate the elements [x^{n}]G(x)^{n}.

Example 16. We let G(x) = ∑_{n=0}^{∞} C_{n}x^{n} be the generating function of the Catalan numbers. We wish to calculate [x^{n}]G(x)^{n}. To this end, we let

c(n, k) = \begin{cases}1, & if n = 0; \\ \frac{1}{n} ∑_{j=1}^{n}(kj − j − n)C_{j}c(n − j, k), & otherwise. \end{cases}

Then [x^{n}]G(x)^{n} is given by c(n, n). In this case, we obtain the sequence \binom{3n−1}{2n} which begins

1, 1, 5, 28, 165, 1001, 6188, 38760, 245157, 1562275 ….

This is essentially \underline{A025174}. The numbers c(n, n) are the central coefficients of the Riordan array (1, xc(x)).

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5 & 5 & 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 14 & 14 & 9 & 4 & 1 & 0 & 0 & 0 \\ 0 & 42 & 42 & 28 & 14 & 5 & 1 & 0 & 0 \\ 0 & 132 & 132 & 90 & 48 & 20 & 6 & 1 & 0 \\ 0 & 429 & 429 & 297 & 165 & 75 & 27 & 7 & 1 \end{matrix} ) .

10 Some numerical results

Example 17. The Bernoulli numbers B_{n} can be defined by

B_{n} = ∑_{k=0}^{n} \frac{1}{k + 1} ∑_{i=0}^{n}(−1)^{i}\binom{k}{i}i^{n}.

They begin

1, −\frac{1}{2}, \frac{1}{6}, 0, −\frac{1}{30}, 0, \frac{1}{42}, 0, −\frac{1}{30}, 0, ….

Letting g(x) = ∑_{k=0}^{n} B_{k}x^{k} and proceeding as above will allow us to find the first n + 1 terms of the central antecedent of the Bernoulli numbers. We can proceed as follows. For a given n ≥ 0, we

1. Set g(x) = ∑_{k=0}^{n} B_{k}x^{k}.

2. Form \frac{g(x)−1}{x} = ∑_{k=1}^{n} B_{k}x^{k}.

3. Carry out the integration ∫_{0}^{x} \frac{g(t)−1}{t} dt = ∑_{k=1}^{n} B_{k} \frac{x^{k+1}}{k}.

4. Evaluate xe^{∑_{k=1}^{n} B_{k} \frac{x^{k+1}}{k}} and revert.

For fixed n, we can carry out this reversion as follows. We form the Riordan array (1, f(x))

[11] where f(x) is the n-degree polynomial that approximates xe^{∑_{k=1}^{n} B_{k} \frac{x^{k+1}}{k}}. We invert this Riordan array and it follows that the elements of the second (k = 1) column of the inverse matrix are the Taylor series coefficients of the n-degree polynomial that approximates the reversion sought. Shifting this once (division by x) and taking the reciprocal then gives us the first n Taylor series coefficients of the antecedent power series, or equivalently, the first n terms of the central antecedent sequence of the Bernoulli numbers.

We find in this manner that the central antecedent sequence of the Bernoulli numbers begins

1, −\frac{1}{2}, −\frac{1}{24}, 0, \frac{3}{640}, 0, −\frac{1525}{580608}, 0, \frac{615881}{199065600}, 0, ….

Example 18. The harmonic numbers ∑_{k=1}^{n} \frac{1}{k} for k = 1, 2, … begin

1, \frac{3}{2}, \frac{11}{6}, \frac{25}{12}, \frac{137}{60}, \frac{49}{20}, \frac{363}{140}, \frac{761}{280}, ….

Proceeding as before, we find that the central antecedent sequence of the harmonic numbers begins

1, \frac{3}{2}, −\frac{5}{24}, \frac{7}{36}, −\frac{439}{1920}, \frac{1631}{5400}, −\frac{41483}{967680}, \frac{14977}{23520}, ….

11 Conclusion

We have shown that given a generating function g(x) where g(0) ≠ 0, we can associate with it a so-called “central antecedent” G(x) so that

[x^{n}]g(x) = [x^{n}]G(x)^{n}.

Examples have been given for common sequences. For certain integer sequences, the antecedent sequence is again an integer sequence. But this is not always the case, as is evidenced for instance by the Catalan numbers. An interesting problem that remains is to characterize those integer sequences whose central antecedents are also integer sequences.

12 Acknowledgments

The author would like to thank the anonymous reviewers for their suggestions, on using the diagonalization formula, and of using the Henrici example at the beginning of this note. It is interesting to note that Henrici [6] uses the Riordan arrays (1, f(x)) to prove the associativity of composition for composable power series. This is an early use of Riordan arrays before the term was “Riordan array” was introduced [11].

References

[1] P. Barry, Riordan Arrays: a Primer, Logic Press, 2017.

[2] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996), 329-–359.

[3] H. Finkel, The differential transformation method and Miller’s recurrence, preprint avail-

   able at https://arxiv.org/abs/1007.2178, 2010.

[4] I. M. Gessel, Lagrange inversion, preprint available at https://arxiv.org/abs/1609. 05988, 2016.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[6] P. Henrici, Applied and Computational Complex Analysis, Volume 1, John Wiley & Sons, 1988.

[7] P. Henrici, An algebraic proof of the Lagrange-Bürmann formula, J. Math. Anal. Appl. 8 (1964), 218–224.

[8] D. Merlini, R. Sprugnoli, and M. C. Verri, Lagrange inversion: when and how, Acta Appl. Math. 94 (2006), 233–249.

[9] D. Merlini, R. Sprugnoli, and M. C. Verri, The method of coefficients, Amer. Math. Monthly 114 (2007), 40–57.

[10] T. D. Noe, On the divisibility of generalized central trinomial coefficients, J. Integer Sequences 9 (2006), Article 06.2.7.

[11] L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

[12] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Published electronically at https://oeis.org/, 2020.

[13] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices Amer. Math. Soc. 50 (2003), 912–915.

[14] R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, 2001.

[15] D. Zeilberger, The J. C. P. Miller recurrence for exponentiating a polynomial, and its q-analog, J. Difference Equ. Appl. 1 (1995), 57–60.

2010 Mathematics Subject Classification: Primary 11Y55; Secondary 05A15, 11B65, 11B68. Keywords: central coefficient, generating function, Lagrange inversion, Catalan number, partition number, Bernoulli number, harmonic number, Lambert function.

(Concerned with sequences \underline{A000027}, \underline{A000041}, \underline{A000108}, \underline{A000203}, \underline{A000984}, \underline{A002426}, \underline{A005043}, \underline{A007317}, \underline{A025174}, and \underline{A214776}.)

Received June 23 2020; revised version received September 2 2020. Published in Journal of Integer Sequences, September 2 2020.

Return to Journal of Integer Sequences home page.