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

%I #23 Aug 25 2024 16:14:56

%S 1,1,2,5,10,32,64,231,462,1792,3584,14586,29172,122880,245760,1062347,

%T 2124694,9371648,18743296,84021990,168043980,763363328,1526726656,

%U 7012604550,14025209100,65028489216,130056978432,607892634420

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

%C 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).

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.

%H M. R. Sepanski, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p32">On Divisibility of Convolutions of Central Binomial Coefficients</a>, Electronic Journal of Combinatorics, 21 (1) 2014, #P1.32.

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

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

%F 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

%e 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).

%p 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);

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

%t Array[a, 28] (* _Jean-François Alcover_, Jul 29 2018 *)

%Y Cf. A078531.

%K nonn

%O 1,3

%A _Emeric Deutsch_, Dec 04 2003

%E Name edited by _Michel Marcus_, Jul 30 2018