

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.


8



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;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

"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 "sealevel" 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.
This sequence is a subsequence of A072601.  Jason Kimberley, Feb 08 2013
Define a map from this set onto the nonnegative integers as follows: set the output bit string to be empty representing zero; process the input string from left to right; when 1 occurs change the rightmost 0 in the output to 1; if there is no 0 in the output then prepend a 1; when 0 occurs in the input change the rightmost 1 in the output to 1; the definition of this sequence ensures that we always have a 1 in the output when a 0 occurs in the input. We this map is onto by showing the restriction to the subset Asubsequence is onto.  Jason Kimberley, Feb 08 2013


LINKS

Table of n, a(n) for n=1..66.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
A. Karttunen, Some notes on Catalan's Triangle
Index entries for sequences related to binary expansion of n


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), h1, i1); fi; NonDivingLatticeSequencesAux((2*x)+1, h+1, i1); fi; end;


CROSSREFS

Cf. A001405, A031443, A036990, A036991, A061855, A014486.
Sequence in context: A225354 A166111 A004762 * A214432 A110086 A107746
Adjacent sequences: A061851 A061852 A061853 * A061855 A061856 A061857


KEYWORD

nonn,base,easy


AUTHOR

Antti Karttunen, May 11 2001


STATUS

approved



