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

Offset: 0

Author

Yixin Lin, Apr 13 2024

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• Sergi Elizalde and Yixin Lin, Penney's game for permutations, arXiv:2404.06585 [math.CO], 2024.

Crossrefs

Cf. A059480.

Programs

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 *)

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))

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)