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

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

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A001815, A001787, A011782, A001793.

Sequence in context: A121530 A121299 A326346 * A291385 A192877 A263622

Adjacent sequences: A046715 A046716 A046717 * A046719 A046720 A046721

Keyword

nonn

Author

Len Smiley

Extensions

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

Status

approved