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

Author

David Bevan, Jun 27 2012

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• David Bevan, Permutation Grid Classes

Programs

Mathematica

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

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