A089073 Number of symmetric non-crossing connected graphs on n equidistant nodes on a circle.

1, 1, 2, 5, 10, 32, 64, 231, 462, 1792, 3584, 14586, 29172, 122880, 245760, 1062347, 2124694, 9371648, 18743296, 84021990, 168043980, 763363328, 1526726656, 7012604550, 14025209100, 65028489216, 130056978432, 607892634420

Offset: 1

Author

Emeric Deutsch, Dec 04 2003

Keywords

• nonn

Comments

Number of symmetric non-crossing connected graphs on n equidistant nodes on a circle (it is assumed that the axis of symmetry is a diameter of the circle passing through a given node).

Examples

			a(4)=5 because on the nodes A,B,C,D (axis of symmetry through A) the only symmetric non-crossing connected graphs are (AB,AC,AD), (AC,BC,DC), (AB,BC,CD,DA), (AB,BC,CD,DA,BD), (AB,BC,CD,DA,AC).
		

Links

• P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
• M. R. Sepanski, On Divisibility of Convolutions of Central Binomial Coefficients, Electronic Journal of Combinatorics, 21 (1) 2014, #P1.32.

Crossrefs

Cf. A078531.

Programs

Maple

a := proc(n) if n mod 2 = 0 then 4^(n/2)*binomial((3*(n/2)-1)/2,n/2)/2/(n/2+1) else 2*4^((n-1)/2)*binomial((3*((n-1)/2)-1)/2,(n-1)/2)/2/((n-1)/2+1) fi end; seq(a(n), n=1..30);

Mathematica

a[n_] := If[EvenQ[n], 2^n Binomial[(3n-2)/4, n/2]/(n+2), 2^n Binomial[ (3n-5)/4, (n-1)/2]/(n+1)];
Array[a, 28] (* Jean-François Alcover, Jul 29 2018 *)

Formula

a(2k) = 4^k*binomial((3k-1)/2, k)/[2(k+1)], a(2k+1) = 2a(2k).

a(2k) = (1/2)A078531(k), a(2k+1) = A078531(k).

Conjecture D-finite with recurrence n*(n+2)*(23*n^2-162*n+199) *a(n) +12*(27*n^2-47*n-10) *a(n-1) +24*(-27*n^2+47*n+10) *a(n-2) +48 *(27*n^2-47*n-10) *a(n-3) -12*(3*n-13)*(3*n-5)*(23*n^2-116*n+60) *a(n-4)=0. - R. J. Mathar, Jul 22 2022

Extensions

Name edited by Michel Marcus, Jul 30 2018