A372310 Number of permutations of length n avoiding the pattern 1324 and with 1 appearing before n.

1, 3, 11, 45, 198, 919, 4446, 22239, 114347, 601722, 3229614, 17632437, 97707195, 548538588, 3115293151, 17875151109, 103511938302, 604392787819, 3555410248782, 21057224371290, 125484804821226, 752020468811244, 4530163818778839, 27419805899781843, 166694596163875206

Offset

2,2

Comments

This sequence counts the number of permutations of size n written in one-line notation that avoid the pattern 1324 and have the 1 appearing before the n.

Links

Table of n, a(n) for n=2..26.

Juan B. Gil, Oscar A. Lopez, and Michael D. Weiner, A positional statistic for 1324-avoiding permutations, arXiv:2311.18227 [math.CO], 2024.

Formula

G.f.: A(x) = (x*(B(x)-2))/(3-B(x)), where B(x) is the g.f. for A000139. (See arxiv paper by Gil, Lopez, Weiner.)

G.f. satisfies 0 = x^4*(8*x-1) + x^2*(9*x-1)*(4*x-1)*A(x) + x*(6*x-1)*(9*x-2)*A(x)^2 + (27*x^2-9*x+1)*A(x)^3.

a(n) ~ 3^(3*n - 9/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n - 5)). - Vaclav Kotesovec, Jul 06 2024

D-finite with recurrence 4*(n-1)*(2*n-5)*a(n) -6*(n-2)*(23*n-63)*a(n-1) +9*(99*n^2-567*n+818)*a(n-2) +81*(-31*n^2+215*n-374)*a(n-3) +243*(3*n-13)*(3*n-14)*a(n-4)=0. - R. J. Mathar, Sep 27 2024

Example

For n=4, a(4)=11 is counting the permutations (in one-line notation): 1234, 1243, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214.

Maple

f:= proc(n) f(n):= 2*(3*n)!/((2*n+1)!*(n+1)!) end:
a:= proc(n) option remember; `if`(n=1, 1,
      add(a(n-i)*f(i), i=1..n))
    end:
seq(a(n), n=2..26);  # Alois P. Heinz, Apr 26 2024

Mathematica

a[1] = 1; a[n_] := a[n] = 2*Sum[a[n-k]*(3*k)!/((2*k + 1)!*(k+1)!), {k, 1, n-1}]; Table[a[n], {n, 2, 30}] (* Vaclav Kotesovec, Jul 06 2024 *)

Crossrefs

Invert of shifted A000139.

Sequence in context: A151132 A200075 A187764 * A151133 A213333 A083886

Adjacent sequences: A372307 A372308 A372309 * A372311 A372312 A372313

Keyword

nonn

Author

Michael D. Weiner, Apr 26 2024

Status

approved