A179257 Number of permutations of length n which avoid the patterns 321 and 1324.

1, 1, 2, 5, 13, 32, 72, 148, 281, 499, 838, 1343, 2069, 3082, 4460, 6294, 8689, 11765, 15658, 20521, 26525, 33860, 42736, 53384, 66057, 81031, 98606, 119107, 142885, 170318, 201812, 237802, 278753, 325161, 377554, 436493, 502573, 576424, 658712, 750140, 851449

Offset

0,3

Links

Table of n, a(n) for n=0..40.

M. D. Atkinson, Restricted permutations, Discrete Math., 195 (1999), 27-38.

Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.

J. West, Generating trees and forbidden subsequences, Discrete Math., 157 (1996), 363-374.

Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Formula

a(n) = 1+binomial(n,2)+binomial(n+2,5).

G.f.: 1-x*(x^5-4*x^4+7*x^3-8*x^2+4*x-1)/(x-1)^6. - Colin Barker, Aug 02 2012

a(n) = 1+A027658(n-2). - R. J. Mathar, Aug 19 2022

Example

There are 13 permutations of length 4 which avoid these two patterns, so a(4)=13.

Mathematica

LinearRecurrence[{6, -15, 20, -15, 6, -1}, {1, 1, 2, 5, 13, 32}, 50] (* Harvey P. Dale, May 19 2024 *)

Crossrefs

Cf. A116699, A116701, A116702, A088921, A005183, A116703, A001519.

Sequence in context: A082733 A095134 A086758 * A116702 A098156 A267862

Adjacent sequences: A179254 A179255 A179256 * A179258 A179259 A179260

Keyword

nonn,easy

Author

Vincent Vatter, Jul 05 2010

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 05 2018

Status

approved