|
|
A262124
|
|
Number A(n,k) of permutations p of [n] such that the up-down signature of p has nonnegative partial sums with a maximal value <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
|
|
16
|
|
|
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 3, 5, 0, 1, 1, 1, 3, 8, 16, 0, 1, 1, 1, 3, 9, 40, 61, 0, 1, 1, 1, 3, 9, 44, 162, 272, 0, 1, 1, 1, 3, 9, 45, 219, 1134, 1385, 0, 1, 1, 1, 3, 9, 45, 224, 1445, 6128, 7936, 0, 1, 1, 1, 3, 9, 45, 225, 1568, 9985, 55152, 50521, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,14
|
|
LINKS
|
|
|
FORMULA
|
A(n,k) = Sum_{i=0..k} A262125(n,i).
|
|
EXAMPLE
|
p = 1423 is counted by T(4,1) because the up-down signature of p = 1423 is 1,-1,1 with partial sums 1,0,1.
q = 1432 is not counted by any T(4,k) because the up-down signature of q = 1432 is 1,-1,-1 with partial sums 1,0,-1.
A(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
A(4,2) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
A(4,3) = 9: 1234, 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 1, 1, 1, 1, 1, 1, ...
0, 2, 3, 3, 3, 3, 3, 3, ...
0, 5, 8, 9, 9, 9, 9, 9, ...
0, 16, 40, 44, 45, 45, 45, 45, ...
0, 61, 162, 219, 224, 225, 225, 225, ...
0, 272, 1134, 1445, 1568, 1574, 1575, 1575, ...
|
|
MAPLE
|
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)-> `if`(n=0, 1, (p-> add(coeff(p, x, i), i=0..min(n, k))
)(add(b(j-1, n-j, 0), j=1..n))):
seq(seq(A(n, d-n), n=0..d), d=0..12);
|
|
MATHEMATICA
|
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_] := If[n==0, 1, Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, k]}]][ Sum[b[j-1, n-j, 0], {j, 1, n}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|