A214568 -id:A214568 - cp's OEIS frontend

A262253 A weighted sum over the rooted trees of n nodes (A214568).

0, 1, 3, 9, 29, 90, 285, 886, 2764, 8543, 26387, 81091, 248752, 760687, 2321950, 7072376

Offset: 0

R. J. Mathar, Sep 16 2015

(More precise name desired.)

R. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179, function F(x).
Index entries for sequences related to rooted trees

a(n) = sum_{k>=1} binomial(k+1,2) A214568(n,k).
A007098(x) = A(x) -A(x^2) -A000081(x)*A(x) -{A000107(x)^2 - A000107(x^2)}/2 is the relation between the generating functions, eq. prior to (4.9) by Harary-Robinson.
A(x) = A000081(x)*{A(x)-A(x^2)+ A000107(x^2)/2} +{A000081(x)+A000107(x)+A000107(x)^2}/2 , eq. (4.6) by Harary-Robinson.

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

Original entry on oeis.org

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

A228601 Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 2, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 2, 1, 0, 0, 1, 2, 4, 1, 2, 1, 0, 2, 1, 7, 4, 4, 4, 1, 0, 1, 2, 7, 7, 9, 10, 8, 3, 0, 2, 3, 12, 10, 17, 19, 20, 17, 6, 0, 1, 2, 12, 14, 28, 37, 45, 46, 35, 15, 0, 2, 1, 18, 21, 46, 60, 87, 106, 103, 78, 29

Offset: 1

Emeric Deutsch, Oct 20 2013

The entries in the triangle have been obtained - painstakingly - from the Read & Wilson reference (pp. 63-73); the white vertices indicate the possible distinct rootings for the given tree.

			Row 4 is 0,2,0,0 because the trees with 4 vertices are (i) the path tree abcd with 2 distinct rootings (at a and at b) and (ii) the star tree with 4 vertices having, obviously, 2 distinct rootings.
Triangle starts:
  1;
  1, 0;
  0, 1, 0;
  0, 2, 0, 0;
  0, 1, 1, 1, 0;
  0, 2, 1, 2, 1, 0;
  0, 1, 2, 4, 1, 2, 1;

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

Sean A. Irvine, Rows n=1..44 of triangle, flattened
F. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179.

Cf. A000055, A000081, A000220.

Sum of entries in row n = A000055(n).
Sum_{k=1..n} k*T(n,k)  = A000081(n).
T(n,n) = A000220(n).
Let A214568(x,y) be the bivariate g.f. of A214568, then this g.f. is A214568(x,y) -( [A214568(x,y)]^2 + A214568(x^2,y^2) )/2 + A214568(x^2,y), see eq. (4.8) by Harary-Robinson. - R. J. Mathar, Sep 16 2015

cp's OEIS Frontend

A262253 A weighted sum over the rooted trees of n nodes (A214568).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

A228601 Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula