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,3

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.

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

Example

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

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 *)

Prog

(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 */

Crossrefs

Sequence in context: A102318 A102206 A192856 * A104854 A226061 A294197

Adjacent sequences: A110883 A110884 A110885 * A110887 A110888 A110889

Keyword

nonn

Author

David Garber, Sep 19 2005

Extensions

More terms from Emeric Deutsch, Dec 31 2006

Status

approved