OFFSET
0,3
COMMENTS
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.
LINKS
Harry J. Smith, Table of n, a(n) for n = 0..200
Sergi Elizalde and Yixin Lin, Penney's game for permutations, arXiv:2404.06585 [math.CO], 2024. See p. 16.
Sergey Kitaev and Toufik Mansour, On multi-avoidance of generalized patterns arXiv:0209340 [math.CO], 2002.
FORMULA
a(n) = a(n - 1) + (n + 1)*a(n - 2); a(0) = a(1) = 1;
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.
E.g.f.: (with offset 2) exp(x+x^2/2) * (1-integral(exp(-t-t^2/2) dt, t=0..x)) - 1 .
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
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
EXAMPLE
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
MATHEMATICA
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 *)
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 *)
B[j_, n_] := Sum[2 n!/((n - j - 2 k)! 2^k k!), {k, 0, n/2}]
H[t_, u_, v_, n_] := HypergeometricPFQRegularized[{1, t+k-n}, {1+(u+k-n)/2, (v+k-n)/2}, -1/2]
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}]
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 *)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Wouter Meeussen, Feb 15 2001
EXTENSIONS
Name changed and offset of interpretation corrected by Olivier Gérard, Sep 26 2012
STATUS
approved