login
Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).
4

%I #19 Dec 19 2020 08:01:13

%S 1,0,1,0,0,1,0,0,1,1,0,0,1,1,1,0,0,1,3,1,1,0,0,1,5,3,1,1,0,0,1,10,7,3,

%T 1,1,0,0,1,17,17,7,3,1,1,0,0,1,36,38,19,7,3,1,1,0,0,1,65,93,45,19,7,3,

%U 1,1,0,0,1,134,220,118,47,19,7,3,1,1,0,0,1,264,537,296,125,47,19,7,3,1,1

%N Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

%C Sum of entries in row n is A000055(n) (= number of trees with n vertices).

%C The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196046, from these Matula numbers one obtains the maximum vertex degrees: 2, 3, 3, 3, 4, 4, 3, 5, 3, 4, 6; the frequencies of 2,3,4,5,6 are 1, 5, 3, 1, 1, respectively. See the Maple program.

%C This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - _Andrew Howroyd_, Dec 17 2020

%H Andrew Howroyd, <a href="/A238414/b238414.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)

%H Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumVertexDegree.html">Maximum Vertex Degree</a>

%F T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - _Andrew Howroyd_, Dec 17 2020

%e Row n=4 is T(4,2)=1,T(4,3)=1; indeed, the maximum vertex degree in the path P[4] is 2, while in the star S[4] it is 3.

%e Triangle starts:

%e 1;

%e 0, 1;

%e 0, 0, 1;

%e 0, 0, 1, 1;

%e 0, 0, 1, 1, 1;

%e 0, 0, 1, 3, 1, 1;

%e 0, 0, 1, 5, 3, 1, 1;

%e 0, 0, 1, 10, 7, 3, 1, 1;

%e 0, 0, 1, 17, 17, 7, 3, 1, 1;

%e ...

%p MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := 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 then max(a(pi(n)), 1+bigomega(pi(n))) else max(a(r(n)), a(s(n)), bigomega(r(n))+bigomega(s(n))) end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 2 .. 6);

%o (PARI) \\ Here V(n, k) gives column k of A144528.

%o MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}

%o V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}

%o M(n, m=n)={my(v=vector(m, k, V(n,k-1)[2..1+n]~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}

%o { my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ _Andrew Howroyd_, Dec 18 2020

%Y Row sums are A000055.

%Y Cf. A144528, A196046, A235111, A332760 (connected graphs), A339788 (forests).

%K nonn,tabl

%O 1,19

%A _Emeric Deutsch_, Mar 05 2014

%E Columns k=0..1 inserted by _Andrew Howroyd_, Dec 18 2020