A229892 Number T(n,k) of k up, k down permutations of [n]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 0, 1, 1, 0, 2, 1, 1, 0, 5, 3, 1, 1, 0, 16, 6, 4, 1, 1, 0, 61, 26, 10, 5, 1, 1, 0, 272, 71, 20, 15, 6, 1, 1, 0, 1385, 413, 125, 35, 21, 7, 1, 1, 0, 7936, 1456, 461, 70, 56, 28, 8, 1, 1, 0, 50521, 10576, 1301, 574, 126, 84, 36, 9, 1, 1

Offset: 0

Author

Alois P. Heinz, Oct 02 2013

Keywords

• nonn
• tabl
• eigen

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = T(n,n) = A000012(n) = 1 for k>n.

T(2*n,n) = C(2*n-1,n) = A088218(n) = A001700(n-1) for n>0.

T(2*n+1,n) = C(2*n,n) = A000984(n).

T(2*n+1,n+1) = C(2n,n-1) = A001791(n) for n>0.

Examples

			Triangle T(n,k) begins:
  1;
  1,    1;
  0,    1,   1;
  0,    2,   1,   1;
  0,    5,   3,   1,  1;
  0,   16,   6,   4,  1,  1;
  0,   61,  26,  10,  5,  1, 1;
  0,  272,  71,  20, 15,  6, 1, 1;
  0, 1385, 413, 125, 35, 21, 7, 1, 1;
		

Links

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

Crossrefs

Columns k=1-10 give: A000111, A058258, A229884, A229885, A229886, A229887, A229888, A229889, A229890, A229891.

Cf. A227941, A229066, A229551.

Programs

Maple

b:= proc(u, o, t, k) option remember; `if`(u+o=0, 1, add(`if`(t=k,
       b(o-j, u+j-1, 1, k), b(u+j-1, o-j, t+1, k)), j=1..o))
    end:
T:= (n, k)-> `if`(k+1>=n, 1, `if`(k=0, 0, b(0, n, 0, k))):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

b[u_, o_, t_, k_] := b[u, o, t, k] = If[u+o == 0, 1, Sum[If[t == k, b[o-j, u+j-1, 1, k], b[u+j-1, o-j, t+1, k]], {j, 1, o}]]; t[n_, k_] := If[k+1 >= n, 1, If[k == 0, 0, b[0, n, 0, k]]]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Formula

T(7,3) = 20: 1237654, 1247653, 1257643, 1267543, 1347652, 1357642, 1367542, 1457632, 1467532, 1567432, 2347651, 2357641, 2367541, 2457631, 2467531, 2567431, 3457621, 3467521, 3567421, 4567321.