cp's OEIS Frontend

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.

%I A258829 #32 Oct 25 2018 14:49:48
%S A258829 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,
%T A258829 272,1260,1263,340,129,6,1,0,1385,10871,8090,4734,819,261,7,1,0,7936,
%U A258829 66576,88101,33855,16066,1890,522,8,1,0,50521,694599,724189,495371,127538,52022,4260,1040,9,1
%N 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.
%H A258829 Alois P. Heinz, <a href="/A258829/b258829.txt">Rows n = 0..140, flattened</a>
%F A258829 T(n,k) = A262163(n,k) - A262163(n,k-1) for k>0, T(n,0) = A262163(n,0).
%e A258829 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.
%e A258829 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.
%e A258829 T(4,1) = 5: 2143, 3142, 3241, 4132, 4231.
%e A258829 T(4,2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.
%e A258829 T(4,3) = 3: 1243, 1342, 2341.
%e A258829 T(4,4) = 1: 1234.
%e A258829 Triangle T(n,k) begins:
%e A258829   1;
%e A258829   0,    1;
%e A258829   0,    1,     1;
%e A258829   0,    2,     2,    1;
%e A258829   0,    5,    11,    3,    1;
%e A258829   0,   16,    38,   28,    4,   1;
%e A258829   0,   61,   263,  130,   62,   5,   1;
%e A258829   0,  272,  1260, 1263,  340, 129,   6, 1;
%e A258829   0, 1385, 10871, 8090, 4734, 819, 261, 7, 1;
%p A258829 b:= proc(u, o, c, k) option remember;
%p A258829       `if`(c<0 or c>k, 0, `if`(u+o=0, 1,
%p A258829        add(b(u-j, o-1+j, c+1, k), j=1..u)+
%p A258829        add(b(u+j-1, o-j, c-1, k), j=1..o)))
%p A258829     end:
%p A258829 A:= (n, k)-> b(n, 0$2, k):
%p A258829 T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
%p A258829 seq(seq(T(n, k), k=0..n), n=0..12);
%t A258829 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}]]];
%t A258829 A[n_, k_] := b[n, 0, 0, k];
%t A258829 T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k - 1]];
%t A258829 Table[T[n, k], {n, 0, 12}, { k, 0, n}] // Flatten (* _Jean-François Alcover_, Jun 09 2018, after _Alois P. Heinz_ *)
%Y A258829 Columns k=0-10 give: A000007, A000111 for n>0, A259213, A316390, A316391, A316392, A316393, A316394, A316395, A316396, A316397.
%Y A258829 Row sums give A258830.
%Y A258829 T(2n,n) gives A266947.
%Y A258829 Cf. A262124, A262125, A262163, A291722, A316292, A316293.
%K A258829 nonn,tabl
%O A258829 0,8
%A A258829 _Alois P. Heinz_, Jun 11 2015