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