|
%I #14 Jan 16 2017 08:53:54
%S 1,1,2,6,23,1,110,10,631,88,1,4223,794,23,32301,7639,379,1,277962,
%T 79164,5706,48,2657797,885128,84354,1520,1,27954521,10657588,1266150,
%U 38452,89,320752991,137752283,19621124,869740,5461,1,3987045780,1904555934,316459848
%N Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 3412; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.
%C Pattern 2143 gives the same triangle.
%H Alois P. Heinz, <a href="/A264319/b264319.txt">Rows n = 0..140, flattened</a>
%F Sum_{k>0} k * T(n,k) = ceiling((n-3)*n!/4!) = A061206(n-3) (for n>3).
%e T(4,1) = 1: 3412.
%e T(5,1) = 10: 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
%e T(6,2) = 1: 563412.
%e T(7,2) = 23: 1674523, 2674513, 3674512, 4673512, 5614723, 5624713, 5634127, 5634712, 5673412, 5714623, 5724613, 5734126, 5734612, 6573412, 6714523, 6724513, 6734125, 6734512, 6735124, 6745123, 6745132, 6745231, 7563412.
%e T(8,3) = 1: 78563412.
%e T(9,3) = 48: 189674523, 289674513, 389674512, ..., 896745132, 896745231, 978563412.
%e Triangle T(n,k) begins:
%e 00 : 1;
%e 01 : 1;
%e 02 : 2;
%e 03 : 6;
%e 04 : 23, 1;
%e 05 : 110, 10;
%e 06 : 631, 88, 1;
%e 07 : 4223, 794, 23;
%e 08 : 32301, 7639, 379, 1;
%e 09 : 277962, 79164, 5706, 48;
%e 10 : 2657797, 885128, 84354, 1520, 1;
%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(expand(
%p b(u+j-1, o-j, j)*`if`(t<0 and j<1-t, x, 1)), j=1..o)+
%p add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
%p seq(T(n), n=0..14);
%t b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[Expand[b[u+j-1, o-j, j]*If[t<0 && j<1-t, x, 1]], {j, 1, o}] + Sum[b[u-j, o+j-1, If[t>0 && j>t, t-j, 0]], {j, 1, u}]]; 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_, Jan 16 2017, translated from Maple_ *)
%Y Columns k=0-10 give: A113229, A264320, A264321, A264322, A264323, A264324, A264325, A264326, A264327, A264328, A264329.
%Y Row sums give A000142.
%Y Cf. A004526, A061206, A264173 (pattern 1324).
%K nonn,tabf
%O 0,3
%A _Alois P. Heinz_, Nov 11 2015
|
