A371943 - OEIS

A371943

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

(This can be proved by observing the possible positions of n.)

LINKS

Table of n, a(n) for n=0..27.

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.