Woon’s Tree and Sums over Compositions

Christophe Vignat L.S.S., CentraleSupelec Université Paris Sud Orsay, 91192 France and Department of Mathematics Tulane University New Orleans, LA 70118 USA

              christophe.vignat@u-psud.fr

Tanay Wakhare University of Maryland College Park, MD 20742 USA

                  twakhare@gmail.com

Abstract

This article studies sums over all compositions of an integer. We derive a generating function for this quantity, and apply it to several special functions, including various generalized Bernoulli numbers. We connect composition sums with a recursive tree introduced by Woon and extended by Fuchs under the name general PI tree, in which an output sequence is associated with an input sequence by summing over each row of the tree built from this input sequence. Our link with the notion of compositions allows to introduce a modification of Fuchs’ tree that takes into account nonlinear transforms of the generating function of the input sequence. We also introduce the notion of generalized sums over compositions, where we look at composition sums over each part of a composition.

1 Introduction

Sums over compositions are an object of study in their own right, and there is a vast literature considering sums over compositions or enumeration of restricted compositions. A composition of an integer number n is any sequence of integers n_{i} ≥ 1, called parts of n, such that

n = n_{1} + ⋯ + n_{m}.

There are 2 compositions of 2 :

2, 1 + 1,

4 compositions of 3 :

3, 2 + 1, 1 + 2, 1 + 1 + 1,

and more generally 2^{n−1} compositions of n. These compositions can be represented as follows:

2 : ●●, ●|●,
3 : ●●●, ●●|●, ●|●●, ●|●|●,

and so on. We also introduce the following notation: let C (n) denote the set of all compositions of n; for an element π = {n_{1}, …, n_{m}} ∈ C (n), let m = |π| denote its length, i.e the number of its parts. For a sequence (g_{n}), we also use the multi-index notation

g_{π} = g_{n_{1}} … g_{n_{m}}.

We can now state our main result, a generating function for sums over compositions:

Theorem 1. [13, Theorem 3, Remark 5] Let g(z) = ∑_{n≥1} g_{n}z^{n} and f(z) = ∑_{n≥0} f_{n}z^{n}. We then have the generating function identity

f(g(z)) = f_{0} + ∑_{n≥1} z^{n} ∑_{π∈C_{n}} f_{|π|}g_{π}.  (1)

This general result unites many previous results spread across the literature, because the composite generating function f(g(z)) often has a simple closed form. It was originally noted by Vella [13], who used it to derive explicit expressions for the Bernoulli and Euler numbers as sums over compositions. The innovative aspect of the current paper is the link between composition sums and Woon’s and Fuchs’ trees, which provide graphical visualization aids, as described below.

In Section 2, we introduce Woon’s and Fuchs’ tree, and in Section 3, we connect them to compositions for the first time. In Section 4, we introduce our main results, and use them to derive a variety of closed form expressions for sums over compositions. In Section 5, we introduce a new notation for generalized composition sums, and explore some basic identities for them. Throughout, we apply our results to special functions and generalized Bernoulli numbers, which allows us to derive expressions for them as sums over compositions.

2 Background

Woon’s tree, as introduced by Woon [15], is the following construction

\frac{1}{2!} ; −\frac{1}{3!} ; \frac{1}{4!} ; −\frac{1}{5!} ; \frac{1}{2!4!!} ; −\frac{1}{2!3!} ; \frac{1}{3!3!} ; −\frac{1}{2!2!3!} ; \frac{1}{2!2!} ; −\frac{1}{3!2!} ; \frac{1}{4!2!} ; −\frac{1}{2!3!2!} ; \frac{1}{2!2!2!} ; −\frac{1}{3!2!2!} ; \frac{1}{2!2!2!2!}

with the rule

±\frac{1}{a_{1}!...a_{k}!} ∓\frac{1}{(a_{1}+1)!...a_{k}!} ±\frac{1}{2!a_{1}!...a_{k}!}

Woon proved, using the Euler-MacLaurin summation formula, that the successive row sums

\frac{1}{2!} = \frac{1}{2}, \frac{1}{2!2!} − \frac{1}{3!} = \frac{1}{4} − \frac{1}{6} = \frac{1}{12}, \frac{1}{4!} − \frac{1}{2!3!} − \frac{1}{3!2!} + \frac{1}{2!2!2!} = 0,
\frac{1}{2!2!2!2!} − \frac{3}{2!2!3!} + \frac{2}{2!4!} + \frac{1}{3!3!} − \frac{1}{5!} = −\frac{1}{720}, …

coincide with the sequence ((−1)^{n} \frac{B_{n}}{n!} )_{n≥1}, where the Bernoulli numbers are defined by the generating function

∑_{n≥0} \frac{B_{n}}{n!} z^{n} = \frac{z}{e^{z} − 1}.

Later on, Fuchs [4] considered a more general construction, the general PI tree. This associates, with the sequence of real numbers (g_{n}), which we call the input sequence, the tree

\begin{matrix}g_{1} \\ g_{1}g_{1} \\ g_{1}g_{1}g_{1} \\ g_{1}g_{1}g_{1}g_{1} \\ g_{2}g_{1}g_{1} \\ g_{2}g_{1} \\ g_{1}g_{2}g_{1} \\ g_{3}g_{1} \\ g_{2} \\ g_{1}g_{2} \\ g_{1}g_{1}g_{2} \\ g_{2}g_{2} \\ g_{3} \\ g_{1}g_{3} \\ g_{4} \end{matrix}

built using the two operators P (for “put a 1”) and I (for “increase”) as follows

g_{i_{1}}g_{i_{2}} … g_{i_{k}} g_{1}g_{i_{1}}g_{i_{2}} … g_{i_{k}} g_{i_{1}+1}g_{i_{2}} … g_{i_{k}} P I

The row sums of the tree generate what will be called the output sequence (x_{n}). Note that although the g_{n} are real numbers, they should be considered as noncommuting variables in the process of construction of the tree. Moreover, Woon’s tree corresponds to a PI tree with the particular choice

g_{n} = \frac{−1}{(n + 1)!}.

Fuchs proved that if x_{0} = 1, then the sequence of row sums (x_{n})_{n≥1} of the general PI tree is related to the sequence of its entries (g_{n})_{n≥1} by the convolution

