Search: id:a213670
|
|
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).
|
|
+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
|
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
|
|
MATHEMATICA
|
r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
G[n_] := Which[n == 1, {x*y, 1}, PrimeOmega[n] == 1, {x*G[PrimePi[n]][[1]] + x*y*G[PrimePi[n]][[2]], G[PrimePi[n]][[1]] + G[PrimePi[n]][[2]]}, True, {G[r[n]][[1]]*G[s[n]][[1]]/(x*y), G[r[n]][[2]]*G[s[n]][[2]]}];
Q[n_] := G[n][[1]] + G[n][[2]];
p[n_] := Q[n] /. x -> 1;
T[n_] := CoefficientList[p[n], y];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.005 seconds
|