A116705 Number of permutations of length n which avoid the patterns 1234, 4312.

1, 2, 6, 22, 86, 321, 1085, 3266, 8797, 21478, 48206, 100728, 198046, 369617, 659505, 1131656, 1876481, 3018946, 4728382, 7230242, 10820046, 15879769, 22896941, 32486742, 45417389, 62639126, 85317142, 114868756, 153005222, 201778521

Offset

1,2

References

Kremer, Darla; and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), no. 1-3, 171-183. MR1983276 (2004b:05006). See Table 1.

Links

Table of n, a(n) for n=1..30.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Formula

G.f.: x*(4*x^8-19*x^7+32*x^6-39*x^5+62*x^4-44*x^3+24*x^2-7*x+1)/(1-x)^9

a(n) = (21*n^8 - 48*n^7 - 966*n^6 + 7728*n^5 - 8211*n^4 - 72912*n^3 + 311556*n^2 - 418608*n + 241920)/60480. - Franklin T. Adams-Watters, Sep 16 2006

Crossrefs

Sequence in context: A206736 A079105 A079104 * A116708 A116706 A165524

Adjacent sequences: A116702 A116703 A116704 * A116706 A116707 A116708

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved