A221957 Number of n X n rook placements avoiding the pattern 012.

1, 2, 7, 31, 159, 921, 5988, 43632, 355491, 3223729, 32329668, 355979064, 4273100846, 55555511298, 777797216472, 11667035805840, 186672873433635, 3173440015174905, 57121924810715940, 1085316589076234760, 21706331850447959610, 455832969128536089030

Offset

0,2

Links

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

Dan Daly and Lara Pudwell, Pattern avoidance in rook monoids, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013.

Formula

From Vaclav Kotesovec, Feb 07 2013: (Start)

E.g.f.: 1/2*(exp(2*x)*BesselI(0,2*x)+1)/(1-x).

Recurrence: n*a(n) = (n^2+4*n-2)*a(n-1)-2*(n-1)*(2*n-1)*a(n-2).

a(n) ~ c * n!, where c = (exp(2)*BesselI(0,2)+1)/2 = 8.921991840629494...

(End)

c = 1 + Sum_{k>=0} binomial(2*k+1,k) / (k+1)!. - Vaclav Kotesovec, Jul 19 2021

Mathematica

CoefficientList[Series[1/2*(Exp[2*x]*BesselI[0, 2*x]+1)/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Feb 07 2013 *)

Prog

(PARI) a(n) = {sum(k=0, n, if (k==n, n!, sum(j=1, k+1, binomial(n-j, n-k-1)*binomial(n, k)*binomial(k, j-1)*(j-1)!))); } \\ Michel Marcus, Feb 07 2013

Crossrefs

Sequence in context: A030882 A273957 A221958 * A030966 A009132 A125275

Adjacent sequences: A221954 A221955 A221956 * A221958 A221959 A221960

Keyword

nonn

Author

N. J. A. Sloane, Feb 04 2013

Extensions

More terms from Michel Marcus, Feb 07 2013

Status

approved