login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A213670 Irregular triangle read by rows: a(n,k) is the number of vertex subsets of the rooted tree with Matula-Goebel number n having k components in the induced subgraph (n>=1, k>=0). 1
1, 1, 1, 3, 1, 6, 1, 1, 6, 1, 1, 10, 5, 1, 10, 5, 1, 11, 3, 1, 1, 11, 3, 1, 1, 15, 15, 1, 1, 15, 15, 1, 1, 15, 15, 1, 1, 17, 11, 3, 1, 17, 11, 3, 1, 17, 11, 3, 1, 21, 35, 7, 1, 20, 6, 4, 1, 1, 17, 11, 3, 1, 25, 27, 11, 1, 20, 6, 4, 1, 1, 24, 30, 8, 1, 1, 24, 30, 8, 1, 1, 21, 35, 7 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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.

Number of entries in row n = 1 + number of vertices in the largest independent vertex subset = 1 + A212625(n).

Sum of entries in row n = 2^{V(n)}, where V(n)=A061775(n) is the number of nodes in the rooted tree with Matula-Goebel number n.

REFERENCES

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 Y-N. 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 Review, 10, 1968, 273.

P. Tittmann, I. Averbuch, and J. A. Makowsky, The enumeration of vertex induced subgraphs with respect to the number of components, Eur. J. Combinatorics, 32, 2011, 954-974.

LINKS

Table of n, a(n) for n=1..84.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.

FORMULA

Following the Tittmann et al. reference, for a tree T we introduce the bivariate generating polynomial Q(T;x,y) of the vertex subsets A of T with respect to number of vertices in A (marked by x) and the number of induced connected components (marked by y). For example, for the path P_3 = abc we have Q(P_3;x,y) = 1 + xy + xy + xy + x^2*y^2 + yx^2 + yx^2 + y*x^3, the terms corresponding to the vertex subsets empty, a, b, c, ac, ab, bc, and abc, respectively. For a rooted tree T, instead of Q(T;x,y) we shall write Q(n), where n is the Matula-Goebel number of T. We break up Q(n) into Q'(n) and Q"(n), referring to vertex subsets containing and not containing the root, respectively. Obviously, Q(n) = Q'(n) + Q"(n).  We have Q'(1)=xy, Q"(1)=1; Q'(t-th prime) = xQ'(t) + xyQ"(t), Q"(t-th prime) = Q'(t) + Q"(t); if n=rs (r,s>=2), then Q'(n) = Q'(r)Q'(s)/(xy), Q"(n) = Q"(r)Q"(s) (see Theorem 25 in the Tittmann et al. reference). The Maple program is based on these recurrence relations.  The command Q(n) yields the bivariate generating polynomial; p(n) yields the generating polynomial of row n.

EXAMPLE

a(5,2)=5 because the rooted tree with Matula-Goebel number 5 is the path P_4 = abcd and the vertex subsets with 2 components in the induced subgraph are: ac, bd, ad, abd, and acd.

Triangle starts:

1,1;

1,3;

1,6,1;

1,6,1;

1,10,5;

1,10,5;

1,11,3,1;

MAPLE

with(numtheory): r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: G := proc (n) if n = 1 then [x*y, 1] elif bigomega(n) = 1 then [expand(x*G(pi(n))[1]+x*y*G(pi(n))[2]), expand(G(pi(n))[1]+G(pi(n))[2])] else [expand(G(r(n))[1]*G(s(n))[1]/(x*y)), expand(G(r(n))[2]*G(s(n))[2])] end if end proc: Q := proc (n) options operator, arrow: G(n)[1]+G(n)[2] end proc: p := proc (n) options operator, arrow: sort(subs(x = 1, Q(n))) end proc: for n to 25 do seq(coeff(p(n), y, k), k = 0 .. degree(p(n))) end do; # yields sequence in triangular form

CROSSREFS

Cf. A212625, A061775.

Sequence in context: A317855 A301331 A301333 * A116609 A124846 A177375

Adjacent sequences:  A213667 A213668 A213669 * A213671 A213672 A213673

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jul 15 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 11:35 EDT 2021. Contains 342845 sequences. (Running on oeis4.)