|
Search: id:A061854
|
|
|
| A061854 |
|
Nondiving binary sequences: numbers which in base 2 have at least the same number of 1's as 0's and reading the binary expansion from left (msb) to right (least significant bit), the number of 0's never exceeds the number of 1's. |
|
+0
7
|
|
| 1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 101, 102, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
"msb" = "most significant bit", A053644.
These encode lattice walks using steps (+1,+1) (= 1's in binary expansion) and (+1,-1) (= 0's in binary expansion) that start from origin (0,0) and never "dive" under the "sea-level" y=0.
The number of such walks of length n (here: the terms of binary width n) is given by C(n,[ n/2 ]) = A001405, which is based on fact mentioned in Guy's article that the shallow diagonals of the Catalan Triangle A009766 sum to A001405.
|
|
LINKS
|
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
A. Karttunen, Some notes on Catalan's Triangle
|
|
MAPLE
|
# We use a simple backtracking algorithm: map(op, [seq(NonDivingLatticeSequences(j), j=1..10)]);
NDLS_GLOBAL := []; NonDivingLatticeSequences := proc(n) global NDLS_GLOBAL; NDLS_GLOBAL := []; NonDivingLatticeSequencesAux(0, 0, n); RETURN(NDLS_GLOBAL); end;
NonDivingLatticeSequencesAux := proc(x, h, i) global NDLS_GLOBAL; if(0 = i) then NDLS_GLOBAL := [op(NDLS_GLOBAL), x]; else if(h > 0) then NonDivingLatticeSequencesAux((2*x), h-1, i-1); fi; NonDivingLatticeSequencesAux((2*x)+1, h+1, i-1); fi; end;
|
|
CROSSREFS
|
A001405, A031443, A036990, A036991, A061855.
Sequence in context: A102750 A166111 A004762 this_sequence A089105 A110086 A107746
Adjacent sequences: A061851 A061852 A061853 this_sequence A061855 A061856 A061857
|
|
KEYWORD
|
nonn,base,easy
|
|
AUTHOR
|
Antti Karttunen May 11 2001
|
|
|
Search completed in 0.002 seconds
|
