A116714 Number of permutations of length n that avoid the patterns 321, 1342, 4123.

1, 1, 2, 5, 12, 24, 46, 87, 162, 300, 554, 1021, 1880, 3460, 6366, 11711, 21542, 39624, 72882, 134053, 246564, 453504, 834126, 1534199, 2821834, 5190164, 9546202, 17558205, 32294576, 59398988, 109251774, 200945343, 369596110, 679793232, 1250334690, 2299724037

Offset

0,3

Links

Paolo Xausa, Table of n, a(n) for n = 0..1000

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Formula

G.f.: (x^5 + 3*x^4 + x^3 - x+1)/((x-1)*(x^3 + x^2 + x - 1)).

Maple

A116714 := proc(n)
    if n = 1 then
        1;
    else
        -5+A000073(n+2)+4*A000073(n+1)+3*A000073(n) ;
        %/2 ;
    end if;
end proc:
seq(A116714(n), n=1..20) ; # R. J. Mathar, Jan 11 2024

Mathematica

LinearRecurrence[{2, 0, 0, -1}, {1, 1, 2, 5, 12, 24}, 50] (* Paolo Xausa, Jan 19 2024 *)

Crossrefs

Sequence in context: A192981 A116713 A261369 * A023615 A320235 A034483

Adjacent sequences: A116711 A116712 A116713 * A116715 A116716 A116717

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 19 2024

Status

approved