Journal of Integer Sequences, Vol. 21 (2018), Article 18.3.4

Woon's Tree and Sums over Compositions

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

Tanay Wakhare
University of Maryland
College Park, MD 20742


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000108 A027641 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