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

%I #11 Dec 29 2020 09:03:48

%S 1,1,11,130,4734,127538,11174035,554432537,92953037066,7392808621010,

%T 2037044419366071,237281497432517293,97619260603080874874,

%U 15664643539583989506694,9013597510492035989870645,1906222253095637349478735538,1463288823474568248157186058298

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

%H Alois P. Heinz and Vaclav Kotesovec, <a href="/A266947/b266947.txt">Table of n, a(n) for n = 0..168</a> (terms 0..100 from Alois P. Heinz)

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

%e a(2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.

%p b:= proc(u, o, c, k) option remember;

%p `if`(c<0 or c>k, 0, `if`(u+o=0, 1,

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

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

%p end:

%p a:= n-> b(2*n, 0$2, n)-b(2*n, 0$2, n-1):

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

%t 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 a[n_] := b[2n, 0, 0, n] - b[2n, 0, 0, n - 1];

%t a /@ Range[0, 20] (* _Jean-François Alcover_, Dec 29 2020, after _Alois P. Heinz_ *)

%Y Cf. A258829.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Jan 06 2016