OFFSET
1,7
COMMENTS
Gives multiplicity for tree shapes in "naturally grown" forests of rooted trees (from file for CM(t) referred to in Broadhurst).
A refinement of the enumeration of the trees of the first few forests in terms of planar rather than nonplanar rooted trees is presented on p. 21 of the Munthe-Kaas and Lundervold paper. - Tom Copeland, Jul 16 2018 (The refinement is presented also in Lundervold and on p. 35 of the Lundervold and Munthe-Kaas paper. - Tom Copeland, Jul 21 2021)
Enumerates the elementary differentials of the Butcher group that Cayley showed are in bijection with these nonplanar rooted trees when considering multivariable vector functions. When considering a scalar function of one independent variable, the associated differentials are no longer in bijection with the planar trees and are enumerated by A139605. Two nonplanar trees are considered equivalent if the branches of one may be rotated about its nodes to match those of the other. - Tom Copeland, Jul 21 2021
REFERENCES
J. Butcher, Numerical Methods for Ordinary Differential Equations, 3rd Ed., Wiley, 2016, Table 310(II) on p. 165.
E. Hairer, C. Lubich, G. Wanner, Geometric Numerical Integration - Structure-Preserving Algorithms for Ordinary Differential Equations, 2nd Ed., Springer, 2006, pp. 52 and 53.
LINKS
S. Agarwala and C. Delaney, Generalizing the Connes-Moscovici Hopf algebra to include all rooted trees, arXiv:1302.4004 [math-ph], 2015, pp. 2, 9, and 21.
C. Bergbauer and D. Kreimer, Hopf algebras in renormalization theory: Locality and Dyson-Schwinger equations from Hochschild cohomology, arXiv:hep-th/0506190 [hep-th], 2006, p. 14.
D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, arXiv:hep-th/9810087 [hep-th], 1998.
C. Brouder, Trees, renormalization, and differential equations, BIT Numerical Mathematics, 44: 425-438, 2004, p. 434.
F. Chapoton, Rooted trees and an exponential-like series, arXiv:math/0209104 [math.QA], 2002.
A. Connes and D. Kreimer, Hopf algebras, renormalization, and noncommutative geometry, arXiv:hep-th/9808042 [hep-th], 1998, pp. 21 and 28.
Tom Copeland, A Walk in the Woods with Cayley and Comtet, 2008.
Tom Copeland, Mathemagical Forests, 2008.
W. Dugan, L. Foissy, and K. Yeats, Sequences of Trees and Higher-Order Renormalization Group Equations, arXiv:2209.06576 [math.CO], 2023, p. 4.
L. Foissy, Faa di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations, arXiv:0707.1204 [math.RA], 2007, p. 2.
E. Getzler, Lie theory for nilpotent L-infinity algebras, arXiv:math/0404003 [math.AT], 2004-2007, p. 22.
M. Ginocchio, Universal expansion of the powers of a derivation, Lett. Math. Phys. 34, 343-364, 1995, see table on p. 364.
T. Krajewski and T. Martinetti, Wilsonian renormalization, differential equations and Hopf algebras, arXiv:0806.4309 [hep-th], 2008, p. 14.
D. Kreimer, Renormalization and Renormalization Group, lecture notes by L. Klaczynski of class lectures by Dirk Kreimer, 2012, p. 16.
A. Lundervold, Lie-Butcher series and geometric numerical integration on manifolds, Ph.D. thesis, Dept. of Math., Univ. of Bergen, 2011, pp. 8 and 10.
A. Lundervold and H. Munthe-Kaas, On algebraic structures of numerical integration on vector spaces and manifolds, arXiv:1112.4465 [math.QA], 2013. p. 6.
Mathoverflow, Formula for n-th iteration of dx/dt=B(x), a question on MathOverflow posed by the user resolvent and answered by Tom Copeland, 2021.
H. Munthe-Kaas and A. Lundervold, On post-Lie algebras, Lie-Butcher series and moving frames, arXiv:1203.4738 [math.NA], 2013.
FORMULA
The table on p. 364 of Ginocchio contains the Connes-Moscovici weights correlated with associated derivatives D^k. From the relation of this entry to A139605 and A145271, the action of the weighted differentials on an exponential is associated with the operation exp(x g(u)D_u) e^(ut) = e^(t H^{(-1)}(H(u)+x)) with g(x) = 1/D(H(x)) and H^{(-1)} the compositional inverse of H. With H^{(-1)}(x) = -log(1-x), the inverse about x=0 is H(x) = 1-e^(-x), giving g(x) = e^x and the resulting action e^(-t log(1-x)) = (1-x)^(-t) for u=0, an e.g.f. for the unsigned Stirling numbers of the first kind A008275 and A048994. Consequently, summing the Connes-Moscovici weights over each associated derivative gives these Stirling numbers. E.g., the fifth row in the examples reduces to (1+3+1+1) D + (4+4+3) D^2 + 6 D^3 + D^4 = 6 D + 11 D^2 + 6 D^3 + D^4. - Tom Copeland, Jul 14 2021
EXAMPLE
From Tom Copeland, Dec 06 2017: (Start)
The number of distinct rooted tree types, or shapes, with n nodes is given by A000081(n+1), so the multiplicities for the tree shapes of the forests of naturally grown trees given here may be grouped according to A000081. For example, A000081(5)=4 corresponds to the four tree types depicted in Fig. 6 of Mathemagical Forests with four nodes, or vertices, with the four multiplicities (1,1,3,1); A000081(4)=2 corresponds to the two tree types depicted in Fig. 3 with three nodes and the two multiplicities (1,1); A000081(3)=1, with one tree type with two nodes and multiplicity (1); and A000081(2)=1, with one tree type with one node and multiplicity (1). Then the sequence here begins (1)(1)(1,1)(1,1,3,1).
First few rows (with last row reordered according to Fig. 7 of Mathemagical Forests):
1
1
1, 1
1, 1, 3, 1
1, 1, 3, 4, 4, 3, 6, 1, 1
This last row corresponds to the one listed in Broadhurst as
1, 3, 1, 1, 4, 4, 3, 6, 1.
(End)
MATHEMATICA
nmax = 7;
SetAttributes[t, Orderless];
size[tree_] := Count[tree, _, All];
lst = {{t[]}};
forests[0, 0] = {{}}; forests[_?Positive, 0] = {}; forests[_?Negative, _] = {};
forests[n_, k_] := forests[n, k] = With[{tree = Flatten[lst][[k]]}, Join[Append[tree] /@ forests[n - size@tree, k], forests[n, k-1]]];
Do[AppendTo[lst, t @@@ forests[n-1, Length[Flatten@lst]]], {n, 2, nmax}];
assoc = Association[{# -> 0} & /@ Flatten@lst];
assoc[t[]] = 1;
Do[assoc[Insert[tree, t[], Append[Most@p, 1]]] += assoc[tree], {n, 2, nmax}, {tree, lst[[n-1]]}, {p, Position[tree, t]}];
Last /@ Normal@assoc (* Andrey Zabolotskiy, Mar 15 2024 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Tom Copeland, May 31 2008
STATUS
approved