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).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (5,-3,1).
FORMULA
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