A046718 Number of permutations of [ n ] with exactly one 132-pattern and two 123-patterns.

1, 4, 14, 47, 152, 472, 1408, 4048, 11264, 30464, 80384, 207616, 526336, 1312768, 3227648, 7835648, 18808832, 44695552, 105250816, 245825536, 569901056, 1312292864, 3003121664, 6833569792, 15468593152, 34846277632, 78148272128, 174533378048, 388291887104

Offset: 4

Author

Len Smiley

Keywords

• nonn

Examples

			a(4) = 1: 1324.
a(5) = 4: 24315, 24351, 41325, 51324.
a(6) = 14: 354216, 354261, 354612, 354621, 435162, 462135, 524316, 524361, 541326, 561324, 624315, 624351, 641325, 651324.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 4..1000
• S. Ekhad, A. Robertson, D. Zeilberger, The number of permutations with a prescribed number of 132 and 123 patterns, arXiv:math/9903170 [math.CO], 1999.
• Index entries for linear recurrences with constant coefficients, signature (8,-24,32,-16).

Crossrefs

Cf. A001815, A001787, A011782, A001793.

Programs

Maple

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-16|32|-24|8>>^(n-4).
        <<1, 4, 14, 47>>)[1, 1]:
seq(a(n), n=4..30);  # Alois P. Heinz, Oct 01 2012

Mathematica

LinearRecurrence[{8, -24, 32, -16}, {1, 4, 14, 47}, 30] (* Jean-François Alcover, Aug 18 2018 *)

Sage

def LinearRecurrence4(a0,a1,a2,a3,a4,a5,a6,a7):
    x, y, z, u = Integer(a0),Integer(a1),Integer(a2),Integer(a3)
    yield x
    while True:
        x, y, z, u = y, z, u, a7*x+a6*y+a5*z+a4*u
        yield x
A046718 = LinearRecurrence4(1, 4, 14, 47, 8, -24, 32, -16)
[next(A046718) for i in range(29)] # Peter Luschny, Oct 02 2012

Formula

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

a(n) = 2^(n-8)*(n^3-11*n^2+54*n-88). - R. J. Mathar, Oct 02 2012

Extensions

Edited at the suggestion of R. J. Mathar by Alois P. Heinz, Oct 01 2012