A059480 - OEIS

%I #39 Apr 19 2024 11:29:53

%S 1,1,4,8,28,76,272,880,3328,12128,48736,194272,827840,3547648,

%T 15965248,72727616,344136832,1653233920,8191833728,41256512128,

%U 213285020416,1120928287232,6026483756800,32928762650368,183590856570368

%N a(0) = a(1) = 1; a(n) = a(n-1) + (n+1)*a(n-2).

%C Number of permutations of order (n+4) that simultaneously avoid the patterns 12-3 and 21-3, start with 1 and end with pattern 12.

%H Harry J. Smith, <a href="/A059480/b059480.txt">Table of n, a(n) for n = 0..200</a>

%H Sergi Elizalde and Yixin Lin, <a href="https://arxiv.org/abs/2404.06585">Penney&#39;s game for permutations</a>, arXiv:2404.06585 [math.CO], 2024. See p. 16.

%H Sergey Kitaev and Toufik Mansour, <a href="https://arxiv.org/abs/math/0209340">On multi-avoidance of generalized patterns</a> arXiv:0209340 [math.CO], 2002.

%F a(n) = a(n - 1) + (n + 1)*a(n - 2); a(0) = a(1) = 1;

%F E.g.f.: (-2*(1+x)+ e^((x*(2+x))/2)*(2+x*(2+x))*(2 +sqrt(2*e*Pi) * erf(1/sqrt(2))) - e^((1+x)^2/2)*sqrt(2*Pi)*(2+x*(2+x)) * erf((1+x)/sqrt(2)))/2.

%F E.g.f.: (with offset 2) exp(x+x^2/2) * (1-integral(exp(-t-t^2/2) dt, t=0..x)) - 1 .

%F a(n) ~ (1/sqrt(2) + sqrt(Pi)/2*exp(1/2) * (erf(1/sqrt(2)) - 1)) * n^(n/2+1)*exp(sqrt(n) - n/2 - 1/4) * (1+31/(24*sqrt(n))). - _Vaclav Kotesovec_, Dec 27 2012

%F a(n) = B(0,n)+B(1,n)+B(2,n)/2+Q(1,n)+Q(2,n)+Q(3,n)/2, n>=4, where B and Q are defined in the Mathematica section below. - _Benedict W. J. Irwin_, Apr 11 2017

%e For n=3, the a(3) = 8 permutations of n+4=7 symbols that satisfy the constraints are: {1,7,2,6,5,3,4},{1,7,3,6,5,2,4},{1,7,4,6,5,2,3},{1,7,5,6,4,2,3},{1,7,6,2,5,3,4},{1,7,6,3,5,2,4},{1,7,6,4,5,2,3} and {1,7,6,5,4,2,3}. - _Olivier Gérard_, Sep 26 2012

%t FullSimplify[CoefficientList[Series[1/2*((Sqrt[2*E*Pi]*Erf[1/Sqrt[2]]+2) * E^(1/2*x*(x+2))*(x*(x+2)+2)-Sqrt[2*Pi]*E^(1/2*(x+1)^2)*(x*(x+2)+2) * Erf[(x+1)/Sqrt[2]]-2*(x+1)), {x, 0, 20}], x]* Range[0, 20]!] (* _Vaclav Kotesovec_, Dec 27 2012 *)

%t RecurrenceTable[{a[0] == 1, a[1] == 1, a[n] == a[n - 1] + (n + 1) a[n - 2]}, a[n], {n, 0, 24}] (* _Ray Chandler_, Jul 30 2015 *)

%t B[j_,n_] := Sum[2 n!/((n - j - 2 k)! 2^k k!), {k, 0, n/2}]

%t H[t_, u_, v_,n_] := HypergeometricPFQRegularized[{1,t+k-n},{1+(u+k-n)/2,(v+k-n)/2},-1/2]

%t Q[t_,n_] := Sqrt[Pi]n!Sum[((-1)^k 2^(k/2)(H[t,t,t+1,n]+(-t-k+n)H[t+1,t,t+3,n])HypergeometricU[1-k/2,3/2,1/2]Binomial[-t+n,k])/(n-t+1)!, {k,1,n-t}]

%t Flatten[{1, 1, 4, 8, FullSimplify@Table[B[0,n] + B[1,n] + B[2,n]/2 + Q[1,n] + Q[2,n] + Q[3,n]/2,{n,4,20}]}] (* _Benedict W. J. Irwin_, Apr 11 2017 *)

%t nxt[{n_,a_,b_}]:={n+1,b,b+a(n+2)}; NestList[nxt,{1,1,1},30][[All,2]] (* _Harvey P. Dale_, Dec 31 2017 *)

%o (PARI) { a=b=c=1; for (n = 0, 200, if (n>1, a=b + (n + 1)*c; c=b; b=a); write("b059480.txt", n, " ", a); ) }  \\ _Harry J. Smith_, Jun 27 2009

%K nonn

%O 0,3

%A _Wouter Meeussen_, Feb 15 2001

%E Name changed and offset of interpretation corrected by _Olivier Gérard_, Sep 26 2012