login
Number of permutations p of [n] such that the up-down signature of p has nonnegative partial sums with a maximal value <= 2.
4

%I #8 Aug 30 2021 06:35:43

%S 1,1,1,3,8,40,162,1134,6128,55152,372560,4098160,33220512,431866656,

%T 4084265360,61263980400,662157708032,11256681036544,136873417800960,

%U 2600594938218240,35134918875668480,737833296389038080,10965215649174414848,252199959931011541504

%N Number of permutations p of [n] such that the up-down signature of p has nonnegative partial sums with a maximal value <= 2.

%H Alois P. Heinz, <a href="/A262126/b262126.txt">Table of n, a(n) for n = 0..464</a>

%F a(n) = A262124(n,2).

%e a(0) = 1: the empty permutation.

%e a(1) = 1: 1.

%e a(2) = 1: 12.

%e a(3) = 3: 123, 132, 231.

%e a(4) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.

%p b:= proc(u, o, c) option remember; `if`(c<0 or c>2, 0, `if`(u+o=0, x^c,

%p (p-> add(coeff(p, x, i)*x^max(i, c), i=0..2))(add(

%p b(u-j, o-1+j, c-1), j=1..u)+add(b(u+j-1, o-j, c+1), j=1..o))))

%p end:

%p a:= n-> `if`(n=0, 1, (p-> add(coeff(p, x, i), i=0..2))(

%p add(b(j-1, n-j, 0), j=1..n))):

%p seq(a(n), n=0..30);

%t b[u_, o_, c_] := b[u, o, c] = If[c < 0 || c > 2, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, 2}]][Sum[b[u - j, o - 1 + j, c - 1], {j, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, o}]]]];

%t a[n_] := If[n == 0, 1, Function[p, Sum[Coefficient[p, x, i], {i, 0, 2}]][Sum[b[j - 1, n - j, 0], {j, n}]]];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Aug 30 2021, after _Alois P. Heinz_ *)

%Y Column k=2 of A262124.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Sep 11 2015