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

Author

Michael D. Weiner, Apr 26 2024

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Invert of shifted A000139.

Programs

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

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