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 *)
A258830
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 522, 3271, 26168, 214955, 2149550, 21881103, 262573236, 3191361201, 44679056814, 631546127049, 10104738032784, 162891774138339, 2932051934490102, 53094870211027831, 1061897404220556620, 21342730463672017301, 469540070200784380622
Offset: 0
p = 1432 is counted by a(4) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.
a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 5: 123, 132, 213, 231, 312.
a(4) = 20: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4132, 4231.
-
b:= proc(u, o, c) option remember;
`if`(c<0, 0, `if`(u+o<=c, (u+o)!,
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-> b(n, 0$2):
seq(a(n), n=0..30);
-
b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o <= c, (u + o)!,
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_] := b[n, 0, 0];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)
A262165
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 3.
Original entry on oeis.org
1, 1, 2, 5, 19, 82, 454, 2795, 20346, 162613, 1469309, 14424200, 155842828, 1812646171, 22807141756, 306480808871, 4403059520043, 67100946088054, 1084001371054298, 18469410744415367, 331442882307143590, 6242679740272435021, 123215973021475320637
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>3, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..3))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 3)))(b(0, n, 0)):
seq(a(n), n=0..25);
-
b[u_, o_, c_] := b[u, o, c] = If[c < 0 || c > 3, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, 3}]][Sum[b[u - j, o - 1 + j, c - 1], {j, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, o}]]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, 3]}]][b[0, n, 0]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)
A262166
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 4.
Original entry on oeis.org
1, 1, 2, 5, 20, 86, 516, 3135, 25080, 196468, 1964680, 18827225, 225926700, 2559350288, 35830904032, 468385940355, 7494175045680, 111029569712844, 1998532254831192, 33092842524631733, 661856850492634660, 12113055891685809704, 266487229617087813488
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>4, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..4))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 4)))(b(0, n, 0)):
seq(a(n), n=0..25);
-
b[u_, o_, c_] := b[u, o, c] = If[c < 0 || c > 4, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, 4}]][Sum[b[u - j, o - 1 + j, c - 1], {j, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, o}]]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, 4]}]][b[0, n, 0]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after Alois P. HeInz *)
A262167
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 5.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 521, 3264, 25899, 212534, 2092218, 21250451, 249294149, 3018733862, 41077515364, 577524896681, 8940290166542, 143098583946093, 2483312451690110, 44571301924473611, 857112705946351481, 17044616630699383294, 359813788663496645489
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>5, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..5))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 5)))(b(0, n, 0)):
seq(a(n), n=0..25);
-
b[u_, o_, c_] := b[u, o, c] = If[c < 0 || c > 5, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, 5}]][Sum[b[u - j, o - 1 + j, c - 1], {j, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, o}]]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, 5]}]][b[0, n, 0]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)
A262168
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 6.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 522, 3270, 26160, 214424, 2144240, 21705682, 260468184, 3134839134, 43887747876, 611561379844, 9784982077504, 154830562162384, 2786950118922912, 49340681212898288, 986813624257965760, 19321622221580752560, 425075688874776556320
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>6, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..6))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 6)))(b(0, n, 0)):
seq(a(n), n=0..25);
A262169
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 7.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 522, 3271, 26167, 214946, 2148500, 21869553, 262040897, 3184440794, 44442180413, 627992981034, 9996086297542, 161044694650665, 2877551846402242, 52059368659632095, 1031291013069584902, 20699996793232418643, 450130761784158558067
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>7, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..7))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 7)))(b(0, n, 0)):
seq(a(n), n=0..25);
A262170
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 8.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 522, 3271, 26168, 214954, 2149540, 21879021, 262548252, 3189754241, 44656559374, 630564958413, 10089039334608, 162310602568627, 2921590846235286, 52733511434265043, 1054670228685300860, 21098558728828707796, 464168292034231571512
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>8, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..8))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 8)))(b(0, n, 0)):
seq(a(n), n=0..25);
A262171
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 9.
Original entry on oeis.org
1, 1, 2, 5, 20, 87, 522, 3271, 26168, 214955, 2149549, 21881092, 262569097, 3191307394, 44674222343, 631473609984, 10100709895340, 162823295801791, 2928983654856296, 53036572897985517, 1059539775650223369, 21293220263695186990, 467627502721031824736
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>9, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..9))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 9)))(b(0, n, 0)):
seq(a(n), n=0..25);
A262164
Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= 2.
Original entry on oeis.org
1, 1, 2, 4, 16, 54, 324, 1532, 12256, 74512, 745120, 5536752, 66441024, 583466480, 8168530720, 82769713504, 1324315416064, 15208157533440, 273746835601920, 3513491887566848, 70269837751336960, 996837786288583168, 21930431298348829696, 340730692136161864704
Offset: 0
-
b:= proc(u, o, c) option remember; `if`(c<0 or c>2, 0, `if`(u+o=0,
x^c, (p-> add(coeff(p, x, i)*x^max(i, c), i=0..2))(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-> (p-> add(coeff(p, x, i), i=0..min(n, 2)))(b(0, n, 0)):
seq(a(n), n=0..25);
Showing 1-10 of 11 results.