%I #56 Oct 21 2022 07:02:07
%S 1,1,1,3,10,34,116,396,1353,4631,15895,54757,189465,658835,2303381,
%T 8098783,28642314,101894922,364614216,1312191768,4748561094,
%U 17275277322,63163858146,232041604038,856219298484,3172442815476,11799466553232,44041859928944,164924424558532,619454123593948
%N Necklace Catalan numbers.
%C The n-th term is the number of ways to 'parenthesize' n beads arranged on a necklace. This can be proved.
%F a(n) = 3^(n-2) + (Sum_{i=0..n-4} 3^i*(2*(n-i-3))/((n-i-1)*(n-i))*binomial(2*(n-i-2), n-i-2)), for n >= 4. Initial terms are a(1)=a(2)=1, a(3)=3.
%F a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Oct 22 2018
%F From _Peter Luschny_, Oct 25 2018: (Start)
%F a(n) = (3^(n-2) + (-4)^n*binomial(3/2, n)*((4/3)*n - 2 + hypergeom([1, -n], [5/2 - n], 3/4)))/2) for n >= 3.
%F a(n) = [x^n] (3/2) + (x - sqrt(1 - 4*x))*(2*x - 1)/(6*x - 2). (End)
%F Recurrence: 12*(2*n-7)*(n-4)*a(n-3) + (-158*n^2+744*n-862)*a(n-2) + 2*(n-1)*(79*n-143)*a(n-1) - 6*n*(11*n-9)*a(n) + (n+1)*(13*n+2)*a(n+1) - (n+1)*(n+2)*a(n+2) = 0. - _Georg Fischer_, Oct 21 2022
%p a:=n->`if`(n<=2,1,`if`(n=2,3,3^(n-2)+add((3^i)*(2*(n-i-3))/((n-i-1)*(n-i))*binomial(2*(n-i-2),n-i-2),i=0..n-4))); seq(a(n),n=0..30); # _Muniru A Asiru_, Oct 05 2018
%p # Alternative:
%p ogf := x -> 3/2 + (x - sqrt(1 - 4*x))*(2*x - 1)/(6*x - 2):
%p ser := series(ogf(x),x,32):
%p seq(coeff(ser, x, n), n=0..29); # _Peter Luschny_, Oct 25 2018
%p # Derivation of the recurrence (requires Maple 2022):
%p FormalPowerSeries:-FindRE(3/2 + (x - sqrt(1 - 4*x))*(2*x - 1)/(6*x - 2),x,a(n)); # _Georg Fischer_, Oct 21 2022
%t Flatten[{1, 1, Table[3^(n - 2) + Sum[3^i*2*(n - i - 3)/((n - i - 1)*(n - i)) * Binomial[2*(n - i - 2), n - i - 2], {i, 0, n - 4}], {n, 2, 30}]}] (* _Vaclav Kotesovec_, Oct 22 2018 *)
%o (PARI) a(n) = if (n<=2, 1, if (n==2, 3, 3^(n-2) + sum(i=0, (n-4), (3^i)*(2*(n-i-3))/((n-i-1)*(n-i))*binomial(2*(n-i-2), n-i-2)))); \\ _Michel Marcus_, Oct 05 2018
%o (GAP) Concatenation([1,1,1,3],List([4..30],n->3^(n-2)+(Sum([0..n-4],i->(3^i)*(2*(n-i-3))/((n-i-1)*(n-i))*Binomial(2*(n-i-2),n-i-2))))); # _Muniru A Asiru_, Oct 05 2018
%Y Cf. A320827, A320902.
%K nonn
%O 0,4
%A _Sachin J. Valera_, Oct 05 2018
%E More terms from _Michel Marcus_, Oct 05 2018