A163824 Number of permutations of length n in the 2x2 double-chevron permutation grid class.

1, 1, 2, 6, 24, 106, 470, 2038, 8624, 35754, 145902, 588358, 2351910, 9341814, 36936146, 145567966, 572415344, 2247578314, 8816986046, 34570684966, 135522530174, 531285354214, 2083180354466, 8170672802686, 32059325714054, 125845764142006, 494223989283650

Offset

0,3

Comments

The double-chevron grid class is the monotone grid class of permutations Grid((1,1),(-1,-1)).

Links

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

David Bevan, Permutation Grid Classes

Formula

O.g.f: 1/sqrt(1-4*x) - x*(1-x)/((1-2*x)*(1-3*x)).

a(n) = A000984(n) - A027649(n-1).

Conjecture: n*(n^2-6*n+11)*a(n) +(-9*n^3+56*n^2-119*n+60)*a(n-1) +2*(13*n^3-83*n^2+193*n-150)*a(n-2) -12*(2*n-5)*(n^2-4*n+6)*a(n-3) =0 . - R. J. Mathar, Jul 24 2012

Example

a(5) = 106 because the following 14 permutations can't be gridded (and hence are in the basis of the permutation class): 12543, 13254, 14253, 15243, 15423, 25413, 31254, 35412, 41253, 51243, 51423, 52413, 53412, 54123.

Mathematica

CoefficientList[Series[1/Sqrt[1-4x]-(x(1-x))/((1-2x)(1-3x)), {x, 0, 30}], x] (* Harvey P. Dale, Jun 09 2016 *)

Crossrefs

Sequence in context: A337770 A171338 A327006 * A356782 A094433 A178594

Adjacent sequences: A163821 A163822 A163823 * A163825 A163826 A163827

Keyword

nonn

Author

David Bevan, Jun 27 2012

Status

approved