A078483 G.f.: -2*x/(1 - 5*x - sqrt(1-4*x) + x*sqrt(1-4*x) + 2*x^2).

1, 1, 2, 6, 20, 69, 243, 869, 3145, 11491, 42312, 156807, 584288, 2187298, 8221257, 31009841, 117331070, 445174418, 1693270531, 6454992143, 24657428519, 94363587324, 361741068087, 1388892123038, 5340282880156, 20560742443041, 79259430563491, 305889059254747

Offset

0,3

Comments

Number of data structures of a certain wreath product type.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.

M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.

Formula

From Gary W. Adamson, Jul 14 2011: (Start)

a(n) is the upper left term in M^n, where M is the following infinite square production matrix:

1, 1, 0, 0, 0, 0, ...

1, 2, 1, 0, 0, 0, ...

1, 1, 1, 1, 0, 0, ...

1, 1, 1, 1, 1, 0, ...

1, 1, 1, 1, 1, 1, ...

... (End)

a(n) = 1 + Sum_{m=1..n} m*Sum_{k=1..n-m} (1/(m+k)) * ((Sum_{j=0..m+k} binomial(j,-2*m-k+2*j)*binomial(m+k,j))*binomial(n-m-1,k-1)). - Vladimir Kruchinin, Oct 11 2011

G.f.: 1/(1 - (x + x^2 * C(x)^3)) where C(x) = (1-sqrt(1-4*x))/(2*x) is the g.f. for the Catalan numbers A000108. - David Callan, Feb 06 2016

a(n) ~ 3 * 2^(2*n + 2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 20 2019

Conjecture D-finite with recurrence: n*a(n) +2*(-5*n+4)*a(n-1) +3*(11*n-18)*a(n-2) +(-41*n+102)*a(n-3) +(21*n-64)*a(n-4) +2*(-2*n+7)*a(n-5)=0. - R. J. Mathar, Jan 23 2020

Mathematica

catGF = (1 - Sqrt[1 - 4 x])/(2 x); CoefficientList[Normal[Series[1/(1 - (x + x^2 catGF^3)), {x, 0, 20}]], x] (* David Callan, Feb 06 2016 *)
CoefficientList[Series[-2 x / (1 - 5 x - Sqrt[1 - 4 x] + x Sqrt[1 - 4 x] + 2 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, May 28 2016 *)

Prog

(Maxima)
a(n):=sum(m*sum(((sum(binomial(j, -2*m-k+2*j)*binomial(m+k, j), j, 0, m+k))*binomial(n-m-1, k-1))/(m+k), k, 1, n-m), m, 1, n)+1; // Vladimir Kruchinin, Oct 11 2011

Crossrefs

Cf. A006318, A078482.

Sequence in context: A094854 A217782 A026029 * A363812 A163135 A359463

Adjacent sequences: A078480 A078481 A078482 * A078484 A078485 A078486

Keyword

nonn

Author

N. J. A. Sloane, Jan 04 2003

Extensions

Replaced definition with g.f. given by Atkinson and Still (2002). - N. J. A. Sloane, May 24 2016

Status

approved