login
A361358
Expansion of x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).
4
2, 9, 39, 170, 742, 3239, 14139, 61720, 269422, 1176089, 5133899, 22410650, 97827642, 427040159, 1864128519, 8137349760, 35521403402, 155059096249, 676868620799, 2954687218650, 12897889327102, 56302253600359, 245772287239139, 1072852564721720
OFFSET
1,1
COMMENTS
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).
FORMULA
a(n) = 5*a(n-1) - 3*a(n-2) + a(n-3) for n > 3.
a(n) = 2*A200676(n+2) - A200676(n+1).
G.f. A(x) satisfies A(x) = x*(2 - x + 2*A(x))/(1 - x)^3.
EXAMPLE
In the following examples, o is a leaf and 1..n+1 is the spine.
a(1) = 2, a leaf can be added to the left or to the right of the spine:
1---2 1 o
| \ |
o 2
.
a(2) = a(1) + 7:
1---2 1---2 1---2 1 o 1 3 1 o 1 o
/ | / | \ | | / | | | | /
3---o o---3 o o o---2 2 o 2---3 2---o
MATHEMATICA
LinearRecurrence[{5, -3, 1}, {2, 9, 39}, 30] (* Paolo Xausa, Jul 20 2024 *)
PROG
(PARI) Vec(x*(2 - x)/(1 - 5*x + 3*x^2 - x^3) + O(x^25))
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Mar 09 2023
STATUS
approved