A335308 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).

1, 0, 0, 1, 3, 16, 26, 20, 69, 370, 1006, 945, 1266, 3015, 2365, 1001, 4367, 24736, 76960, 69615, 138397, 322944, 286824, 133056, 159391, 546504, 978054, 674245, 531530, 957320, 495495, 142506, 906191, 5537808, 18828096, 16231039, 37000909, 81351936, 71761536

Offset: 0

Author

Alois P. Heinz, Sep 12 2020

Keywords

• nonn
• look
• base

Examples

			a(0) = 1: (), the empty permutation.
a(3) = 1: 321 (down, down).
a(4) = 3: 1243, 1342, 2341 (up, up, down).
a(5) = 16: 21435, 21534, 31425, 31524, 32415, 32514, 41325, 41523, 42315, 42513, 43512, 51324, 51423, 52314, 52413, 53412 (down, up, down, up).
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).
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).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..4095

Crossrefs

Cf. A060351, A242783, A242784, A242785.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),
     `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),
      add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))
    end:
a:= n-> b(n, 0, 2*n):
seq(a(n), n=0..42);

Formula

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

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

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