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,4

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.

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.

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

Example

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
.

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

Prog

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

Crossrefs

Cf. A054727, A303729.

Sequence in context: A078789 A299443 A128736 * A149037 A228769 A361768

Adjacent sequences: A303727 A303728 A303729 * A303731 A303732 A303733

Keyword

nonn

Author

Andrew Howroyd, Apr 29 2018

Status

approved