cp's OEIS Frontend

A124593 Number of 4-indecomposable trees with n nodes.

%I A124593 #15 Nov 16 2016 12:47:18
%S A124593 1,1,1,1,2,3,6,11,13,17,23,27,33,42,48,57,69,78,90,106,118,134,154,
%T A124593 170,190,215,235,260,290,315,345,381,411,447,489,525,567,616,658,707,
%U A124593 763,812,868,932,988,1052,1124,1188,1260,1341,1413,1494,1584,1665,1755,1855,1945
%N A124593 Number of 4-indecomposable trees with n nodes.
%C A124593 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.
%C A124593 Every connected graph with < 2k nodes is automatically k-indecomposable.
%C A124593 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.
%C A124593 From _Brendan McKay_, Feb 15 2007: (Start)
%C A124593 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}.
%C A124593 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)
%C A124593 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.
%H A124593 Colin Barker, <a href="/A124593/b124593.txt">Table of n, a(n) for n = 0..1000</a>
%H A124593 <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,-2,-2,1,1,1,-1).
%F A124593 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.
%e A124593 Rather than show some 4-indecomposable trees, instead we show all four 3-indecomposable trees with 7 nodes:
%e A124593 O-O-O-O-O....O..........O.O...O...O
%e A124593 ....|........|..........|/.....\./.
%e A124593 ....O....O-O-O-O-O..O-O-O-O...O-O-O
%e A124593 ....|........|..........|....../.\.
%e A124593 ....O........O..........O.....O...O
%e A124593 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.
%o A124593 (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
%Y A124593 Cf. A000055, A125709.
%K A124593 nonn,easy
%O A124593 0,5
%A A124593 _David Applegate_ and _N. J. A. Sloane_, Feb 14 2007, extended with generating function Feb 25 2007