x_{n} = ∑_{j=1}^{n} g_{j}x_{n−j} = g_{n} + g_{n−1}x_{1} + ⋯ + g_{1}x_{n−1}.  (2)

This result translates in terms of generating functions as follows — see the result by Fuchs [4]: if (g_{n}) and (x_{n}) are the input and output sequences of Fuchs’ tree, then their generating functions

x (z) = ∑_{n≥1} x_{n}z^{n}, g (z) = ∑_{n≥1} g_{n}z^{n}

are related by

x (z) = \frac{g (z)}{1 − g (z)}  (3)

and

g (z) = \frac{x (z)}{1 + x (z)}.  (4)

This convolution between the sequences (x_{n}) and (g_{n}) and the corresponding functional equations are the key interests of our paper; they imply nontrivial inter-relations for sequences which can be generated by Fuchs’ tree.

Example 2. In the case of Bernoulli numbers, the generating function of the input sequence is

g (z) = ∑_{k≥1} \frac{−1}{(k + 1)!}z^{k} = −\frac{1}{z} (e^{z} − 1 − z) = 1 − \frac{e^{z} − 1}{z},

so that the generating function of the row sums sequence is

x (z) = \frac{1 − \frac{e^{z}−1}{z}}{\frac{e^{z}−1}{z}} = \frac{z}{e^{z} − 1} − 1 = ∑_{n≥1} \frac{B_{n}}{n!} z^{n}.

The recursive identity (2) is the well-known identity for Bernoulli numbers [10, 24.5.3]

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

Example 3. The Bernoulli polynomials B_{n} (x) are defined by the generating function

∑_{n≥0} \frac{B_{n} (x)}{n!}z^{n} = \frac{ze^{zx}}{e^{z} − 1}.

We deduce that the tree with polynomial entries

g_{n} = \frac{(−1)^{n+1}}{(n + 1)!} [x^{n+1} − (x − 1)^{n+1}]

has row sums that coincide with the Bernoulli polynomials:

x_{n} = \frac{B_{n} (x)}{n!}.

This gives a decomposition of Bernoulli polynomials as a sum of elementary polynomials; for example

B_{1} (x) = \frac{1}{2} [x^{2} − (x − 1)^{2}] ,

\frac{B_{2} (x)}{2!} = \frac{1}{2} [x^{2} − (x − 1)^{2}] − \frac{1}{6} [x^{3} − (x − 1)^{3}] .

The general expression for \frac{B_{n}(x)}{n!} is given in Theorem 16 below.

Example 4. Higher-order Bernoulli numbers, also called Nörlund polynomials, are defined for an integer parameter p by the generating function

∑_{n≥0} \frac{B_{n}^{(p)}}{n!} z^{n} = (\frac{z}{e^{z} − 1})^{p} .  (5)

The output sequence

x_{n} = \frac{B_{n}^{(p)}}{n!}

corresponds to the input sequence

g_{n} = −\frac{p!}{(p + n)!} \{ \begin{matrix}n + p \\ p \end{matrix} \} ,

where \{ \begin{matrix}n \\ p \end{matrix} \} is the Stirling number of the second kind.

Example 5. The hypergeometric Bernoulli numbers, as introduced by Howard [7], are defined, for a > 0 and b > 0, by the generating function

∑_{n≥0} \frac{B_{n}^{(a,b)}}{n!} z^{n} = \frac{1}{_{1}F_{1} ( \begin{matrix}a \\ a + b \end{matrix} ; z)},

where _{1}F_{1} is the hypergeometric function

1F_{1} ( \begin{matrix}a \\ c \end{matrix} ; z) = ∑_{n≥0} \begin{matrix}(a) & n \\ (c) & n \end{matrix} \frac{z^{n}}{n!} ,

with the notation (a)_{n} for the Pochhammer symbol

(a)_{n} = \frac{Γ (a + n)}{Γ (a)}.

The output sequence

x_{n} = \frac{B_{n}^{(a,b)}}{n!}

corresponds to the input sequence

g_{n} = −\frac{1}{n!} \begin{matrix}(a) & n \\ (a + b) & n \end{matrix} .

3 Connection to compositions

3.1 Definitions

In the examples studied so far, we were able to compute a few row sums of Fuchs’ tree, but we still need a general and non-recursive formula that gives the row sum sequence (x_{n}) explicitly as a function of the input sequence (g_{n}). This implies a better description of the row generating process of Woon’s tree, which requires the notion of compositions.

The representation

\begin{matrix}● \\ ●|● \\ ●|●|● \\ ●●|● \\ ● & ● \\ ●|●● \\ ● & ● & ● \end{matrix}

suggests a natural bijection between the generation process of the next row in Woon’s tree and the generation process of the compositions of the integer n + 1 in terms of those of n. We restate Fuchs’ result [4] in terms of compositions, and then apply this result to derive several new identities for Catalan numbers and Hermite polynomials.

3.2 Fuchs’ result

We can now restate Fuchs’ main result (2) as follows

Theorem 6. The sequence of row sums (x_{n}) in Woon’s tree can be computed from its sequence of entries (g_{n}) as the sum over compositions

x_{n} = ∑_{π∈C(n)} g_{π} = ∑_{p=1}^{n} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥1}} g_{k_{1}} … g_{k_{p}}.  (6)

This sum over compositions can also be expressed as the weighted sum over convolutions

x_{n} = ∑_{p=1}^{n} \binom{n + 1}{p + 1} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥0}} g_{k_{1}} … g_{k_{p}}.  (7)

Moreover, these relations can be inverted by exchanging x_{n} with −g_{n} : the input sequence (g_{n}) in Woon’s tree can be recovered from its row sum sequence (x_{n}) as the sum over compositions

g_{n} = ∑_{π∈C(n)} (−1)^{π+1} x_{π} = ∑_{p=1}^{n} (−1)^{p+1} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥1}} x_{k_{1}} … x_{k_{p}}  (8)

or as the weighted sum over convolutions

x_{n} = ∑_{p=1}^{n} (−1)^{p+1} \binom{n + 1}{p + 1} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥0}} x_{k_{1}} … x_{k_{p}}.  (9)

