A116703 Number of permutations of length n which avoid the patterns 231, 4123.

1, 2, 5, 13, 33, 82, 202, 497, 1224, 3017, 7439, 18343, 45228, 111514, 274945, 677894, 1671393, 4120937, 10160465, 25051354, 61765902, 152288233, 375477484, 925766477, 2282543187, 5627772815, 13875674756, 34211464510, 84350802705

Offset

1,2

Comments

Also number of permutations of length n which avoid the patterns 312, 2341, 3412; or avoid the patterns 132, 1324, 3214, etc.

Except for the offset, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^3; see A291000. - Clark Kimberling, Aug 24 2017

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.

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

David Callan, Toufik Mansour, Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 62-97.

Toufik Mansour and Mark Shattuck, Avoidance of type (1,2) patterns by Catalan words, Turkish Journal of Analysis and Number Theory, May 2017. See item 1-23 in Table 1, p. 3.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.

L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.

Index entries for linear recurrences with constant coefficients, signature (4,-5,3).

Formula

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

Binomial transform of A000930 starting with offset 1: [1, 1, 2, 3, 4, 6, 9, ...]. - Gary W. Adamson, Oct 23 2007

Mathematica

CoefficientList[Series[x*(1-2*x+2*x^2)/(1-4*x+5*x^2-3*x^3), {x, 0, 50}], x] (* G. C. Greubel, Apr 29 2017 *)

Prog

(PARI) x='x+O('x^50); Vec(x*(1-2*x+2*x^2)/(1-4*x+5*x^2-3*x^3)) \\ G. C. Greubel, Apr 29 2017

Crossrefs

Cf. A000930.

Sequence in context: A067676 A292507 A307465 * A007443 A120925 A086588

Adjacent sequences: A116700 A116701 A116702 * A116704 A116705 A116706

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

Edited by N. J. A. Sloane, Mar 16 2008

Status

approved