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

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A124593 Number of 4-indecomposable 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 k-decomposable 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 k-indecomposable. Necessary conditions are that a 4-indecomposable tree may not contain a path with >= 8 nodes, nor two node-disjoint 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 node-disjoint subtrees each of which is P_4 or K_{1,3}. Alternatively, a tree with n vertices is k-decomposable iff, for each edge, removing that edge leaves a component with at most k-1 vertices. Finding the maximal k such that a tree is k-decomposable is easy to do in linear time. (End) The counts of 1-indecomposable (1,0,0,0,...), 2-indecomposable (1,1,1,1,1,1,...) or 3-indecomposable (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) / ((1-x)*(1-x^2)*(1-x^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 4-indecomposable trees, instead we show all four 3-indecomposable trees with 7 nodes: O-O-O-O-O....O..........O.O...O...O ....|........|..........|/.....\./. ....O....O-O-O-O-O..O-O-O-O...O-O-O ....|........|..........|....../.\. ....O........O..........O.....O...O On the other hand, O-O-O-O-O-O-O is 3-decomposable, because removing the third edge gives O-O-O O-O-O-O, 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

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.

Last modified December 3 08:35 EST 2022. Contains 358515 sequences. (Running on oeis4.)