%I #49 Nov 06 2023 11:04:50
%S 1,5,31,213,1551,11723,90945,719253,5773279,46889355,384487665,
%T 3177879675,26442188865,221278343445,1860908156031,15717475208853,
%U 133256583398655,1133591857814363,9672323357640129,82752014457666363,709719620585186529,6100394753270329605
%N Number of odd length roads between any adjacent nodes in virtual optimal chordal ring of degree 3 (the length of chord < number of nodes/2).
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 2nd ed. 1998, see page number?
%H Seiichi Manyama, <a href="/A087457/b087457.txt">Table of n, a(n) for n = 1..1052</a> (terms 1..100 from T. D. Noe)
%F a(1) = 1; a(n) = 9*a(n-1) - 2*A086618(n), where A086618(n) = Sum_{k=0..n} Catalan(n)*binomial(n, k)^2, and Catalan(n) = (2*n)!/(n!*(n+1)!). - _Michael Somos_
%F a(n) = A002893(n)/3 = (1/3)*Sum_{k=0..n}binomial(n,k)^2*binomial(2k,k). - _Philippe Deléham_, Sep 14 2008
%F Recurrence: n^2*a(n) = (10*n^2-10*n+3)*a(n-1) - 9*(n-1)^2*a(n-2). - _Vaclav Kotesovec_, Oct 14 2012
%F a(n) ~ 3^(2*n+1/2)/(4*Pi*n). - _Vaclav Kotesovec_, Oct 14 2012
%F G.f.: (hypergeom([1/3, 1/3],[1],-27*x*(x-1)^2/(9*x-1)^2)/(1-9*x)^(2/3)-1)/3. - _Mark van Hoeij_, May 14 2013
%F G.f.: G(0)/(6*x*(1-9*x)^(2/3) ) -1/(3*x), where G(k)= 1 + 1/(1 - 3*(3*k+1)^2*x*(1-x)^2/(3*(3*k+1)^2*x*(1-x)^2 - (k+1)^2*(1-9*x)^2/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 31 2013
%F a(n) = hypergeom([1/2, -n, -n], [1, 1], 4) / 3. - _Peter Luschny_, Nov 06 2023
%e a(1)=1; a(2)=9*a(1)-2*2=9-4=5; a(3)=9*5-2*7=31; a(4)=9*31-2*33=213; etc
%p a := 1; s := 0; for k from 1 to 10 do for i from 0 to k do ss := ((2*(i))!/((i)!*(i+1)!))*((k)!/((i)!*(k-i)!))^2; s := s+ss; od; a := (9*a-2*s); s := 0; od;
%p # Alternative:
%p a := n -> hypergeom([1/2, -n, -n], [1, 1], 4)/3;
%p seq(simplify(a(n)), n = 1..22); # _Peter Luschny_, Nov 06 2023
%t Table[Sum[Binomial[n,k]^2*Binomial[2k,k],{k,0,n}]/3,{n,1,20}] (* _Vaclav Kotesovec_, Oct 14 2012 *)
%o (PARI) a(n) = sum(k=0, n, binomial(n,k)^2*binomial(2*k,k))/3; \\ _Michel Marcus_, May 10 2020
%Y Cf. A086617, A086618, A002893.
%K nonn
%O 1,2
%A B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Oct 23 2003