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

Comments

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

Links

Table of n, a(n) for n=3..25.

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

Example

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

Crossrefs

Sequence in context: A319553 A054851 A000762 * A086952 A230971 A282524

Adjacent sequences: A217708 A217709 A217710 * A217712 A217713 A217714

Keyword

nonn

Author

Cheyne Homberger, Mar 20 2013

Status

approved