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,5

Links

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

Formula

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

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

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

Example

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

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);

Crossrefs

Cf. A060351, A242783, A242784, A242785.

Sequence in context: A091273 A256931 A101405 * A193367 A322413 A298873

Adjacent sequences: A335305 A335306 A335307 * A335309 A335310 A335311

Keyword

nonn,look,base

Author

Alois P. Heinz, Sep 12 2020

Status

approved