cp's OEIS Frontend

A240159 Triangle read by rows: T(n,k) = number of trees with n vertices and k segments (n >= 2; 1 <= k <= n-1).

%I A240159 #15 Sep 13 2024 08:12:08
%S A240159 1,1,0,1,0,1,1,0,1,1,1,0,2,1,2,1,0,3,2,3,2,1,0,4,3,7,4,4,1,0,5,5,12,
%T A240159 10,9,5,1,0,7,6,22,20,25,15,10,1,0,8,9,34,38,54,46,31,14,1,0,10,11,53,
%U A240159 65,114,111,103,57,26,1,0,12,15,76,108,212,250,267,204,114,42,1,0,14,18,110,167,383,502,644,583,440,219,78
%N A240159 Triangle read by rows: T(n,k) = number of trees with n vertices and k segments (n >= 2; 1 <= k <= n-1).
%C A240159 A segment of a tree is a path-subtree whose terminal vertices are branching or pendent vertices of the tree. A pendent vertex is a vertex of degree 1; a branching vertex is a vertex of degree >=3.
%C A240159 The author has no formula for obtaining the terms of the sequence. The first Maple program yields the number of segments of a tree identified by the Matula number of any of its associated rooted trees. The second program, making use of the set M of M-indices of the trees with n vertices (given in A235111 for n<=12), yields row n of the triangle. The M-index of a tree is the smallest of the Matula numbers of its associated rooted trees. In the Maple program given below we have n=7.
%F A240159 Sum of entries in row n = A000055(n) = number of trees with n vertices.
%F A240159 T(n,n-1) = A000014(n) = number of reduced trees with n vertices.
%e A240159 Row 4 is 1, 0, 1. Indeed, there are 2 trees with 4 vertices: the path P_4 having 1 segment and the star S_4 having 3 segments.
%e A240159 Triangle begins:
%e A240159   1;
%e A240159   1,0;
%e A240159   1,0,1;
%e A240159   1,0,2,1,2;
%e A240159   1,0,3,2,3,2;
%p A240159 with(numtheory): seg := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow; n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 and bigomega(pi(n)) = 1 then seg(pi(n)) elif bigomega(n) = 1 and bigomega(pi(n)) = 2 then seg(pi(n))+2 elif bigomega(n) = 1 then seg(pi(n))+1 elif bigomega(r(n)) = 1 and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n))-1 elif bigomega(r(n)) = 1 and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+1 elif bigomega(r(n)) = 2 and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n))+1 elif bigomega(r(n)) = 2 and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+2 elif bigomega(r(n)) = 1 and 2 < bigomega(s(n)) then seg(r(n))+seg(s(n)) elif 2 < bigomega(r(n)) and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n)) elif bigomega(r(n)) = 2 and 2 < bigomega(s(n)) then seg(r(n))+seg(s(n))+1 elif 2 < bigomega(r(n)) and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+1 else seg(r(n))+seg(s(n)) end if end proc:
%p A240159 M := {25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64}: P := sort(add(x^seg(M[i]), i = 1 .. nops(M))): seq(coeff(P, x, j), j = 1 .. 6);
%t A240159 r[n_] := FactorInteger[n][[1, 1]];
%t A240159 s[n_] := n/r[n];
%t A240159 seg[n_] := Which[n == 1, 0,
%t A240159   PrimeOmega[n] == 1 && PrimeOmega[PrimePi[n]] == 1, seg[PrimePi[n]],
%t A240159   PrimeOmega[n] == 1 && PrimeOmega[PrimePi[n]] == 2, seg[PrimePi[n]]+2,
%t A240159   PrimeOmega[n] == 1, seg[PrimePi[n]]+1,
%t A240159   PrimeOmega[r[n]] == 1 && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]]-1,
%t A240159   PrimeOmega[r[n]] == 1 && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+1,
%t A240159   PrimeOmega[r[n]] == 2 && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]]+1,
%t A240159   PrimeOmega[r[n]] == 2 && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+2,
%t A240159   PrimeOmega[r[n]] == 1 && 2 < PrimeOmega[s[n]], seg[r[n]] + seg[s[n]],
%t A240159   2 < PrimeOmega[r[n]] && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]],
%t A240159   PrimeOmega[r[n]] == 2 && 2 < PrimeOmega[s[n]], seg[r[n]] + seg[s[n]]+1,
%t A240159   2 < PrimeOmega[r[n]] && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+1,
%t A240159   True, seg[r[n]] + seg[s[n]]];
%t A240159 M = {25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64};
%t A240159 (* M is row[7] in A235111 *)
%t A240159 P = Sort[Sum[x^seg[M[[i]]], {i, 1, Length[M]}]];
%t A240159 Table[Coefficient[P, x, j], {j, 1, 6}] (* _Jean-François Alcover_, Sep 10 2024, after Maple program *)
%Y A240159 Cf. A000014, A000055, A235111.
%K A240159 nonn,tabl
%O A240159 2,13
%A A240159 _Emeric Deutsch_, Apr 02 2014