login
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).
5
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
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
KEYWORD
nonn,look,base
AUTHOR
Alois P. Heinz, Sep 12 2020
STATUS
approved