A226432 The number of simple permutations of length n in a particular geometric grid class.

1, 2, 0, 2, 3, 7, 13, 25, 46, 84, 151, 269, 475, 833, 1452, 2518, 4347, 7475, 12809, 21881, 37274, 63336, 107375, 181657, 306743, 517057, 870168, 1462250, 2453811, 4112479, 6884101, 11510809, 19226950, 32084028, 53489287, 89097893, 148290067, 246615425, 409835844, 680609086

Offset

1,2

Comments

This geometric grid class is given by the array [[0,0,1,0],[0,0,0,1],[0,1,-1,0],[1,0,0,-1]]. A picture is given in the LINKS section.

The sequence of all permutations in this class is given by A226431.

Links

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

Jay Pantone, The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832 [math.CO], (2013).

Jay Pantone, Picture of the geometric grid class

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

Formula

G.f.: x+2*x^2+ x^4*(1-x)*(2+x)/(1-x-x^2)^2 (corrected, Joerg Arndt, Jun 26 2013)

a(n) = A191830(n+2)-A000045(n+2), n>=4. - R. J. Mathar, Aug 31 2013

Mathematica

Join[{1, 2}, LinearRecurrence[{2, 1, -2, -1}, {0, 2, 3, 7}, 40]] (* Jean-François Alcover, Jul 21 2018 *)

Prog

(PARI) x='x+O('x^66); Vec(x+2*x^2+(x^4*(1-x)*(2+x))/((1-x-x^2)^2) ) \\ Joerg Arndt, Jun 19 2013

Crossrefs

Sequence in context: A222753 A274568 A233399 * A072514 A071547 A220222

Adjacent sequences: A226429 A226430 A226431 * A226433 A226434 A226435

Keyword

nonn,easy

Author

Jay Pantone, Jun 06 2013

Status

approved