A184165 -id:A184165 - cp's OEIS frontend

A212623 Irregular triangle read by rows: T(n,k) is the number of independent vertex subsets with k vertices of the rooted tree with Matula-Goebel number n (n>=1, k>=0).

1, 1, 1, 2, 1, 3, 1, 1, 3, 1, 1, 4, 3, 1, 4, 3, 1, 4, 3, 1, 1, 4, 3, 1, 1, 5, 6, 1, 1, 5, 6, 1, 1, 5, 6, 1, 1, 5, 6, 2, 1, 5, 6, 2, 1, 5, 6, 2, 1, 6, 10, 4, 1, 5, 6, 4, 1, 1, 5, 6, 2, 1, 6, 10, 5, 1, 5, 6, 4, 1, 1, 6, 10, 5, 1, 1, 6, 10, 5, 1, 1, 6, 10, 4, 1, 6, 10, 5, 1, 6, 10, 7, 2, 1, 7, 15

Offset: 1

Emeric Deutsch, Jun 01 2012

A vertex subset in a tree is said to be independent if no pair of vertices is connected by an edge. The empty set is considered to be independent.
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.
Sum of entries in row n = A184165(n) = number of independent vertex subset (the Merrifield-Simmons index).
Sum(k*T(n,k), k>=0) = A212624(n) = number of vertices in all independent vertex subsets.
Number of entries in row n = 1 + number of vertices in the largest independent vertex subset = 1 + A212625(n).
Last entry in row n = A212626(n) = number of largest independent vertex subsets.
With the given Maple program, the command P(n) yields the generating polynomial of row n.

			Row 5 is [1,4,3] because the rooted tree with Matula-Goebel number 5 is the path tree R - A - B - C with independent vertex subsets: {}, {R}, {A}, {B}, {C}, {R,B}, {R,C}, {A,C}.
Triangle starts:
  1, 1;
  1, 2;
  1, 3, 1;
  1, 3, 1;
  1, 4, 3;
  ...

Emeric 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.
H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quarterly, 20, 1982, 16-21.
Index entries for sequences related to Matula-Goebel numbers

Cf. A212618, A212619, A212620, A212621, A212622, A212624, A212625, A212626, A212627, A212628, A212629, A212630, A212631, A212632.

with(numtheory): A := 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 [x, 1] elif bigomega(n) = 1 then [expand(x*A(pi(n))[2]), expand(A(pi(n))[1])+A(pi(n))[2]] else [sort(expand(A(r(n))[1]*A(s(n))[1]/x)), sort(expand(A(r(n))[2]*A(s(n))[2]))] end if end proc: P := proc (n) options operator, arrow: sort(A(n)[1]+A(n)[2]) end proc: for n to 35 do seq(coeff(P(n), x, k), k = 0 .. degree(P(n))) end do; % yields sequence in triangular form

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
A [n_] := Which[n == 1, {x, 1}, PrimeOmega[n] == 1, {x*A[PrimePi[n]][[2]], A[PrimePi[n]][[1]] + A[PrimePi[n]][[2]]}, True, {A[r[n]][[1]]*A[s[n]][[1]]/x, A[r[n]][[2]]*A[s[n]][[2]]}];
P[n_] := A[n] // Total;
T[n_] := CoefficientList[P[n], x];
Table[T[n], {n, 1, 35}] // Flatten (* Jean-François Alcover, Jun 20 2024, after Maple code *)

Define R(n) =R(n,x) (S(n)=S(n,x)) the generating polynomial of the independent vertex subsets that contain (do not contain) the root of the rooted tree with Matula-Goebel number n. Then R(1)=x, S(1)=1, R(the t-th prime) = x*S(t), S(the t-th prime) = R(t) + S(t); R(rs) = R(r)R(s)/x, S(rs) = S(r)S(s), (r,s>=2).

A193404 Number of matchings (independent edge subsets) in the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 3, 5, 5, 4, 4, 8, 8, 8, 7, 7, 7, 13, 5, 7, 12, 5, 11, 11, 13, 12, 9, 21, 12, 20, 10, 11, 19, 13, 6, 21, 11, 18, 16, 9, 9, 19, 14, 12, 17, 10, 18, 32, 20, 19, 11, 15, 30, 18, 17, 6, 28, 34, 13, 14, 19, 11, 25, 16, 21, 28, 7, 31, 31, 9, 15, 32, 27, 14

Offset: 1

Emeric Deutsch, Feb 11 2012

nonn

A matching in a graph is a set of edges, no two of which have a vertex in common. The empty set is considered to be a matching.

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.

			a(3)=3 because the rooted tree with Matula-Goebel number 3 is the path ABC on 3 vertices; it has 3 matchings: empty, {AB}, {BC}.

É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319.
Emeric 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. A202853 (by size), A347966 (maximal), A347967 (maximum).

