A110886 Number of signed weighted Euler trees with total weight n (associated to even switching classes of matrices of order 2n).

1, 1, 3, 8, 27, 104, 436, 1930, 8871, 41916, 202300, 992942, 4940912, 24867870, 126371426, 647494746, 3341341155, 17350565376, 90593056624, 475333630402, 2504959102224, 13252904123786, 70366654738470, 374824160997086

Offset: 0

Author

David Garber, Sep 19 2005

Keywords

• nonn

Examples

			a(5) = 104. (1, 3, 8, 27) dot (1, 2, 5, 19) = 77; then 104 = a(4) + 77 = 27 + 77.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..300
• R. Bacher and D. Garber, Spindle-configurations of skew lines, Geom. Topol 11 (2007) 1049.

Programs

Maple

G:=(3*(1-z)-sqrt((1-z)*(1-5*z-4*z^2)))/2/(1-z): Gser:=series(G,z=0,32): seq(coeff(Gser,z,n),n=0..27); # Emeric Deutsch, Dec 31 2006

Mathematica

CoefficientList[Series[(3*(1-x)-Sqrt[(1-x)*(1-5*x-4*x^2)])/2/(1-x), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 18 2012 *)
a[n_] := Sum[(Binomial[2*k-2, k-1]*Sum[Binomial[k, n-k-i]*Binomial[k+i-1, k-1], {i, 0, n-k}])/k, {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jan 24 2013, after Vladimir Kruchinin *)

Maxima

a(n):=sum((binomial(2*k-2,k-1)*sum(binomial(k,n-k-i)*binomial(k+i-1,k-1),i,0,n-k))/k,k,1,n); /* Vladimir Kruchinin, Jan 24 2013 */

PARI

N = 66;  x = 'x + O('x^N);
gf =  ( 3*(1-x)-sqrt((1-x)*(1-5*x-4*x^2))  ) / (2*(1-x));
v = Vec(gf)
/* Joerg Arndt, Jan 24 2013 */

Formula

G.f.: ( 3*(1-z)-sqrt((1-z)*(1-5*z-4*z^2)) ) / (2*(1-z)).

a(n) = 2 + Sum_{k=1..n-1} a(n-k)*a(k). - Benoit Cloitre, Jul 27 2008

Recurrence: n*a(n) = 2*(3*n-4)*a(n-1) - (n+2)*a(n-2) - 2*(2*n-7)*a(n-3). - Vaclav Kotesovec, Oct 18 2012

a(n) ~ sqrt(41-3*sqrt(41))*((5+sqrt(41))/2)^n/(16*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 18 2012

a(n) = Sum_{k=1..n} (binomial(2*k-2, k-1)*Sum_{i=0..n-k} binomial(k, n-k-i)*binomial(k+i-1, k-1)/k), n > 0, a(0)=1. - Vladimir Kruchinin, Jan 24 2013

a(n+1) starting (1, 3, ...) = (first n terms) dot product (first n difference terms), added to a(n). - Gary W. Adamson, May 20 2013

Extensions

More terms from Emeric Deutsch, Dec 31 2006