cp's OEIS Frontend

A371943 Number of permutations that end with a consecutive pattern 123, and avoid consecutive patterns 123 and 213 elsewhere.

%I A371943 #34 Apr 14 2024 11:29:29
%S A371943 0,0,0,1,2,10,28,116,388,1588,5960,25168,102856,453608,1985008,
%T A371943 9163360,42486128,205065136,1000056928,5035366208,25689681760,
%U A371943 134588839648,715328668736,3889568161408,21463055829568,120839175460160,690344333849728,4015753752384256
%N A371943 Number of permutations that end with a consecutive pattern 123, and avoid consecutive patterns 123 and 213 elsewhere.
%C A371943 (This can be proved by observing the possible positions of n.)
%H A371943 Sergi Elizalde and Yixin Lin, <a href="https://arxiv.org/abs/2404.06585">Penney's game for permutations</a>, arXiv:2404.06585 [math.CO], 2024.
%F A371943 a(0)=a(1)=a(2)=0, a(3)=1, a(4)=2; a(n) = a(n-1)+(n-1)*a(n-2)+b(n-1), where b(n) = b(n-1)+(n-1)*b(n-2) is the same sequence as A059480, up to the first initial terms. Here, our b(n) has initial terms 0, 0, 0, 1, 4.
%F A371943 From _Vaclav Kotesovec_, Apr 14 2024: (Start)
%F A371943 a(n) ~ c * n^((n+1)/2) * exp(sqrt(n) - n/2), where c = exp(-1/4) / sqrt(2) - exp(1/4) * sqrt(Pi) * erfc(1/sqrt(2)) / 2 = 0.189615662815288097469466802437...
%F A371943 E.g.f.: -1 + exp(x*(2 + x)/2) * (1 + x) + exp((1 + x)^2/2) * sqrt(Pi/2) * (2 + x) * (erf(1/sqrt(2)) - erf((1 + x)/sqrt(2))). (End)
%e A371943 For n=0, 1, 2, there are no permutations ending with 123. Hence, a(0)=a(1)=a(2)=0. For n=3, a(3)=1 since 123 is the only permutation that ends with 123. For n=4, a(4)=2 with qualified permutations 3124, 4123. For n=5, a(5)=10 with qualified permutations 14235, 15234, 24135, 25134, 34125, 35124, 43125, 45123, 53124, 54123.
%p A371943 a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
%p A371943       2*a(n-1)+2*(n-2)*(a(n-2)-a(n-3))-(n-2)*(n-3)*a(n-4)))
%p A371943     end:
%p A371943 seq(a(n), n=0..30);  # _Alois P. Heinz_, Apr 13 2024
%t A371943 a[n_]:=a[n]=If[n<3, 0, If[n==3, 1, 2*a[n-1]+2*(n-2)*(a[n-2]-a[n-3])-(n-2)*(n-3)*a[n-4]]]; Table[a[n], {n,0,27}] (* _Stefano Spezia_, Apr 13 2024 *)
%t A371943 RecurrenceTable[{a[n] == 2*a[n-1] + 2*(n-2)*(a[n-2] - a[n-3]) - (n-2)*(n-3)*a[n-4], a[0] == 0, a[1] == 0, a[2] == 0, a[3] == 1}, a, {n, 0, 30}] (* _Vaclav Kotesovec_, Apr 14 2024 *)
%t A371943 nmax = 30; FullSimplify[CoefficientList[Series[-1 + E^(x*(2 + x)/2) * (1 + x) + E^((1 + x)^2/2) * Sqrt[Pi/2] * (2 + x)*(Erf[1/Sqrt[2]] - Erf[(1 + x)/Sqrt[2]]), {x, 0, nmax}], x] * Range[0, nmax]!] (* _Vaclav Kotesovec_, Apr 14 2024 *)
%o A371943 (Python)
%o A371943 def aList(len):
%o A371943     b = [0, 0, 0, 1, 4]
%o A371943     a = [0, 0, 0, 1, 2]
%o A371943     for i in range(4, len):
%o A371943         b.append(b[i] + i * b[i - 1])
%o A371943         a.append(a[i] + i * a[i - 1] + b[i])
%o A371943     return a
%o A371943 print(aList(27))
%Y A371943 Cf. A059480.
%K A371943 nonn
%O A371943 0,5
%A A371943 _Yixin Lin_, Apr 13 2024