A206496 -id:A206496 - cp's OEIS frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).

Each n occurs A000081(n) times.

			a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.

import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
   g x = y : g (x + 1) where
      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
          where t = a049084 x; u = a020639 x; v = x `div` u
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
a(n) = A091238(A091204(n)). - Antti Karttunen, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

A006472 a(n) = n!*(n-1)!/2^(n-1).

Original entry on oeis.org

1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, 2571912000, 141455160000, 9336040560000, 728211163680000, 66267215894880000, 6958057668962400000, 834966920275488000000, 113555501157466368000000, 17373991677092354304000000, 2970952576782792585984000000

Offset: 1

N. J. A. Sloane

Product of first (n-1) positive triangular numbers. - Amarnath Murthy, May 19 2002, corrected by Alex Ratushnyak, Dec 03 2013
Number of ways of transforming n distinguishable objects into n singletons via a sequence of n-1 refinements. Example: a(3)=3 because we have XYZ->X|YZ->X|Y|Z, XYZ->Y|XZ->X|Y|Z and XYZ->Z|XY->X|Y|Z. - Emeric Deutsch, Jan 23 2005
In other words, a(n) is the number of maximal chains in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018
From David Callan, Aug 27 2009: (Start)
With offset 0, a(n) = number of unordered increasing full binary trees of 2n edges with leaf set {n,n+1,...,2n}, where full binary means each nonleaf vertex has two children, increasing means the vertices are labeled 0,1,2,...,2n and each child is greater than its parent, unordered might as well mean ordered and each pair of sibling vertices is increasing left to right. For example, a(2)=3 counts the trees with edge lists {01,02,13,14}, {01,03,12,14}, {01,04,12,13}.
PROOF. Given such a tree of size n, to produce a tree of size n+1, two new leaves must be added to the leaf n. Choose any two of the leaf set {n+1,...,2n,2n+1,2n+2} for the new leaves and use the rest to replace the old leaves n+1,...,2n, maintaining relative order. Thus each tree of size n yields (n+2)-choose-2 trees of the next size up. Since the ratio a(n+1)/a(n)=(n+2)-choose-2, the result follows by induction.
Without the condition on the leaves, these trees are counted by the reduced tangent numbers A002105. (End)
a(n) = Sum(M(t)N(t)), where summation is over all rooted trees t with n vertices, M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494) and N(t) is  the number of ways to build up t from the one-vertex tree by adding successively edges to the existing vertices (the Connes-Moscovici weight; see A206496). See Remark on p. 3801 of the Hoffman reference. Example: a(3) = 3; indeed, there are two rooted trees with 3 vertices: t' = the path r-a-b and t" = V; we have M(t')=N(t')=1 and M(t") =1, N(t")=2, leading to M(t')N(t') + M(t")N(t")=3. - Emeric Deutsch, Jul 20 2012
Number of coalescence sequences or labeled histories for n lineages: the number of sequences by which n distinguishable leaves can coalesce to a single sequence. The coalescence process merges pairs of lineages into new lineages, labeling each newly formed lineage l by a subset of the n initial lineages corresponding to the union of all initial lineages that feed into lineage l. - Noah A Rosenberg, Jan 28 2019
Conjecture: For n > 1, n divides 2*a(n-1) + 4 if and only if n is prime. - Werner Schulte, Oct 04 2020
For a proof of the above conjecture see Himane. The list of primes p such that p^2 divides (2*a(p-1) + 4) (analog of A007540 - Wilson primes) begins [239, 24049, ...]. - Peter Bala, Nov 06 2024

			From _Gus Wiseman_, Jul 22 2018: (Start)
The (3) = 3 maximal chains in the lattice of set partitions of {1,2,3}:
  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
  {{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
  {{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
(End)

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.
László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Mike Steel, Phylogeny: Discrete and Random Processes in Evolution, SIAM, 2016, p. 47.

T. D. Noe, Table of n, a(n) for n = 1..50
E. H. Dickey, N. A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Karl Dienger, Beiträge zur Lehre von den arithmetischen und geometrischen Reihen höherer Ordnung, Jahres-Bericht Ludwig-Wilhelm-Gymnasium Rastatt, Rastatt, 1910. [Annotated scanned copy]
Daniel Dockery, Polygorials, Special "Factorials" of Polygonal Numbers, preprint, 2003.
Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012.
A. W. F. Edwards, Estimation of the branch points of a branching diffusion Process, J. Royal Stat. Soc. Ser. B 32 (1970), 155-164.
P. Erdős, R. K. Guy and J. W. Moon, On refining partitions, J. London Math. Soc., 9 (1975), 565-570.
L. Ferretti, F. Disanto and T. Wiehe, The Effect of Single Recombination Events on Coalescent Tree Height and Shape, PLoS ONE 8(4): e60123.
O. Frank and K. Svensson, On probability distributions of single-linkage dendrograms, Journal of Statistical Computation and Simulation, 12 (1981), 121-131. (Annotated scanned copy)
Djamel Himane, A simple proof of Werner Schulte's conjecture, arXiv:2404.08646 [math.GM], 2024. See also Notes Num. Theor. Disc. Math., (2025) Vol. 31, No. 2, 251-225.
M. E. Hoffman, Combinatorics of rooted trees and Hopf algebras, Trans. Amer. Math. Soc., 355, 2003, 3795-3811.
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of the Legendre-Stirling numbers, arXiv:1805.10998 [math.CO], 2018.
C. L. Mallows, Note to N. J. A. Sloane circa 1979.
F. Murtagh, Counting dendrograms: a survey, Discrete Applied Mathematics, 7 (1984), 191-199.
N. A. Rosenberg, The mean and variance of the numbers of r-pronged nodes and r-caterpillars in Yule-generated genealogical trees, Annals of Combinatorics, 10 (2006), 129-146.
Thomas Wiehe, Counting, grafting and evolving binary trees, arXiv:2010.06409 [q-bio.PE], 2020.
Johannes Wirtz, On the enumeration of leaf-labelled increasing trees with arbitrary node-degree, arXiv:2211.03632 [q-bio.PE], 2022. See page 12.
Index entries for sequences related to factorial numbers.

Cf. A000110, A000258, A002846, A005121, A213427, A317145, A363679 (sum of reciprocals).
Cf. A084939, A084940, A084941, A084942, A084943, A084944.
For the type B and D analogs, see A001044 and A123385.

[Factorial(n)*Factorial(n-1)/2^(n-1): n in [1..20]]; // Vincenzo Librandi, Aug 23 2018

Maple
```
A006472 := n -> n!*(n-1)!/2^(n-1):
```

FoldList[Times,1,Accumulate[Range[20]]] (* Harvey P. Dale, Jan 10 2013 *)

a(n) = n*(n-1)!^2/2^(n-1) \\ Charles R Greathouse IV, May 18 2015

from math import factorial
def A006472(n): return n*factorial(n-1)**2 >> n-1 # Chai Wah Wu, Jun 22 2022

a(n) = a(n-1)*A000217(n-1).
a(n) = A010790(n-1)/2^(n-1).
a(n) = polygorial(n, 3) = (A000142(n)/A000079(n))*A000142(n+1) = (n!/2^n)*Product_{i=0..n-1} (i+2) = (n!/2^n)*Pochhammer(2, n) = (n!^2/2^n)*(n+1) = polygorial(n, 4)/2^n*(n+1). - Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
a(n-1) = (-1)^(n+1)/(n^2*det(M_n)) where M_n is the matrix M_(i, j) = abs(1/i - 1/j). - Benoit Cloitre, Aug 21 2003
From Ilya Gutkovskiy, Dec 15 2016: (Start)
a(n) ~ 4*Pi*n^(2*n)/(2^n*exp(2*n)).
Sum_{n>=1} 1/a(n) = BesselI(1,2*sqrt(2))/sqrt(2) = 2.3948330992734... (End)
D-finite with recurrence 2*a(n) -n*(n-1)*a(n-1)=0. - R. J. Mathar, May 02 2022
Sum_{n>=1} (-1)^(n+1)/a(n) = BesselJ(1,2*sqrt(2))/sqrt(2). - Amiram Eldar, Jun 25 2022

A139002 Weights of Connes-Moscovici Hopf subalgebra.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 4, 4, 3, 6, 1, 1, 6, 3, 4, 4, 1, 1, 3, 1, 5, 15, 5, 5, 10, 10, 10, 10, 15, 10, 1, 1, 10, 15, 10, 10, 10, 10, 5, 5, 15, 5, 1, 3, 1, 1, 4, 4, 3, 6, 1, 6, 36, 18, 24, 24, 6, 6, 18, 6, 15, 15, 45, 45, 15, 15, 15, 15, 10, 20, 60, 20, 10, 60, 20, 15, 45, 15, 1, 1

Offset: 1

Tom Copeland, May 31 2008

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

			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)

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.

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], 2005-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.

Cf. A000081, A008275, A048994, A139605, A145271, A206495.

A206496 is a permutation of this sequence.

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 *)

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

cp's OEIS Frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A006472 a(n) = n!*(n-1)!/2^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A139002 Weights of Connes-Moscovici Hopf subalgebra.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula