A217711 Total number of 321 patterns in the set of permutations avoiding 123.

1, 16, 144, 1016, 6271, 35584, 190628, 979496, 4876530, 23686560, 112796176, 528495600, 2442949979, 11163970432, 50520351612, 226688100104, 1009648508590, 4467591809376, 19654294688768, 86018255452048, 374715017442966, 1625489878136576, 7024392489806344

Offset: 3

Author

Cheyne Homberger, Mar 20 2013

Keywords

• nonn

Comments

a(n) is the total number of occurrences of 321 patterns in the set of all 123-avoiding n-permutations.

Examples

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

Links

• Cheyne Homberger, Expected patterns in permutation classes, Electronic Journal of Combinatorics, 19(3) (2012), P43.

Formula

G.f.: 1/2*(32*x^4 - 88*x^3 + 52*x^2 + sqrt(-4*x + 1)*(36*x^3 - 34*x^2 + 10*x - 1) - 12*x + 1)/(64*x^4 - 48*x^3 + 12*x^2 - x).

Conjecture: -(n+1)*(25*n-3314)*a(n) -5*n*(5*n+9446)*a(n-1) +2*(594*n^2 +128863*n -142613)*a(n-2) +16*(-119*n^2-39230*n+87888)*a(n-3) -32*(2*n-7)*(53*n-8687)*a(n-4)=0. - R. J. Mathar, Oct 08 2016