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
Examples
There are 13 permutations of length 4 which avoid these two patterns, so a(4)=13.
Links
- 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).
Programs
-
Mathematica
LinearRecurrence[{6,-15,20,-15,6,-1},{1,1,2,5,13,32},50] (* Harvey P. Dale, May 19 2024 *)
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
Extensions
a(0)=1 prepended by Alois P. Heinz, Jul 05 2018