login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A240159 Triangle read by rows: T(n,k) = number of trees with n vertices and k segments (n >= 2; 1 <= k <= n-1). 0
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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,13

COMMENTS

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.

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.

LINKS

Table of n, a(n) for n=2..92.

FORMULA

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

T(n,n-1) = A000014(n) = number of reduced trees with n vertices.

EXAMPLE

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.

Triangle begins:

1;

1,0;

1,0,1;

1,0,2,1,2;

1,0,3,2,3,2;

MAPLE

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:

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

CROSSREFS

Cf. A000014, A000055, A235111.

Sequence in context: A079532 A328176 A191312 * A309447 A320312 A269942

Adjacent sequences:  A240156 A240157 A240158 * A240160 A240161 A240162

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Apr 02 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 10 21:08 EDT 2021. Contains 343780 sequences. (Running on oeis4.)