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.
Original entry on oeis.org
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
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;
Columns k=0-10 give:
A000007,
A000111 for n>0,
A259213,
A316390,
A316391,
A316392,
A316393,
A316394,
A316395,
A316396,
A316397.
-
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);
-
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 *)
A262163
Number A(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 4, 5, 0, 1, 1, 2, 5, 16, 16, 0, 1, 1, 2, 5, 19, 54, 61, 0, 1, 1, 2, 5, 20, 82, 324, 272, 0, 1, 1, 2, 5, 20, 86, 454, 1532, 1385, 0, 1, 1, 2, 5, 20, 87, 516, 2795, 12256, 7936, 0, 1, 1, 2, 5, 20, 87, 521, 3135, 20346, 74512, 50521, 0
Offset: 0
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 2, 2, 2, 2, 2, ...
0, 2, 4, 5, 5, 5, 5, 5, ...
0, 5, 16, 19, 20, 20, 20, 20, ...
0, 16, 54, 82, 86, 87, 87, 87, ...
0, 61, 324, 454, 516, 521, 522, 522, ...
0, 272, 1532, 2795, 3135, 3264, 3270, 3271, ...
Columns k=0-10 give:
A000007,
A000111 for n>0,
A262164,
A262165,
A262166,
A262167,
A262168,
A262169,
A262170,
A262171,
A262172.
-
b:= proc(u, o, c) option remember; `if`(c<0, 0, `if`(u+o=0, x^c,
(p-> add(coeff(p, x, i)*x^max(i, c), i=0..degree(p)))(add(
b(u-j, o-1+j, c-1), j=1..u)+add(b(u+j-1, o-j, c+1), j=1..o))))
end:
A:= (n, k)-> (p-> add(coeff(p, x, i), i=0..min(n, k)))(b(0, n, 0)):
seq(seq(A(n, d-n), n=0..d), d=0..12);
-
b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, Exponent[p, x]}]][Sum[b[u - j, o - 1 + j, c - 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, 1, o}]]]]; A[n_, k_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, k]}]][b[0, n, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)
Original entry on oeis.org
1, 2, 11, 38, 263, 1260, 10871, 66576, 694599, 5182960, 63738259, 561098224, 7969169739, 80865956192, 1304923903919, 14998292190464, 271341955926479, 3484403002454016, 69899466563099435, 991886288235459072, 21861082423955691795, 339715268249655012352
Offset: 0
Showing 1-3 of 3 results.