login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A238414 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
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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,19

COMMENTS

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

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.

This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - Andrew Howroyd, Dec 17 2020

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Eric Weisstein's World of Mathematics, Maximum Vertex Degree

FORMULA

T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - Andrew Howroyd, Dec 17 2020

EXAMPLE

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.

Triangle starts:

  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, 1, 1;

  0, 0, 1, 17, 17, 7, 3, 1, 1;

  ...

MAPLE

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

PROG

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

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

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

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])))}

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

CROSSREFS

Row sums are A000055.

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

Sequence in context: A204242 A211313 A321609 * A195151 A271024 A125208

Adjacent sequences:  A238411 A238412 A238413 * A238415 A238416 A238417

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Mar 05 2014

EXTENSIONS

Columns k=0..1 inserted by Andrew Howroyd, Dec 18 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 26 19:25 EDT 2022. Contains 354885 sequences. (Running on oeis4.)