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
Keywords
Examples
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).
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).
Programs
-
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 *) -
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
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)