A303730 Number of noncrossing path sets on n nodes with each path having at least two nodes.

1, 0, 1, 3, 10, 35, 128, 483, 1866, 7344, 29342, 118701, 485249, 2001467, 8319019, 34810084, 146519286, 619939204, 2635257950, 11248889770, 48198305528, 207222648334, 893704746508, 3865335575201, 16761606193951, 72860178774410, 317418310631983, 1385703968792040

Offset: 0

Author

Andrew Howroyd, Apr 29 2018

Keywords

• nonn

Comments

Paths are constructed using noncrossing line segments between the vertices of a regular n-gon. Isolated vertices are not allowed.

A noncrossing path set is a noncrossing forest (A054727) where each tree is restricted to being a path.

Examples

			Case n=3: There are 3 possibilities:
.
     o       o       o
    /         \     / \
   o---o   o---o   o   o
.
Case n=4: There are 10 possibilities:
.
   o   o   o   o   o---o   o---o   o---o
   |   |   |   |   |       |   |       |
   o   o   o---o   o---o   o   o   o---o
.
   o---o   o---o   o---o   o   o   o   o
             /       \     | / |   | \ |
   o---o   o---o   o---o   o   o   o   o
.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.

Crossrefs

Cf. A054727, A303729.

Programs

Mathematica

InverseSeries[x*(1 - 2*x)^2/(1 - 4*x + 5*x^2 - x^3) + O[x]^30, x] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Jul 03 2018, from PARI *)

PARI

Vec(serreverse(x*(1 - 2*x)^2/(1 - 4*x + 5*x^2 - x^3) + O(x^30)))

Formula

G.f.: G(x)/x where G(x) is the reversion of x*(1 - 2*x)^2/(1 - 4*x + 5*x^2 - x^3).