A210064 Total number of 231 patterns in the set of permutations avoiding 123.

0, 0, 1, 11, 81, 500, 2794, 14649, 73489, 356960, 1691790, 7864950, 36000186, 162697176, 727505972, 3223913365, 14176874193, 61926666824, 268931341414, 1161913686618, 4997204887550, 21404922261112, 91351116184716, 388581750349946, 1647982988377786

Offset: 1

Author

Cheyne Homberger, Mar 16 2012

Keywords

• nonn

Comments

a(n) is the total number of 231 (and also 312) patterns in the set of all 123 avoiding n-permutations. Also the number of 231 (or 213, or 312) patterns in the set of all 132 avoiding n-permutations.

Examples

			a(3) = 1 since there is only one 231 pattern in the set {132,213,231,312,321}.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Cheyne Homberger, Expected patterns in permutation classes, Electronic Journal of Combinatorics, 19(3) (2012), P43.

Crossrefs

Cf. A045720.

Programs

Mathematica

Rest[CoefficientList[Series[x/(2*(1-4*x)^2) + (x-1)/(2*(1-4*x)^(3/2)) + 1/(2 - 8*x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 15 2014 *)

PARI

x='x+O('x^50); concat([0,0], Vec(x/(2*(1-4*x)^2) + (x-1)/(2*(1-4*x)^(3/2)) + 1/(2 - 8*x))) \\ G. C. Greubel, May 31 2017

Formula

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

a(n) ~ n * 2^(2*n-3) * (1 - 6/sqrt(Pi*n)). - Vaclav Kotesovec, Mar 15 2014

Conjecture: n*(n-3)*a(n) +2*(-4*n^2+11*n-2)*a(n-1) +8*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Oct 08 2016