A224290 Number of permutations of length n containing exactly 3 occurrences of 123 and 3 occurrences of 132.

0, 0, 0, 0, 0, 1, 6, 30, 136, 566, 2176, 7808, 26440, 85332, 264632, 793792, 2315136, 6592640, 18390784, 50392064, 135921664, 361536512, 949708800, 2466807808, 6342115328, 16153509888, 40790523904, 102186352640, 254105092096, 627533152256, 1539764125696

Offset

0,7

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

B. Nakamura, Approaches for enumerating permutations with a prescribed number of occurrences of patterns, arXiv 1301.5080 [math.CO], 2013.

B. Nakamura, A Maple package for enumerating n-permutations with r occurrences of the pattern 123 and s occurrences of the pattern 132 [Broken link]

Index entries for linear recurrences with constant coefficients, signature (14,-84,280,-560,672,-448,128).

Formula

G.f.: -(4*x^8-8*x^7+24*x^6-36*x^5+62*x^4-60*x^3+30*x^2-8*x+1)*x^5 / (2*x-1)^7. - Alois P. Heinz, Apr 03 2013

From Colin Barker, Nov 28 2018: (Start)

a(n) = (1/9)*2^(n-15) * (307008 - 247512*n + 78118*n^2 - 12087*n^3 + 937*n^4 - 33*n^5 + n^6) for n>6.

a(n) = 14*a(n-1) - 84*a(n-2) + 280*a(n-3) - 560*a(n-4) + 672*a(n-5) - 448*a(n-6) + 128*a(n-7) for n>13.

(End)

Example

a(5) = 1: (1,4,3,2,5).
a(6) = 6: (2,5,4,3,1,6), (2,5,4,3,6,1), (3,5,1,4,6,2), (3,6,1,4,2,5), (5,1,4,3,2,6), (6,1,4,3,2,5).

Maple

# Programs can be obtained from the Nakamura link

Mathematica

Join[{0, 0, 0, 0, 0, 1, 6}, LinearRecurrence[{14, -84, 280, -560, 672, -448, 128}, {30, 136, 566, 2176, 7808, 26440, 85332}, 33]] (* Jean-François Alcover, Nov 28 2018 *)

Prog

(PARI) concat([0, 0, 0, 0, 0], Vec(x^5*(1 - 8*x + 30*x^2 - 60*x^3 + 62*x^4 - 36*x^5 + 24*x^6 - 8*x^7 + 4*x^8) / (1 - 2*x)^7 + O(x^40))) \\ Colin Barker, Nov 28 2018

Crossrefs

Cf. A000079, A001787, A001815, A046718, A001793.

Sequence in context: A317755 A036068 A162743 * A081895 A030280 A034545

Adjacent sequences: A224287 A224288 A224289 * A224291 A224292 A224293

Keyword

nonn

Author

Brian Nakamura, Apr 03 2013

Status

approved