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

1, 1, 2, 6, 23, 1, 110, 10, 631, 88, 1, 4223, 794, 23, 32301, 7639, 379, 1, 277962, 79164, 5706, 48, 2657797, 885128, 84354, 1520, 1, 27954521, 10657588, 1266150, 38452, 89, 320752991, 137752283, 19621124, 869740, 5461, 1, 3987045780, 1904555934, 316459848

Offset: 0

Author

Alois P. Heinz, Nov 11 2015

Keywords

• nonn
• tabf

Comments

Pattern 2143 gives the same triangle.

Examples

			T(4,1) = 1: 3412.
T(5,1) = 10: 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
T(6,2) = 1: 563412.
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.
T(8,3) = 1: 78563412.
T(9,3) = 48: 189674523, 289674513, 389674512, ..., 896745132, 896745231, 978563412.
Triangle T(n,k) begins:
00 :       1;
01 :       1;
02 :       2;
03 :       6;
04 :      23,      1;
05 :     110,     10;
06 :     631,     88,     1;
07 :    4223,    794,    23;
08 :   32301,   7639,   379,    1;
09 :  277962,  79164,  5706,   48;
10 : 2657797, 885128, 84354, 1520, 1;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A113229, A264320, A264321, A264322, A264323, A264324, A264325, A264326, A264327, A264328, A264329.

Row sums give A000142.

Cf. A004526, A061206, A264173 (pattern 1324).

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(expand(
       b(u+j-1, o-j, j)*`if`(t<0 and j<1-t, x, 1)), j=1..o)+
      add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u))
    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] = 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_ *)

Formula

Sum_{k>0} k * T(n,k) = ceiling((n-3)*n!/4!) = A061206(n-3) (for n>3).