cp's OEIS Frontend

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.

%I A061854 #45 Sep 11 2023 12:32:01
%S A061854 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,
%T A061854 45,46,47,50,51,52,53,54,55,56,57,58,59,60,61,62,63,85,86,87,89,90,91,
%U A061854 92,93,94,95,101,102,103,105,106,107,108,109,110,111,113,114,115,116
%N 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.
%C A061854 "msb" = "most significant bit", A053644.
%C A061854 These encode lattice walks using steps (+1,+1) (= 1's in binary expansion) and (+1,-1) (= 0's in binary expansion) that start from the origin (0,0) and never "dive" under the "sea-level" y=0.
%C A061854 The number of such walks of length n (here: the terms of binary width n) is given by C(n,floor(n/2)) = A001405, which is based on the fact mentioned in Guy's article that the shallow diagonals of the Catalan triangle A009766 sum to A001405.
%C A061854 From _Jason Kimberley_, Feb 08 2013: (Start)
%C A061854 This sequence is a subsequence of A072601.
%C A061854 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, 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. (End)
%C A061854 The binary representation of a(n) is the numeric representation of the left half of a symmetric balanced string of parentheses with "(" representing 1 and ")" representing 0 (see comments and examples in A001405). Some of the numbers in this sequence cannot be realized as the 1-0-pattern of the odd/even positions of 1's in any row n of A237048 that determines the parts and their widths in the symmetric representation of sigma(n), see A352696. - _Hartmut F. W. Hoft_, Mar 29 2022
%H A061854 Harvey P. Dale, <a href="/A061854/b061854.txt">Table of n, a(n) for n = 1..1000</a>
%H A061854 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%H A061854 Antti Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/tab9766.htm">Some notes on Catalan's Triangle</a>
%H A061854 Thomas Finn Lidbetter, <a href="http://hdl.handle.net/10012/14254">Counting, Adding, and Regular Languages</a>, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
%H A061854 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%e A061854 From _Hartmut F. W. Hoft_, Mar 29 2022: (Start)
%e A061854 The columns in the table are the numbers n, the base-2 representation of n, the left half of the symmetric balanced string of parentheses corresponding to n, validity of the nondiving property for n, and associated number a(n):
%e A061854 1   1      (      True    a(1)
%e A061854 2   10     ()     True    a(2)
%e A061854 3   11     ((     True    a(3)
%e A061854 4   100    ())    False    -
%e A061854 5   101    ()(    True    a(4)
%e A061854 6   110    (()    True    a(5)
%e A061854 7   111    (((    True    a(6)
%e A061854 8   1000   ()))   False    -
%e A061854 9   1001   ())(   False    -
%e A061854 10  1010   ()()   True    a(7)
%e A061854 ...
%e A061854 20  10100  ()())  False    -
%e A061854 21  10101  ()()(  True    a(13)
%e A061854 ...
%e A061854 (End)
%p A061854 # We use a simple backtracking algorithm: map(op,[seq(NonDivingLatticeSequences(j),j=1..10)]);
%p A061854 NDLS_GLOBAL := []; NonDivingLatticeSequences := proc(n) global NDLS_GLOBAL; NDLS_GLOBAL := []; NonDivingLatticeSequencesAux(0,0,n); RETURN(NDLS_GLOBAL); end;
%p A061854 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;
%t A061854 a061854[n_] := Select[Range[n], !MemberQ[FoldList[#1+If[#2>0, 1, -1]&, 0, IntegerDigits[n, 2]], -1]]
%t A061854 a061854[116] (* _Hartmut F. W. Hoft_, Mar 29 2022 *)
%t A061854 Select[Range[120],Min[Accumulate[IntegerDigits[#,2]/.(0->-1)]]>=0&] (* _Harvey P. Dale_, Sep 11 2023 *)
%Y A061854 Cf. A001405, A031443, A036990, A036991, A061855, A014486.
%Y A061854 Cf. A237593, A237048, A237591, A237593, A352696.
%K A061854 nonn,base,easy
%O A061854 1,2
%A A061854 _Antti Karttunen_, May 11 2001