A193406 -id:A193406 - 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

A193405 The Matula numbers of the rooted trees that have a perfect matching.

Original entry on oeis.org

2, 5, 6, 15, 18, 22, 23, 26, 31, 41, 45, 54, 55, 65, 66, 69, 78, 93, 94, 103, 122, 123, 135, 137, 158, 162, 165, 166, 167, 195, 198, 202, 207, 211, 234, 235, 242, 253, 254, 279, 282, 283, 286, 299, 305, 309, 338, 341, 358, 366, 369, 394, 395, 401, 403, 405, 411, 415, 419, 431, 451, 474, 486, 495, 498

Offset: 1

Emeric Deutsch, Feb 12 2012

nonn

The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.
It is known that a tree has at most one perfect matching.
Complement of A193406.

			2,6,31 are in the sequence because they are the Matula numbers of the paths on 2,4,6 vertices, respectively.

C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993.

É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319.
E. Deutsch, Rooted tree statistics from Matula numbers, 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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

Cf. A061775, A193406.

with(numtheory): N := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then 1+N(pi(n)) else N(r(n))+N(s(n))-1 end if end proc: M := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then [0, 1] elif bigomega(n) = 1 then [x*M(pi(n))[2], M(pi(n))[1]+M(pi(n))[2]] else [M(r(n))[1]*M(s(n))[2]+M(r(n))[2]*M(s(n))[1], M(r(n))[2]*M(s(n))[2]] end if end proc: m := proc (n) options operator, arrow: sort(expand(M(n)[1]+M(n)[2])) end proc: PM := {}: for n to 500 do if N(n) = 2*degree(m(n)) then PM := `union`(PM, {n}) else  end if end do: PM;

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
V[n_] := Which[n == 1, 1, PrimeOmega[n] == 1, 1 + V[PrimePi[n]], True, V[r[n]] + V[s[n]] - 1];
M[n_] := Which[n == 1, {0, 1}, PrimeOmega[n] == 1, {x*M[PrimePi[n]][[2]], Total[M[PrimePi[n]]]}, True, {M[r[n]][[1]]*M[s[n]][[2]] + M[r[n]][[2]]*M[s[n]][[1]], M[r[n]][[2]]*M[s[n]][[2]]}];
m[n_] := M[n] // Total // Expand;
PM = {};
Do[If[V[n] == 2 Exponent[m[n], x], PM = Union[PM, {n}]], {n, 1, 500}];
PM (* Jean-François Alcover, Jun 21 2024, after Maple code *)

Define b(n) (c(n)) to be the generating polynomials of the matchings of the rooted tree with Matula-Goebel number n that contain (do not contain) the root, with respect to the size of the matching. We have the following recurrence for the pair M(n)=[b(n),c(n)]. M(1)=[0,1]; if n=prime(t), then M(n)=[xc(t),b(t)+c(t)]; if n=r*s (r,s,>=2), then M(n)=[b(r)*c(s)+c(r)*b(s), c(r)*c(s)]. Then m(n)=b(n)+c(n) is the generating polynomial of the matchings of the rooted tree with respect to the size of the matchings (a modified matching polynomial). The tree has a perfect matching if and only if the degree of this polynomial is 1/2 of the number of vertices of the tree.

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