login
A264173
Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 1324; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.
14
1, 1, 2, 6, 23, 1, 110, 10, 632, 86, 2, 4229, 782, 29, 32337, 7571, 407, 5, 278204, 78726, 5856, 94, 2659223, 882997, 84351, 2215, 14, 27959880, 10657118, 1251246, 48234, 322, 320706444, 137977980, 19318314, 984498, 14322, 42, 3985116699, 1910131680, 311306106
OFFSET
0,3
COMMENTS
Pattern 4231 gives the same triangle.
LINKS
FORMULA
Sum_{k>0} k * T(n,k) = ceiling((n-3)*n!/4!) = A061206(n-3) (for n>3).
EXAMPLE
T(4,1) = 1: 1324.
T(6,2) = 2: 132546, 142536.
T(8,3) = 5: 13254768, 13264758, 14253768, 14263758, 15263748.
T(10,4) = 14: 132547698(10), 132548697(10), 132647598(10), 132648597(10), 132748596(10), 142537698(10), 142538697(10), 142637598(10), 142638597(10), 142738596(10), 152637498(10), 152638497(10), 152738496(10), 162738495(10).
Triangle T(n,k) begins:
00 : 1;
01 : 1;
02 : 2;
03 : 6;
04 : 23, 1;
05 : 110, 10;
06 : 632, 86, 2;
07 : 4229, 782, 29;
08 : 32337, 7571, 407, 5;
09 : 278204, 78726, 5856, 94;
10 : 2659223, 882997, 84351, 2215, 14;
MAPLE
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
add(b(u-j, o+j-1, `if`(t>0 and j<t, -j, 0)), j=1..u)+
add(b(u+j-1, o-j, j)*`if`(t<0 and -j<=t, x, 1), j=1..o)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14);
MATHEMATICA
b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[b[u - j, o + j - 1, If[t > 0 && j < t, -j, 0]], {j, 1, u}] + Sum[b[u + j - 1, o - j, j] * If[t < 0 && -j <= t, x, 1], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Apr 30 2017, translated from Maple *)
CROSSREFS
Row sums give A000142.
T(2n+2,n) gives A000108(n) for n>0.
Cf. A004526, A061206, A264319 (pattern 3412).
Sequence in context: A350274 A350273 A264319 * A220183 A177252 A168270
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Nov 06 2015
STATUS
approved