A078483 - OEIS

%I #47 Nov 23 2024 10:09:40

%S 1,1,2,6,20,69,243,869,3145,11491,42312,156807,584288,2187298,8221257,

%T 31009841,117331070,445174418,1693270531,6454992143,24657428519,

%U 94363587324,361741068087,1388892123038,5340282880156,20560742443041,79259430563491,305889059254747

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

%C Number of data structures of a certain wreath product type.

%H Vincenzo Librandi, <a href="/A078483/b078483.txt">Table of n, a(n) for n = 0..1000</a>

%H M. D. Atkinson and T. Stitt, <a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/WreathProduct/Wreathpaper.pdf">Restricted permutations and the wreath product</a>, Preprint, 2002.

%H M. D. Atkinson and T. Stitt, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00443-0">Restricted permutations and the wreath product</a>, Discrete Math., 259 (2002), 19-36.

%F From _Gary W. Adamson_, Jul 14 2011: (Start)

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

%F   1, 1, 0, 0, 0, 0, ...

%F   1, 2, 1, 0, 0, 0, ...

%F   1, 1, 1, 1, 0, 0, ...

%F   1, 1, 1, 1, 1, 0, ...

%F   1, 1, 1, 1, 1, 1, ...

%F   ... (End)

%F 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

%F 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

%F a(n) ~ 3 * 2^(2*n + 2) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jul 20 2019

%F 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

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

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

%o (Maxima)

%o 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 */

%Y Cf. A006318, A078482.

%K nonn,changed

%O 0,3

%A _N. J. A. Sloane_, Jan 04 2003

%E Replaced definition with g.f. given by Atkinson and Still (2002). - _N. J. A. Sloane_, May 24 2016