cp's OEIS Frontend

A361358 Expansion of x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).

%I A361358 #19 Jul 20 2024 15:46:25
%S A361358 2,9,39,170,742,3239,14139,61720,269422,1176089,5133899,22410650,
%T A361358 97827642,427040159,1864128519,8137349760,35521403402,155059096249,
%U A361358 676868620799,2954687218650,12897889327102,56302253600359,245772287239139,1072852564721720
%N A361358 Expansion of x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).
%C A361358 This sequence arises in the enumeration of noncrossing caterpillar graphs (A361356). Given a directed edge (A,B) on the spine of the caterpillar where B is not a leaf node, then a(n) is the number of ways to complete the caterpillar using at most n nodes. Nodes cannot be added to A. Equivalently, a(n) is the number of ways to complete the caterpillar using exactly n nodes allowing leaves to be added to the left of A (but not to the right).
%H A361358 Andrew Howroyd, <a href="/A361358/b361358.txt">Table of n, a(n) for n = 1..1000</a>
%H A361358 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-3,1).
%F A361358 a(n) = 5*a(n-1) - 3*a(n-2) + a(n-3) for n > 3.
%F A361358 a(n) = 2*A200676(n+2) - A200676(n+1).
%F A361358 G.f. A(x) satisfies A(x) = x*(2 - x + 2*A(x))/(1 - x)^3.
%e A361358 In the following examples, o is a leaf and 1..n+1 is the spine.
%e A361358 a(1) = 2, a leaf can be added to the left or to the right of the spine:
%e A361358    1---2    1  o
%e A361358        |     \ |
%e A361358        o       2
%e A361358 .
%e A361358 a(2) = a(1) + 7:
%e A361358    1---2   1---2    1---2    1   o    1   3    1   o   1   o
%e A361358      /         |      / |      \ |    | / |    |   |   | /
%e A361358    3---o   o---3    o   o    o---2    2   o    2---3   2---o
%t A361358 LinearRecurrence[{5, -3, 1}, {2, 9, 39}, 30] (* _Paolo Xausa_, Jul 20 2024 *)
%o A361358 (PARI) Vec(x*(2 - x)/(1 - 5*x + 3*x^2 - x^3) + O(x^25))
%Y A361358 Cf. A361356, A361359, A361360.
%K A361358 nonn,easy
%O A361358 1,1
%A A361358 _Andrew Howroyd_, Mar 09 2023