Proof. Let g_{n} denote = −\frac{w_{n}}{n!} so that

x_{n} = ∑_{m=1}^{n} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} g_{k_{1}} … g_{k_{m}} = ∑_{m=1}^{n} (−1)^{m} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} \frac{w_{k_{1}}}{k_{1}!} … \frac{w_{k_{m}}}{k_{m}!}

= ∑_{m=1}^{n} \frac{(−1)^{m}}{n!} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} \binom{n}{k_{1}, …, k_{m}}w_{k_{1}} … w_{k_{m}}.

Let us denote the incomplete sum

S̃_{m,n} = ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} \binom{n}{k_{1}, …, k_{m}}w_{k_{1}} … w_{k_{m}}

and its complete version

S_{m,n} = ∑_{k_{1}+···+k_{m}=n_{k_{i}≥0}} \binom{n}{k_{1}, …, k_{m}}w_{k_{1}} … w_{k_{m}},

so that

x_{n} = ∑_{m=1}^{n} \frac{(−1)^{m}}{n!} S̃_{m,n}

and both variables S_{m,n} and S̃_{m,n} are related by

S̃_{m,n} = ∑_{p=1}^{m} (−1)^{m−p} \binom{m}{p}S_{p,n},

an identity that can be proved, for example, by induction on m. Following the same steps as in the Bernoulli case above, we deduce that

x_{n} = ∑_{m=1}^{n} \frac{(−1)^{m}}{n!} ∑_{p=1}^{m} (−1)^{m−p} \binom{m}{p}S_{p,n} = ∑_{p=1}^{n} \frac{(−1)^{p}}{n!} S_{p,n} ∑_{m=p}^{n} \binom{m}{p}.

Moreover,

S_{p,n} = ∑_{k_{1}+···+k_{p}=n_{k_{i}≥0}} \binom{n}{k_{1}, …, k_{p}}w_{k_{1}} … w_{k_{p}} = (−1)^{p} n! ∑_{k_{1}+···+k_{p}=n_{k_{i}≥0}} g_{k_{1}} … g_{k_{p}},

and the proof of the first part follows. The inversion of these relations is deduced from the identity (4).

The result of Theorem 6 has been rediscovered many times in relation to sums over compositions. For examples of identities derived from this result, see the articles by Sills [11], Hoggatt et al. [6] and Gessel et al. [5]. Selecting various g_{k} = 1 for k in some set of indices J, and g_{i} = 0 otherwise, also gives the generating function for the number of compositions into parts from this set J. For example, we can let g_{2n} = 0 and g_{2n+1} = 1 to find a formula for the number of compositions into odd parts.

3.3 Invariant sequences

In this section, we look for sequences that are invariant by Fuchs’ tree.

3.3.1 Catalan numbers

The Catalan numbers (\underline{A000108} in the On-Line Encyclopedia of Integer Sequences) are defined by the generating function

∑_{n≥0} C_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} .

They are invariants of Woon’s tree in the following sense.

Theorem 7. If

g_{n} = \begin{cases}C_{n−1}, & if n ≥ 1; \\ 1, & if n = 0, \end{cases}

is the input sequence of Woon’s tree, then the row sums are

x_{n} = C_{n}, n ≥ 0.

As a consequence, the Catalan numbers satisfy the sum over compositions identities

C_{n} = ∑_{m=1}^{n} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} C_{k_{1}−1} … C_{k_{m}−1}  (10)

and

C_{n−1} = ∑_{m=1}^{n} (−1)^{m+1} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1}} C_{k_{1}} … C_{k_{m}}.  (11)

Remark 8. Identity (10) can be considered as a generalization of the classic convolution identity for Catalan numbers [10, Entry 26.5.3]

C_{n} = ∑_{k=0}^{n−1} C_{k}C_{n−1−k}.

Remark 9. Vella [14] previously proved identity (10) in 2013 through the result [13, Theorem 3 Remark 5] without reference to Woon’s tree. He also provided a combinatorial proof based on Dyck words which does not rely on generating functions. This identity has also been the subject of several talks by Vella.

Proof. From the generating function of the input sequence

g (z) = ∑_{n≥1} g_{n}z^{n} = ∑_{n≥1} C_{n−1}z^{n} = z \frac{1 − \sqrt{1 − 4z}}{2z} = \frac{1 − \sqrt{1 − 4z}}{2} ,

we deduce the generating function of the row sums

X (z) = \frac{g (z)}{1 − g (z)} = \frac{1 − \sqrt{1 − 4z}}{1 + \sqrt{1 − 4z}} = −1 + \frac{1 − \sqrt{1 − 4z}}{2z} = ∑_{n≥1} C_{n}z^{n},

which proves the result. Both identities for Catalan numbers (10) and (11) are a consequence of identities (6) and (8).

3.3.2 Hermite polynomials

Another invariant sequence of Woon’s tree is the sequence of Hermite polynomials (H_{n} (x)) defined by the generating function

∑_{n≥0} \frac{H_{n} (x)}{n!}z^{n} = e^{2xz−z^{2}}.

It can be checked that if the entries of Woon’s tree are chosen as

g_{n} = −ı^{n} \frac{H_{n} (ıx)}{n!},

then the sequence of row sums is equal to

x_{n} = \frac{H_{n} (x)}{n!}.

4 A nonlinear generalization

We are able to generalize these results to sums over compositions with weights, which corresponds to a further generalization of Fuchs’ tree. Because Fuchs’ tree graphically represents sums over compositions, we can represent the generating function f(g(z)) as the convolution of two trees:

\begin{matrix}g_{1} \\ g_{1}g_{1} \\ g_{1}g_{1}g_{1} \\ g_{2}g_{1} \\ g_{2} \\ g_{1}g_{2} \\ g_{3} \end{matrix}  ∗  \begin{matrix}f_{1} \\ f_{2} \\ f_{3} \\ f_{2} \\ f_{1} \\ f_{2} \\ f_{1} \end{matrix}  =  \begin{matrix}f_{1}g_{1} \\ f_{2}g_{1}g_{1} \\ f_{3}g_{1}g_{1}g_{1} \\ f_{2}g_{2}g_{1} \\ f_{1}g_{2} \\ f_{2}g_{1}g_{2} \\ f_{1}g_{3} \end{matrix}

