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,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.

Sequence in context: A000900 A124023 A127921 * A106184 A327696 A372871

Adjacent sequences: A371940 A371941 A371942 * A371944 A371945 A371946

Keyword

nonn

Author

Yixin Lin, Apr 13 2024

Status

approved