login
A371943
Number of permutations that end with a consecutive pattern 123, and avoid consecutive patterns 123 and 213 elsewhere.
0
0, 0, 0, 1, 2, 10, 28, 116, 388, 1588, 5960, 25168, 102856, 453608, 1985008, 9163360, 42486128, 205065136, 1000056928, 5035366208, 25689681760, 134588839648, 715328668736, 3889568161408, 21463055829568, 120839175460160, 690344333849728, 4015753752384256
OFFSET
0,5
COMMENTS
(This can be proved by observing the possible positions of n.)
LINKS
Sergi Elizalde and Yixin Lin, Penney's game for permutations, arXiv:2404.06585 [math.CO], 2024.
FORMULA
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.
From Vaclav Kotesovec, Apr 14 2024: (Start)
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...
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)
EXAMPLE
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.
MAPLE
a:= proc(n) option remember; `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)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Apr 13 2024
MATHEMATICA
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 *)
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 *)
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 *)
PROG
(Python)
def aList(len):
b = [0, 0, 0, 1, 4]
a = [0, 0, 0, 1, 2]
for i in range(4, len):
b.append(b[i] + i * b[i - 1])
a.append(a[i] + i * a[i - 1] + b[i])
return a
print(aList(27))
CROSSREFS
Cf. A059480.
Sequence in context: A000900 A124023 A127921 * A106184 A327696 A372871
KEYWORD
nonn
AUTHOR
Yixin Lin, Apr 13 2024
STATUS
approved