The analytic description of this operation is as follows.

Theorem 10. [13, Theorem 3, Remark 5] Let g(z) = ∑_{n≥1} g_{n}z^{n} and f(z) = ∑_{n≥0} f_{n}z^{n}. Then we have the generating function identity

f(g(z)) = f_{0} + ∑_{n≥1} z^{n} ∑_{π∈C_{n}} f_{|π|}g_{π}.  (12)

Proof. We note that the case f_{0} = 0 and f_{n} = 1, n ≥ 1, corresponds to Theorem 6. Then f(z) = \frac{z}{1−z}, leading to the observed relationship between g(z) and x(z). In terms of trees, the sum ∑_{π∈C_{n}} f_{|π|}g_{π} corresponds to a row sum, with additional weights depending on how many different parts are in each composition of n. With the notation T_{n}(f; a) = \frac{f^{(n)}(a)}{n!}, we have the following result of Vella [13], based off the classical Faá di Bruno formula:

T_{n}(f ∘ g; a) = ∑_{π∈C_{n}} T_{|π|}(f; g(a)) ∏_{i=1}^{n}[T_{i}(g; a)]^{π_{i}}.  (13)

We let a = 0, so that g(a) = 0. Then letting T_{n}(f; 0) = f_{n} and T_{n}(g; 0) = g_{n} yields the result.

Remark 11. Eger [2] explored the case f_{k} = 1 and f_{n} = 0 for n ≠ k. He used this to define “extended binomial coefficients”, which constitute a special case of our results.

Remark 12. One consequence of identity (12) is as follows: let (μ_{n}) denote the moment sequence and (κ_{n}) the cumulant sequence of a random variable Z: the moments are the expectations μ_{n} = 𝔼Z^{n} and the cumulants are the Taylor coefficients of the logarithm of the moment generating function ∑_{n≥0} \frac{μ_{n}}{n!} z^{n}. Choosing

g_{1} (z) = ∑_{n=1}^{∞} μ_{n} \frac{z^{n}}{n!} , f (z) = log (1 + z) ,

so that

f (g_{1} (z)) = ∑_{n=1}^{∞} κ_{n} \frac{z^{n}}{n!} ,

we deduce the identity between moments and cumulants

∑_{π∈C(n)} \frac{(−1)^{|π|}}{|π|} \frac{μ_{π}}{π!} = \frac{κ_{n}}{n!} .

Let g_{2}(z) = ∑_{n=1}^{∞} κ_{n} \frac{z^{n}}{n!} be the cumulant generating function and f(z) = e^{z} − 1, so that f(g_{2}(z)) is the moment generating function. This gives the other identity between moments and cumulants

∑_{π∈C(n)} \frac{1}{|π|!} \frac{κ_{π}}{π!} = \frac{μ_{n}}{n!} .

This allows us to express moments and cumulants in terms of sums over compositions of each other. Note that by definition, if π = k_{1} … k_{p} then (−1)^{π} = (−1)^{k_{1}+···+k_{p}}, μ_{π} = μ_{k_{1}} … μ_{k_{p}}, κ_{π} = κ_{k_{1}} … κ_{k_{p}}, π! = k_{1}! … k_{p}! and |π|! = p!.

Theorem 13. We have the following identity for sums over compositions:

∑_{π∈C_{n}} f_{|π|}g_{π} = ∑_{p=1}^{n} f_{p} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥1}} g_{k_{1}} … g_{k_{p}} = ∑_{p=1}^{n} (∑_{m=p}^{n} f_{m}\binom{m}{p}) ∑_{k_{1}+···+k_{p}=n} g_{k_{1}} … g_{k_{p}}. (14)

Proof. The proof is identical to that given in Theorem 6.

We can also, for the first time, find a general formula for sums over all parts of all compositions of n. This corresponds to an “additive” Woon tree where the creation operator “I” adds g_{1} instead of multiplying by it.

Theorem 14. Let g(z) = ∑_{n≥1} g_{n}z^{n} and f(z) = ∑_{n≥0} f_{n}z^{n}. Then we have the generating function identity

f′ (\frac{z}{1 − z} ) g(z) = ∑_{n≥1} z^{n} ∑_{π∈C_{n}} f_{|π|} ∑_{k_{i}∈π} g_{k_{i}}.  (15)

Proof. We begin with g(z) = ∑_{n≥1} g_{n}z^{n} and transform it to the bivariate generating function G(z, λ) = ∑_{n≥1} λ^{g_{n}}z^{n}. We then take a partial derivative with respect to λ and evaluate at λ = 1 to obtain

\frac{∂}{∂λ}f(G(z, λ))|_{λ=1} = \frac{∂}{∂λ} ∑_{n≥1} z^{n} ∑_{π∈C_{n}} f_{|π|}λ^{∑_{k_{i}∈π} g_{k_{i}}} |_{λ=1}.  (16)

Noting that G(z, 1) = \frac{z}{1−z} and \frac{∂}{∂λ}G(z, λ)|_{λ=1} = g(z) yields the result.

Remark 15. As a consequence of this result, choosing f (z) = \frac{z}{1−z}, we deduce the generating function of the sequence

( ∑_{π∈C_{n}} ∑_{k_{i}∈π} g_{k_{i}})_{n≥1}

as

∑_{n≥1} z^{n} ∑_{π∈C_{n}} ∑_{k_{i}∈π} g_{k_{i}} = (\frac{1 − z}{1 − 2z} )^{2} g (z) .

Generating functions for other sequences related to compositions, such as the total number of summands in all the compositions of n, can be found for example in the paper by Merlini et al. [9].

4.1 Back to the Bernoulli numbers

Going back to Example 2 and Equation (7), we deduce the expression for the Bernoulli numbers

\frac{B_{n}}{n!} = ∑_{π∈C(n)} \frac{(−1)^{|π|}}{(π + 1)!} = ∑_{p=1}^{n} \binom{n + 1}{p + 1} (−1)^{p} ∑_{k_{1}+···+k_{p}=n} \frac{1}{(k_{1} + 1)! … (k_{p} + 1)!},

with the notation

