

A124593


Number of 4indecomposable trees with n nodes.


5



1, 1, 1, 1, 2, 3, 6, 11, 13, 17, 23, 27, 33, 42, 48, 57, 69, 78, 90, 106, 118, 134, 154, 170, 190, 215, 235, 260, 290, 315, 345, 381, 411, 447, 489, 525, 567, 616, 658, 707, 763, 812, 868, 932, 988, 1052, 1124, 1188, 1260, 1341, 1413, 1494, 1584, 1665, 1755, 1855, 1945
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

A connected graph is called kdecomposable if it is possible to remove some edges and leave a graph with at least two connected components in which every component has at least k nodes.
Every connected graph with < 2k nodes is automatically kindecomposable.
Necessary conditions are that a 4indecomposable tree may not contain a path with >= 8 nodes, nor two nodedisjoint paths with >= 4 nodes each.
From Brendan McKay, Feb 15 2007: (Start)
A necessary and sufficient condition seems to be that there are no two nodedisjoint subtrees each of which is P_4 or K_{1,3}.
Alternatively, a tree with n vertices is kdecomposable iff, for each edge, removing that edge leaves a component with at most k1 vertices. Finding the maximal k such that a tree is kdecomposable is easy to do in linear time. (End)
The counts of 1indecomposable (1,0,0,0,...), 2indecomposable (1,1,1,1,1,1,...) or 3indecomposable (1,1,1,2,3,3,4,4,5,5,6,6,7,7,...) trees with number of nodes = 1,2,3,4,... are all trivial.


LINKS

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1,2,2,1,1,1,1).


FORMULA

G.f.: f(x) / ((1x)*(1x^2)*(1x^3)^2) where f(x) = 1  x^2  2*x^3 + x^4 + 3*x^5 + 3*x^6 + 2*x^7  4*x^8  5*x^9  3*x^10 + 3*x^11 + 4*x^12 + x^13  x^14  x^15.


EXAMPLE

Rather than show some 4indecomposable trees, instead we show all four 3indecomposable trees with 7 nodes:
OOOOO....O..........O.O...O...O
....................../.....\./.
....O....OOOOO..OOOO...OOO
............................/.\.
....O........O..........O.....O...O
On the other hand, OOOOOOO is 3decomposable, because removing the third edge gives OOO OOOO, with 2 connected components each with >= 3 nodes.


PROG

(PARI) Vec((1 x^2 2*x^3 +x^4 +3*x^5 +3*x^6 +2*x^7 4*x^8 5*x^9 3*x^10 +3*x^11 +4*x^12 +x^13 x^14 x^15) / ((1 x)^4*(1 +x)*(1 +x +x^2)^2) + O(x^50)) \\ Colin Barker, May 27 2016


CROSSREFS

Cf. A000055, A125709.
Sequence in context: A105614 A116441 A116051 * A125882 A057758 A057125
Adjacent sequences: A124590 A124591 A124592 * A124594 A124595 A124596


KEYWORD

nonn,easy


AUTHOR

David Applegate and N. J. A. Sloane, Feb 14 2007, extended with generating function Feb 25 2007


STATUS

approved



