A258829 Number T(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 11, 3, 1, 0, 16, 38, 28, 4, 1, 0, 61, 263, 130, 62, 5, 1, 0, 272, 1260, 1263, 340, 129, 6, 1, 0, 1385, 10871, 8090, 4734, 819, 261, 7, 1, 0, 7936, 66576, 88101, 33855, 16066, 1890, 522, 8, 1, 0, 50521, 694599, 724189, 495371, 127538, 52022, 4260, 1040, 9, 1

Offset

0,8

Links

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

Formula

T(n,k) = A262163(n,k) - A262163(n,k-1) for k>0, T(n,0) = A262163(n,0).

Example

p = 1432 is counted by T(4,2) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.
q = 4321 is not counted by any T(4,k) because the up-down signature of 0,q = 04321 is 1,-1,-1,-1 with partial sums 1,0,-1,-2.
T(4,1) = 5: 2143, 3142, 3241, 4132, 4231.
T(4,2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.
T(4,3) = 3: 1243, 1342, 2341.
T(4,4) = 1: 1234.
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,     1;
  0,    2,     2,    1;
  0,    5,    11,    3,    1;
  0,   16,    38,   28,    4,   1;
  0,   61,   263,  130,   62,   5,   1;
  0,  272,  1260, 1263,  340, 129,   6, 1;
  0, 1385, 10871, 8090, 4734, 819, 261, 7, 1;

Maple

b:= proc(u, o, c, k) option remember;
      `if`(c<0 or c>k, 0, `if`(u+o=0, 1,
       add(b(u-j, o-1+j, c+1, k), j=1..u)+
       add(b(u+j-1, o-j, c-1, k), j=1..o)))
    end:
A:= (n, k)-> b(n, 0$2, k):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[u_, o_, c_, k_] := b[u, o, c, k] = If[c < 0 || c > k, 0, If[u + o == 0, 1, Sum[b[u - j, o - 1 + j, c + 1, k], {j, 1, u}] + Sum[b[u + j - 1, o - j, c - 1, k], {j, 1, o}]]];
A[n_, k_] := b[n, 0, 0, k];
T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k - 1]];
Table[T[n, k], {n, 0, 12}, { k, 0, n}] // Flatten (* Jean-François Alcover, Jun 09 2018, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A000111 for n>0, A259213, A316390, A316391, A316392, A316393, A316394, A316395, A316396, A316397.

Row sums give A258830.

T(2n,n) gives A266947.

Cf. A262124, A262125, A262163, A291722, A316292, A316293.

Sequence in context: A065066 A266291 A064045 * A110314 A370890 A152882

Adjacent sequences: A258826 A258827 A258828 * A258830 A258831 A258832

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 11 2015

Status

approved