(π + 1)! = ∏_{i} (k_{i} + 1)!.

From the multinomial identity, we know that, in terms of Stirling numbers of the second kind,

∑_{k_{1}+···+k_{p}=n} \binom{n}{k_{1}, …, k_{p}} \frac{1}{(k_{1} + 1) … (k_{p} + 1)} = \frac{n!p!}{(n + p)!} \{ \begin{matrix}n + p \\ p \end{matrix} \} .  (17)

We deduce the expression for the Bernoulli numbers

B_{n} = ∑_{p=1}^{n} (−1)^{p} \begin{matrix}\{ & \begin{matrix}n + p \\ p \end{matrix} & \} \\ ( & {n+p \atop p} & ) \end{matrix}\binom{n + 1}{p + 1}, n ≥ 1.

Another extremely similar expression for the Bernoulli numbers can be obtained by choosing

g (z) = e^{z} − 1 = ∑_{n≥1} \frac{z^{n}}{n!}

and

f (z) = \frac{log (1 + z)}{z} = ∑_{n≥0} \frac{(−1)^{n}}{n + 1} z^{n},

giving

\frac{B_{n}}{n!} = ∑_{π∈C(n)} \frac{(−1)^{|π|}}{|π| + 1} \frac{1}{π!}  (18)

= ∑_{p=1}^{n} \frac{(−1)^{p}}{p + 1} ∑_{k_{1}+···+k_{p}=n_{k_{i}≥1}} \frac{1}{k_{1}! … k_{p}!} = ∑_{p=1}^{n} \frac{(−1)^{p}}{p + 1} p! \{ \begin{matrix}n \\ p \end{matrix} \} ,  (19)

an identity that can be found under a slightly different form as Entry 24.6.9 in the NIST Digital Library [10], and that was previously obtained using the same method by Vella [13, Theorem 11].

We note that we have obtained two distinct but very similar representations of the Bernoulli numbers as sums over compositions:

\frac{B_{n}}{n!} = ∑_{π∈C(n)} \frac{(−1)^{|π|}}{(π + 1)!} = ∑_{π∈C(n)} \frac{(−1)^{|π|}}{|π| + 1} \frac{1}{π!}.

We also notice that Vella [13] obtained other expressions of the Bernoulli and Euler numbers as sums over compositions.

4.2 Back to Bernoulli polynomials

We can now provide a general formula for the Bernoulli polynomials as follows:

Theorem 16. The Bernoulli polynomials can be expanded as

B_{n} (x) = ∑_{p=1}^{n} \binom{n + 1}{p + 1} (−1)^{p} B_{n}^{(−p)} (−px) , n ≥ 1,

where B_{n}^{(p)} (x) is the higher-order Bernoulli polynomial with parameter p, defined by the generating function

∑_{n≥0} \frac{B_{n}^{(p)} (x)}{n!}z^{n} = e^{zx} (\frac{z}{e^{z} − 1})^{p} .  (20)

Proof. Using

g_{n} = \frac{(−1)^{n+1}}{(n + 1)!} (x^{n+1} − (x − 1)^{n+1}) = \frac{(−1)^{n+1}}{n!} ∫_{0}^{1} (x + u − 1)^{n} du,

we deduce

x_{n} = \frac{B_{n} (x)}{n!} = ∑_{p=1}^{n} \binom{n + 1}{p + 1} ∑_{k_{1}+···+k_{p}=n} g_{k_{1}} … g_{k_{p}},

with

∑_{k_{1}+···+k_{p}=n} g_{k_{1}} … g_{k_{p}} = \frac{(−1)^{n+p}}{n!} ∑_{k_{1}+···+k_{p}=n} \binom{n}{k_{1}, …, k_{p}} ∫_{0}^{1} … ∫_{0}^{1} ∏_{i=1}^{p} (x + u_{i} − 1)^{k_{i}} du_{1} … du_{p}

= \frac{(−1)^{n+p}}{n!} ∫_{0}^{1} ⋯ ∫_{0}^{1} (px − p + u_{1} + ⋯ + u_{p})^{n} du_{1} … du_{p}.

This sequence has generating function

∑_{n≥0} (\frac{(−1)^{n+p}}{n!} ∫_{0}^{1} ⋯ ∫_{0}^{1} (px − p + u_{1} + ⋯ + u_{p})^{n} du_{1} … du_{p}) z^{n} = (−1)^{p} e^{−z(px−p)} (\frac{1 − e^{−z}}{z} )^{p}

= (−1)^{p} e^{−zpx} (\frac{e^{z} − 1}{z})^{p};

comparing to the generating function of the higher-order Bernoulli polynomials (20), we deduce

∑_{k_{1}+···+k_{p}=n} g_{k_{1}} … g_{k_{p}} = \frac{(−1)^{p}}{n!} B_{n}^{(−p)} (−px)

and

B_{n} (x) = ∑_{p=1}^{n} \binom{n + 1}{p + 1} (−1)^{p} B_{n}^{(−p)} (−px) ,

which is the desired result.

This result was proved by Vella in 2006 [14], using a theorem from the same author [13, Theorem 3 Remark 5].

4.3 Back to higher-order Bernoulli polynomials

We apply the result of Theorem 10 to higher-order Bernoulli numbers as follows: starting from

g_{n} = −\frac{1}{(n + 1)!}, g (z) = 1 − \frac{e^{z} − 1}{z},

the desired generating function is

f (g (z)) = (\frac{z}{e^{z} − 1})^{q} − 1 = (\frac{1}{1 − g (z)})^{q} − 1,

so that

f (z) = (\frac{1}{1 − z} )^{p} − 1 = ∑_{k≥1} \binom{k + p − 1}{p − 1}z^{k}.

Applying formula (14), we deduce

\frac{B_{n}^{(q)}}{n!} = ∑_{p=1}^{n} (∑_{m=p}^{n} \binom{m}{p}\binom{m + q − 1}{q − 1}) ∑_{k_{1}+···+k_{p}=n} \frac{(−1)^{p}}{(k_{1} + 1)! … (k_{p} + 1)!}.

The inner sum is easily computed as

∑_{m=p}^{n} \binom{m}{p}\binom{m + q − 1}{q − 1} = \frac{n − p + 1}{p + q}\binom{n + 1}{p}\binom{n + q}{q − 1},

