|
%I #34 Apr 14 2024 11:29:29
%S 0,0,0,1,2,10,28,116,388,1588,5960,25168,102856,453608,1985008,
%T 9163360,42486128,205065136,1000056928,5035366208,25689681760,
%U 134588839648,715328668736,3889568161408,21463055829568,120839175460160,690344333849728,4015753752384256
%N Number of permutations that end with a consecutive pattern 123, and avoid consecutive patterns 123 and 213 elsewhere.
%C (This can be proved by observing the possible positions of n.)
%H 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 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 From _Vaclav Kotesovec_, Apr 14 2024: (Start)
%F 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 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 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 a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
%p 2*a(n-1)+2*(n-2)*(a(n-2)-a(n-3))-(n-2)*(n-3)*a(n-4)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Apr 13 2024
%t 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 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 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 (Python)
%o def aList(len):
%o b = [0, 0, 0, 1, 4]
%o a = [0, 0, 0, 1, 2]
%o for i in range(4, len):
%o b.append(b[i] + i * b[i - 1])
%o a.append(a[i] + i * a[i - 1] + b[i])
%o return a
%o print(aList(27))
%Y Cf. A059480.
%K nonn
%O 0,5
%A _Yixin Lin_, Apr 13 2024
|
