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,4

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.

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.

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

Example

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

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 *)

Prog

(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

Crossrefs

Cf. A045720.

Sequence in context: A119364 A305826 A252817 * A323223 A211557 A333061

Adjacent sequences: A210061 A210062 A210063 * A210065 A210066 A210067

Keyword

nonn

Author

Cheyne Homberger, Mar 16 2012

Status

approved