whereas the last sum is, by (17), equal to

∑_{k_{1}+···+k_{p}=n} \frac{(−1)^{p}}{(k_{1} + 1)! … (k_{p} + 1)!} = (−1)^{p} \frac{p!}{(n + p)!} \{ \begin{matrix}n + p \\ p \end{matrix} \} ,

so that

B_{n}^{(q)} = \binom{n + q}{q − 1} ∑_{p=1}^{n} (−1)^{p} \begin{matrix}\{ & \begin{matrix}n + p \\ p \end{matrix} & \} \\ ( & {n+p \atop p} & ) \end{matrix} (\frac{n + 1}{p + q}) \binom{n}{p}

= ∑_{p=1}^{n} (−1)^{p} \begin{matrix}\{ & \begin{matrix}n + p \\ p \end{matrix} & \} \\ ( & {n+p \atop p} & ) \end{matrix}\binom{n + q}{n − k}\binom{q + k − 1}{k}.

This identity can be found in the article by Srivastava et al. [12, Eq. 15].

4.4 Compositions with restricted summands

When the input sequence (g_{n}) has a simple structure, more details can be obtained about the row-sum sequence (x_{n}). We emphasize that the material in this section, save the connection to Woon’s tree, was discovered by Vella [14] in 2006 using a result from the same author [13, Theorem 3 Remark 5] but was not previously published. Vella has, however, extensively lectured on the topic. We start with the example of Fibonacci numbers, by explicitly constructing Woon’s tree for the Fibonacci case

x_{n} = F_{n},

with

F_{0} = 1, F_{1} = 1, F_{2} = 2, F_{3} = 3, F_{4} = 5, F_{5} = 8, …

Since the Fibonacci numbers satisfy the recurrence

F_{n} = F_{n−1} + F_{n−2}, n ≥ 2,

we deduce from (17) that the sequence of entries of the tree satisfies

g_{k} = \begin{cases}1, & if k = 1, 2; \\ 0, & otherwise. \end{cases}

The first rows of the corresponding Woon’s tree are as follows.

1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 We deduce the expression for the Fibonacci numbers as

F_{n} = C_{n}^{{1,2}} = # {(k_{1}, …, k_{m}) |k_{1} + ⋯ + k_{m} = n, k_{i} = 1, 2} ,

the number of compositions of n with parts equal to 1 or 2. This result that can be found in Flajolet’s book [3, p. 42] and Alladi’s article [1]. Moreover, we recover from this representation the generating function for Fibonacci numbers

\frac{z + z^{2}}{1 − z − z^{2}} = ∑_{n≥1} F_{n}z^{n}.

These results can be generalized remarking that we have a correspondence between linear recurrences and compositions into restricted parts. For a given set of integers J, we adopt the notation

C_{n}^{{J}} = # {(k_{1}, …, k_{m}) |k_{1} + ⋯ + k_{m} = n, k_{i} ∈ J}

from Flajolet’s book [3, p. 42] to denote the number of compositions of n with parts in the set J. Theorem 17. Let J be a finite set of positive indices and consider the linear recurrence x_{n} = ∑_{j∈J} x_{n−j}. Then we have the dual identities

x_{n} = C_{n}^{{J}}  (21)

and

∑_{n≥1} x_{n}z^{n} = \frac{∑_{j∈J} z^{j}}{1 − ∑_{j∈J} z^{j}} .  (22)

Furthermore, the corresponding Woon tree has input sequence

g_{k} = \begin{cases}1 & if k ∈ J; \\ 0 & otherwise. \end{cases}  (23)

Proof. We begin with the recurrence (2), x_{n} = ∑_{j=1}^{n} g_{j}x_{n−j}, where x_{n} corresponds to the n−th row sum of Woon’s tree. Since x_{n} = ∑_{j∈J} x_{n−j}, the set J consists of the indices i such that g_{i} = 1. We also have that g_{i} = 0 everywhere else. This sequence then satisfies the conditions to be considered a generalized Woon tree, so we have the realization (23). We can then apply the transform x(z) = \frac{g(z)}{1−g(z)}, which yields (22), since g(z) = ∑_{n≥1} g_{n}z^{n} = ∑_{j∈J} z^{j}. Finally, we can apply (14) with f_{0} = 0 and f_{n} = 1 otherwise, to yield

\frac{g(z)}{1 − g(z)} = ∑_{n≥1} z^{n} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1, m≥1}} g_{k_{1}} … g_{k_{m}} = ∑_{n≥1} z^{n} ∑_{k_{1}+···+k_{m}=n_{k_{i}≥1, k_{i}∈J, m≥1}} 1 = ∑_{n≥1} C_{n}^{\{J\}}z^{n}.

Comparing coefficients yields (21).

A direction for future research is to study the asymptotics of x_{n} = C_{n}^{{J}}. The asymptotics of x_{n} = ∑ g_{i}x_{n−i} are complicated, but we have a much easier problem in the case where the coefficients {g_{i}} are either zero or one. Finding the asymptotics of x_{n} = ∑ g_{i}x_{n−i} then reduces to studying the roots of a special characteristic polynomial.

4.5 Sum of digits

For a given n, the set of 2^{n−1} integers {|π|}_{π∈C(n)} coincides with the set {1 + s_{2} (k)}_{0≤k≤2^{n−1}−1} , where s_{2} (k) is the number of 1′s in the binary expansion of k.

For example, for n = 3,

{|π|}_{π∈C(3)} = {1, 2, 2, 3}

while

s_{2} (0) = 0, s_{2} (1) = 1, s_{2} (2) = 1, s_{2} (3) = 2.

This remark, together with Theorem 13, can be used to derive some interesting finite sums that involve the sequence (s_{2} (k)). For example, the choice

f (z) = log (1 + z) , g (z) = \frac{z}{1 − z}

gives

f (g (z)) = − log (1 − z) ,

so that

x_{n} = \frac{1}{n} = ∑_{k=0}^{2^{n−1}−1} \frac{(−1)^{s_{2}(k)}}{s_{2} (k) + 1}, n ≥ 1.

This extends naturally as follows:

