cp's OEIS Frontend

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).

%I A213670 #19 Jun 26 2024 02:31:29
%S A213670 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,
%T A213670 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,
%U A213670 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
%N 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).
%C A213670 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.
%C A213670 Number of entries in row n = 1 + number of vertices in the largest independent vertex subset = 1 + A212625(n).
%C A213670 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.
%D A213670 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.
%H A213670 Emeric Deutsch, <a href="http://arxiv.org/abs/1111.4288">Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288 [math.CO], 2011.
%H A213670 F. Goebel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.
%H A213670 I. Gutman and A. Ivic, <a href="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.
%H A213670 I. Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publ. Inst. Math., 53 (67), 1993, 17-22.
%H A213670 D. W. Matula, <a href="http://www.jstor.org/stable/2027327">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.
%F A213670 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.
%e A213670 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.
%e A213670 Triangle starts:
%e A213670   1,1;
%e A213670   1,3;
%e A213670   1,6,1;
%e A213670   1,6,1;
%e A213670   1,10,5;
%e A213670   1,10,5;
%e A213670   1,11,3,1;
%e A213670   ...
%p A213670 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
%t A213670 r[n_] := FactorInteger[n][[1, 1]];
%t A213670 s[n_] := n/r[n];
%t A213670 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]]}];
%t A213670 Q[n_] := G[n][[1]] + G[n][[2]];
%t A213670 p[n_] := Q[n] /. x -> 1;
%t A213670 T[n_] := CoefficientList[p[n], y];
%t A213670 Table[T[n], {n, 1, 25}] // Flatten (* _Jean-François Alcover_, Jun 25 2024, after Maple code *)
%Y A213670 Cf. A212625, A061775.
%K A213670 nonn,tabf
%O A213670 1,4
%A A213670 _Emeric Deutsch_, Jul 15 2012