The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 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: A301331 A301333 A347231 * 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 02:45 EST 2023. Contains 367717 sequences. (Running on oeis4.)