Cf. A184165 (independent vertex sets).

with(numtheory): A := 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 [A(pi(n))[2], A(pi(n))[1]+A(pi(n))[2]] else [A(r(n))[1]*A(s(n))[2]+A(s(n))[1]*A(r(n))[2], A(r(n))[2]*A(s(n))[2]] end if end proc: a := proc (n) options operator, arrow: A(n)[1]+A(n)[2] end proc: seq(a(n), n = 1 .. 80);

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
A[n_] := Which[n == 1, {0, 1}, PrimeOmega[n] == 1, {A[PrimePi[n]][[2]], A[PrimePi[n]][[1]] + A[PrimePi[n]][[2]]}, True, {A[r[n]][[1]]* A[s[n]][[2]] + A[s[n]][[1]]*A[r[n]][[2]], A[r[n]][[2]]*A[s[n]][[2]]}];
a[n_] := Total[A[n]];
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Jun 25 2024, after Maple code *)

Define b(n) (c(n)) to be the number of matchings of the rooted tree with Matula-Goebel number n that contain (do not contain) the root. We have the following recurrence for the pair A(n)=[b(n),c(n)]. A(1)=[0,1]; if n=prime(t), then A(n)=[c(t),b(t)+c(t)]; if n=r*s (r,s,>=2), then A(n)=[b(r)*c(s)+c(r)*b(s), c(r)c(s)]. Clearly, a(n)=b(n)+c(n). See the Czabarka et al. reference (p. 3315, (2)). The Maple program is based on this recursive formula.

A228731 Number of independent subsets in the rooted tree with Matula-Goebel number n that contain the root.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 4, 3, 5, 2, 6, 4, 6, 1, 5, 4, 8, 3, 8, 5, 9, 2, 9, 6, 8, 4, 10, 6, 8, 1, 10, 5, 12, 4, 12, 8, 12, 3, 8, 8, 10, 5, 12, 9, 15, 2, 16, 9, 10, 6, 16, 8, 15, 4, 16, 10, 9, 6, 18, 8, 16, 1, 18, 10, 9, 5, 18, 12, 20, 4, 15, 12, 18, 8, 20, 12

Offset: 1

Emeric Deutsch and Reinhard Zumkeller, Sep 01 2013

A184165(n) = a(n) + A228732(n);

this sequence and A228732 are defined by a pair of mutually recursive functions, see A184165 for definition (called b and c there).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Matula-Goebel numbers

Cf. A184165, A228732.

Haskell
```
see A184165.
```

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
A[n_] := A[n] = If[n==1, {1, 1}, If[PrimeOmega[n]==1, {A[PrimePi[n]][[2]], A[PrimePi[n]] // Total}, A[r[n]] * A[s[n]]]];
a[n_] := A[n][[1]];
a /@ Range[1, 80] (* Jean-François Alcover, Sep 20 2019 *)

Completely multiplicative with a(prime(t)) = A228732(t). - Andrew Howroyd, Aug 01 2018

A228732 Number of independent subsets in the rooted tree with Matula-Goebel number n that do not contain the root.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 5, 8, 9, 10, 8, 12, 8, 10, 15, 16, 9, 18, 9, 20, 15, 16, 13, 24, 25, 16, 27, 20, 13, 30, 13, 32, 24, 18, 25, 36, 14, 18, 24, 40, 14, 30, 14, 32, 45, 26, 21, 48, 25, 50, 27, 32, 17, 54, 40, 40, 27, 26, 14, 60, 22, 26, 45, 64, 40, 48, 17, 36

Offset: 1

Emeric Deutsch and Reinhard Zumkeller, Sep 01 2013

A184165(n) = A228731(n) + a(n);

this sequence and A228731 are defined by a pair of mutually recursive functions, see A184165 for definition (called b and c there).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Matula-Goebel numbers

Cf. A184165, A228731.

Haskell
```
see A184165.
```

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
A[n_] := A[n] = If[n==1, {1, 1}, If[PrimeOmega[n]==1, {A[PrimePi[n]][[2]], A[PrimePi[n]] // Total}, A[r[n]] * A[s[n]]]];
a[n_] := A[n][[2]];
a /@ Range[1, 80] (* Jean-François Alcover, Sep 20 2019 *)

Completely multiplicative with a(prime(t)) = A228731(t) + A228732(t). - Andrew Howroyd, Aug 01 2018

cp's OEIS Frontend

A212623 Irregular triangle read by rows: T(n,k) is the number of independent vertex subsets with k vertices of the rooted tree with Matula-Goebel number n (n>=1, k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A193404 Number of matchings (independent edge subsets) in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A228731 Number of independent subsets in the rooted tree with Matula-Goebel number n that contain the root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A228732 Number of independent subsets in the rooted tree with Matula-Goebel number n that do not contain the root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula