login
A303730
Number of noncrossing path sets on n nodes with each path having at least two nodes.
4
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
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
Sequence in context: A078789 A299443 A128736 * A149037 A228769 A361768
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Apr 29 2018
STATUS
approved