A087457 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).

1, 5, 31, 213, 1551, 11723, 90945, 719253, 5773279, 46889355, 384487665, 3177879675, 26442188865, 221278343445, 1860908156031, 15717475208853, 133256583398655, 1133591857814363, 9672323357640129, 82752014457666363, 709719620585186529, 6100394753270329605

Offset: 1

Author

B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Oct 23 2003

Keywords

• nonn

Examples

			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
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 2nd ed. 1998, see page number?

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..1052 (terms 1..100 from T. D. Noe)

Crossrefs

Cf. A086617, A086618, A002893.

Programs

Maple

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;
# Alternative:
a := n -> hypergeom([1/2, -n, -n], [1, 1], 4)/3;
seq(simplify(a(n)), n = 1..22);  # Peter Luschny, Nov 06 2023

Mathematica

Table[Sum[Binomial[n,k]^2*Binomial[2k,k],{k,0,n}]/3,{n,1,20}] (* Vaclav Kotesovec, Oct 14 2012 *)

PARI

a(n) = sum(k=0, n, binomial(n,k)^2*binomial(2*k,k))/3; \\ Michel Marcus, May 10 2020

Formula

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

a(n) = A002893(n)/3 = (1/3)*Sum_{k=0..n}binomial(n,k)^2*binomial(2k,k). - Philippe Deléham, Sep 14 2008

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

a(n) ~ 3^(2*n+1/2)/(4*Pi*n). - Vaclav Kotesovec, Oct 14 2012

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

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

a(n) = hypergeom([1/2, -n, -n], [1, 1], 4) / 3. - Peter Luschny, Nov 06 2023