A303330 a(n) is the number of noncrossing path sets on 3*n nodes up to rotation and reflection with each path having exactly 3 nodes.

1, 1, 4, 22, 201, 2244, 29096, 404064, 5915838, 89918914, 1408072452, 22585364697, 369552118682, 6148989874890, 103788529623864, 1773645405777098, 30638842342771863, 534324445644633987, 9397210553851138484, 166518651072771792918, 2970743502941350443069

Offset: 0

Author

J. Stauduhar, Apr 21 2018

Keywords

• nonn

Comments

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Math StackExchange, Question from user Matan at math.stackexchange.com: Number of ways to connect sets of k dots in a perfect n-gon

Crossrefs

Column k=3 of A302828.

Cf. A303839, A303865, A303867.

Programs

Mathematica

seq[n_] := Module[{p, h, q, c}, p = 1 + InverseSeries[x/(3*(1 + x)^3) + O[x]^n , x]; h = (p /. x -> x^2 + O[x]^n); q = x*D[p, x]/p; c = Integrate[((p - 1)/3 + Sum[EulerPhi[d]*(q /. x -> x^d + O[x]^n), {d, 2, n}])/x, x]; CoefficientList[1 + c + (1 + h + x^2*h^3 + x*2*h^2)/2, x]/2];
seq[30] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)

PARI

seq(n)={
my(p=1 + serreverse( x/(3*(1 + x)^3) + O(x*x^n) ));
my(h=subst(p, x, x^2 + O(x*x^n)), q=x*deriv(p)/p);
my(c=intformal(((p-1)/3 + sum(d=2, n, eulerphi(d)*subst(q, x, x^d+O(x*x^n))))/x));
Vec(1 + c + (1 + h + x^2*h^3 + x*2*h^2)/2)/2} \\ Andrew Howroyd, Apr 29 2018

Formula

a(n) ~ 3^(4*n - 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 3)). - Vaclav Kotesovec, Jun 01 2022

Extensions

Terms a(8) and beyond from Andrew Howroyd, Apr 29 2018

a(6) corrected by Andrew Howroyd, May 03 2018