login
Number of permutations p of [n] such that the sequence of ascents and descents of p is encoded by the 0's and 1's, respectively, in the binary expansion of n (read from right to left and using leading 0's if necessary).
5

%I #27 Sep 19 2020 18:23:21

%S 1,0,0,1,3,16,26,20,69,370,1006,945,1266,3015,2365,1001,4367,24736,

%T 76960,69615,138397,322944,286824,133056,159391,546504,978054,674245,

%U 531530,957320,495495,142506,906191,5537808,18828096,16231039,37000909,81351936,71761536

%N Number of permutations p of [n] such that the sequence of ascents and descents of p is encoded by the 0's and 1's, respectively, in the binary expansion of n (read from right to left and using leading 0's if necessary).

%H Alois P. Heinz, <a href="/A335308/b335308.txt">Table of n, a(n) for n = 0..4095</a>

%F a(n) = A060351(n,n).

%F a(2^n-1) = binomial(2^n-2,n).

%F a(2^n) = binomial(2^n,n+1)-1.

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

%e a(3) = 1: 321 (down, down).

%e a(4) = 3: 1243, 1342, 2341 (up, up, down).

%e a(5) = 16: 21435, 21534, 31425, 31524, 32415, 32514, 41325, 41523, 42315, 42513, 43512, 51324, 51423, 52314, 52413, 53412 (down, up, down, up).

%e a(6) = 26: 143256, 153246, 154236, 163245, 164235, 165234, 243156, 253146, 254136, 263145, 264135, 265134, 342156, 352146, 354126, 362145, 364125, 365124, 452136, 453126, 462135, 463125, 465123, 562134, 563124, 564123 (up, down, down, up, up).

%e a(7) = 20: 4321567, 5321467, 5421367, 5431267, 6321457, 6421357, 6431257, 6521347, 6531247, 6541237, 7321456, 7421356, 7431256, 7521346, 7531246, 7541236, 7621345, 7631245, 7641235, 7651234 (down^3, up^3).

%p b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),

%p `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),

%p add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))

%p end:

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

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

%Y Cf. A060351, A242783, A242784, A242785.

%K nonn,look,base

%O 0,5

%A _Alois P. Heinz_, Sep 12 2020