A303330 - OEIS

%I #27 Jun 01 2022 06:01:58

%S 1,1,4,22,201,2244,29096,404064,5915838,89918914,1408072452,

%T 22585364697,369552118682,6148989874890,103788529623864,

%U 1773645405777098,30638842342771863,534324445644633987,9397210553851138484,166518651072771792918,2970743502941350443069

%N 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.

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

%H Andrew Howroyd, <a href="/A303330/b303330.txt">Table of n, a(n) for n = 0..200</a>

%H Math StackExchange, <a href="https://math.stackexchange.com/questions/1294224/">Question from user Matan at math.stackexchange.com: Number of ways to connect sets of k dots in a perfect n-gon</a>

%F a(n) ~ 3^(4*n - 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 3)). - _Vaclav Kotesovec_, Jun 01 2022

%t 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];

%t seq[30] (* _Jean-François Alcover_, Jul 05 2018, after _Andrew Howroyd_ *)

%o (PARI)

%o seq(n)={

%o my(p=1 + serreverse( x/(3*(1 + x)^3) + O(x*x^n) ));

%o my(h=subst(p, x, x^2 + O(x*x^n)), q=x*deriv(p)/p);

%o my(c=intformal(((p-1)/3 + sum(d=2, n, eulerphi(d)*subst(q, x, x^d+O(x*x^n))))/x));

%o Vec(1 + c + (1 + h + x^2*h^3 + x*2*h^2)/2)/2} \\ _Andrew Howroyd_, Apr 29 2018

%Y Column k=3 of A302828.

%Y Cf. A303839, A303865, A303867.

%K nonn

%O 0,3

%A _J. Stauduhar_, Apr 21 2018

%E Terms a(8) and beyond from _Andrew Howroyd_, Apr 29 2018

%E a(6) corrected by _Andrew Howroyd_, May 03 2018