Theorem 18. For f (z) = ∑_{k≥1} f_{k}z^{k}, we have

∑_{k=0}^{2^{n−1}−1} f_{s_{2}(k)+1} = [z^{n}] f (\frac{z}{1 − z} ) = ∑_{k=1}^{n} f_{k}\binom{n − 1}{n − k}.

This formula simply expresses the fact that, for 0 ≤ k ≤ 2^{n−1} − 1, the sequence (s_{2} (k)) takes on the value zero \binom{n−1}{1} times, the value one \binom{n−2}{2} times, and so on.

5 A general formula for composition of functions

We conclude this study with a general formula for composition of functions. Introduce the notation

π ⊧ n

for π ∈ C (n). This mirrors the notation λ ⊢ n, which states that λ is a partition of n. From Theorem 10, we have the formula

(f ∘ g)_{n} = ∑_{π⊧n} f_{|π|}g_{π}.

Now we look at

(f ∘ (g ∘ h))_{n} = ∑_{π⊧n} f_{|π|} (g ∘ h)_{π} ,

where

(g ∘ h)_{π} = (g ∘ h)_{π_{1}} … (g ∘ h)_{π_{p}}

= ( ∑_{μ_{1}⊧π_{1}} g_{l(μ_{1})}h_{μ_{1}} ) … ( ∑_{μ_{p}⊧π_{p}} g_{l(μ_{p})}h_{μ_{p}} )

= ∑_{μ_{1}⊧π_{1}} … ∑_{μ_{p}⊧π_{p}} g_{l(μ_{1})} … g_{l(μ_{p})}h_{μ_{1}} … h_{μ_{p}}.

We introduce the new notation for a “composition of compositions”,

∑_{μ⊧π} x_{μ} = ∑_{μ_{1}⊧π_{1}} … ∑_{μ_{p}⊧π_{p}} x_{μ_{1}} … x_{μ_{p}},

so that we can write

(f ∘ (g ∘ h))_{n} = ∑_{μ⊧π⊧n} f_{|π|}g_{|μ|}h_{μ}.

Moreover, the associativity of function compositions translates into another equivalent expression,

((f ∘ g) ∘ h)_{n} = ∑_{\begin{matrix}π⊧n \\ μ⊧|π| \end{matrix}} f_{|μ|}g_{μ}h_{π}.

For n = 4, we have the 5 equivalent possibilities

f^{(1)} ∘ f^{(2)} ∘ f^{(3)} ∘ f^{(4)} = f^{(1)} ∘ (f^{(2)} ∘ (f^{(3)} ∘ f^{(4)})) = ∑\begin{matrix}π⊧n \\ μ⊧π \\ λ⊧μ \end{matrix} f_{|π|}^{(1)}f_{|μ|}^{(2)}f_{|λ|}^{(3)}f_{λ}^{(4)}

= ((f^{(1)} ∘ f^{(2)}) ∘ f^{(3)}) ∘ f^{(4)} = ∑\begin{matrix}π⊧n \\ μ⊧|π| \\ λ⊧|μ| \end{matrix} f_{|λ|}^{(1)}f_{λ}^{(2)}f_{μ}^{(3)}f_{π}^{(4)}

= (f^{(1)} ∘ f^{(2)}) ∘ (f^{(3)} ∘ f^{(4)}) = ∑\begin{matrix}π⊧n \\ μ⊧|π| \\ λ⊧π \end{matrix} f_{|μ|}^{(1)}f_{μ}^{(2)}f_{|λ|}^{(3)}f_{λ}^{(4)}

= f^{(1)} ∘ ((f^{(2)} ∘ f^{(3)}) ∘ f^{(4)}) = ∑\begin{matrix}π⊧n \\ μ⊧π \\ λ⊧|μ| \end{matrix} f_{|π|}^{(1)}f_{|λ|}^{(2)}f_{λ}^{(3)}f_{μ}^{(4)}

= (f^{(1)} ∘ (f^{(2)} ∘ f^{(3)})) ∘ f^{(4)} = ∑\begin{matrix}π⊧n \\ μ⊧|π| \\ λ⊧μ \end{matrix} f_{|μ|}^{(1)}f_{|λ|}^{(2)}f_{λ}^{(3)}f_{π}^{(4)},

with the corresponding tree representations

f^{(1)} ∘ (f^{(2)} ∘ (f^{(3)} ∘ f^{(4)})) f^{(1)} f^{(2)} ∘ (f^{(3)} ∘ f^{(4)}) f^{(2)} f^{(3)} ∘ f^{(4)} f^{(3)} f^{(4)} |π| π |μ| μ |λ| λ  \begin{matrix}((f^{(1)} ∘ f^{(2)}) ∘ f^{(3)}) ∘ f^{(4)} \\ (f^{(1)} ∘ f^{(2)}) ∘ f^{(3)} \\ f^{(1)} ∘ f^{(2)} \\ f^{(1)} \\ f^{(2)} \\ f^{(3)} \\ f^{(4)} \\ |π| \\ |μ| \\ |λ| \\ λ \\ μ \\ π \end{matrix} \begin{matrix}(f^{(1)} ∘ f^{(2)}) ∘ (f^{(3)} ∘ f^{(4)}) \\ f^{(1)} ∘ f^{(2)} \\ f^{(1)} \\ f^{(2)} \\ f^{(3)} ∘ f^{(4)} \\ f^{(3)} \\ f^{(4)} \\ |π| \\ |μ| \\ μ \\ π \\ |λ| \\ λ \end{matrix}

f^{(1)} ∘ ((f^{(2)} ∘ f^{(3)}) ∘ f^{(4)}) f^{(1)} (f^{(2)} ∘ f^{(3)}) ∘ f^{(4)} f^{(2)} ∘ f^{(3)} f^{(2)} f^{(3)} f^{(4)} |π| π |μ| |λ| λ μ  \begin{matrix}(f^{(1)} ∘ (f^{(2)} ∘ f^{(3)})) ∘ f^{(4)} \\ f^{(1)} ∘ (f^{(2)} ∘ f^{(3)}) \\ f^{(1)} \\ f^{(2)} ∘ f^{(3)} \\ f^{(2)} \\ f^{(3)} \\ f^{(4)} \\ |π| \\ |μ| \\ μ \\ |λ| \\ λ \\ π \end{matrix}

