|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
