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,3

Comments

Pattern 2143 gives the same triangle.

Links

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

Formula

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

Example

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;

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_ *)

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

Sequence in context: A342865 A350274 A350273 * A264173 A220183 A177252

Adjacent sequences: A264316 A264317 A264318 * A264320 A264321 A264322

Keyword

nonn,tabf

Author

Alois P. Heinz, Nov 11 2015

Status

approved