Consider now the general case f^{(1)} ∘ ⋯ ∘ f^{(n)}. There are C_{n+1} ways to compose these functions associatively, where C_{n} is the n−th Catalan number

C_{n} = \frac{1}{2n + 1}\binom{2n}{n}.

The associativity of function composition gives us then C_{n+1} − 1 equivalent representations for generalized composition sums.

While writing down each of these C_{n+1} representations is very messy, we present a simple algorithmic approach for doing so. The general formula for the composition f^{(1)} ∘ ⋯ ∘ f^{(n)} is

∑ ; π_{1}⊧n ; π_{2}⊧π_{1}^{±} ; ⋮ ; π_{n−1}⊧π_{n−2}^{±} f_{π_{i_{1}}^{±}}^{(1)}f_{π_{i_{2}}^{±}}^{(2)}⋮f_{π_{in}^{±}}^{(n)},

with the notation π_{i}^{+} = π_{i} and π_{i}^{−} = |π_{i}|. We draw the tree representation for function composition and determine the summation set by the following rules:

• If the parent of the level corresponding to π_{i} is a right child, we sum over π_{i−1}^{+} = π_{i−1}. If it is a left child, we sum over π_{i−1}^{−} = |π_{i−1}|.

• Select f^{(i)} and look where it is a leaf. If it is a right child, we sum over the factor f_{π_{j}}^{(i)}, where j is the depth of the leaf f^{(i)}. If f^{(i)} is a leaf and a left child, we sum over the factor f_{|π_{j}|}^{(i)}.

• At the top level, the previous rules do not apply and we always sum over f_{π_{1}}^{(i)} and π_{1} ⊧ n.

This way, the subscript is determined by the leaf’s position while the summation set is determined by the parent’s position in the corresponding tree. For instance, select the following tree:

(f^{(1)} ∘ (f^{(2)} ∘ f^{(3)})) ∘ f^{(4)} f^{(1)} ∘ (f^{(2)} ∘ f^{(3)}) f^{(1)} f^{(2)} ∘ f^{(3)} f^{(2)} f^{(3)} f^{(4)} |π_{1}| |π_{2}| π_{2} |π_{3}| π_{3} π_{1}

Consider the term f^{(1)}. It is a left child with depth 2, so it has the subscript |π_{2}|. Its parent f^{(1)} ∘ (f^{(2)} ∘ f^{(3)}) is also a left child, so that the summation includes the terms π_{2} ⊧ |π_{1}|. The term f^{(3)} is a right child with depth 3, so that we sum over f_{π_{3}}^{(3)}. Its parent is a right child so the summation goes over π_{3} ⊧ π_{2}. Repeating this procedure for f^{(2)} and f^{(4)} allows us to recover our previous expression

(f^{(1)} ∘ (f^{(2)} ∘ f^{(3)})) ∘ f^{(4)} = ∑_{\begin{matrix}π_{1}⊧n \\ π_{2}⊧|π_{1}| \\ π_{3}⊧π_{2} \end{matrix}} f_{|π_{2}|}^{(1)}f_{|π_{3}|}^{(2)}f_{π_{3}}^{(3)}f_{π_{1}}^{(4)}.  (24)

6 Conclusion

In this paper, we recognized Fuchs’ generalized PI tree as a graphical method to represent sums over compositions. Then, the introduction of the Faá di Bruno formula allowed us to introduce further set of weights based on the number of parts in every compositions. Trees are then an easy “bookkeeping” method to visualize the classical Faá di Bruno formula. The introduction of this Faá di Bruno formula also allowed us to synthesize many past works, since the nonlinear weights f_{n} generalize most of the existing literature on compositions. Through this generating function methodology, we were also able to find a generating function for sums over all parts of all compositions of n. Together, our results unite the existing literature on composition sums and provide an efficient method to graphically visualize them. For the first time, we also study iterated sums over compositions and link them to tree representations.

7 Acknowledgements

T.W. would like to thank Calvert 2209, Harford fam, and the Wu Tang Clan for many good times this semester, and the ability to put up with him for far too long. We also wish the best to Prof. Vella, who has championed the ideas underlying this paper for close to two decades and independently discovered many of our results.

References

[1] K. Alladi and V. E. Hoggatt Jr., Compositions with ones and twos, Fibonacci Quart. 13 (1975), 233–239.

[2] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Seq. 16 (2013), Article 13.1.3.

[3] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge, 2009.

[4] P. Fuchs, Bernoulli numbers and binary trees, Tatra Mt. Math. Publ. 20 (2000), 111–117.

[5] I. M. Gessel and J. Li, Compositions and Fibonacci identities, J. Integer Seq. 16 (2013), Article 13.4.5.

[6] V. E. Hoggatt, Jr. and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combin. Theory 4 (1968), 121–124.

[7] F. T. Howard, Some sequences of rational numbers related to the exponential function, Duke Math. J. 34 (1967), 701–716.

[8] M. Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. Integer Seq. 3 (2000), Article 00.2.9.

[9] D. Merlini, F. Uncini, and M. C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), #A23.

[10] F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, and B. V. Saunders, eds., NIST Digital Library of Mathematical Functions, Release 1.0.17 of 2017-12-22. Available at NIST.

[11] A. V. Sills, Compositions, partitions, and Fibonacci numbers, Fibonacci Quart. 49 (2011), 348–354.

[12] H. M. Srivastava and P. G. Todorov, An explicit formula for the generalized Bernoulli polynomials, J. Math. Anal. Appl. 130 (1988), 509–513.

[13] D. C. Vella, Explicit formulas for Bernoulli and Euler numbers, Integers 8 (2008), #A01.

[14] D. C. Vella, Unpublished, Private communication.

[15] S. C. Woon, A tree for generating Bernoulli numbers, Math. Mag. 70 (1997), 51–56.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: Woon’s tree, sum over compositions.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A027641}, and \underline{A027642}.)

Received June 4 2017; revised versions received December 27 2018; January 24 2018; March 9 2018. Published in Journal of Integer Sequences, March 9 2018.

Return to Journal of Integer Sequences home page.