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

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

Author

Andrew Howroyd, Mar 09 2023

Keywords

• nonn
• easy

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).

Examples

			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
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (5,-3,1).

Crossrefs

Cf. A361356, A361359, A361360.

Programs

Mathematica

LinearRecurrence[{5, -3, 1}, {2, 9, 39}, 30] (* Paolo Xausa, Jul 20 2024 *)

PARI

Vec(x*(2 - x)/(1 - 5*x + 3*x^2 - x^3) + O(x^25))

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.