A350346 Binary numbers such that when read from right to left, the number of 0's never exceeds the number of 1's.

0, 1, 11, 101, 111, 1011, 1101, 1111, 10011, 10101, 10111, 11011, 11101, 11111, 100111, 101011, 101101, 101111, 110011, 110101, 110111, 111011, 111101, 111111, 1000111, 1001011, 1001101, 1001111, 1010011, 1010101, 1010111, 1011011, 1011101, 1011111, 1100111

Offset

1,3

Comments

Binary expansion of A036991 terms.

Dyck language interpreted as binary numbers in ascending order (inverse encode of A063171).

The first term a(1)=0 corresponds to an empty string, denote it NULL.

Restoring the leading 0's (need the same number of 0's and 1's) and then replacing "0" by the left parenthesis "(" and "1" by the right parenthesis ")" give well-formed parenthesis strings: 0 -> NULL, 1=01 -> (), 11=0011 -> (()), 101=0101 -> ()(), 111=000111 -> ((())), 1011=001011 -> (()()), 1101=001101 -> (())() and so on.

Chomsky-2 grammar with axiom s, terminal alphabet {0, 1} and three rules s -> ss, s -> 0s1, s -> 01 (compare A063171).

Links

Gennady Eremin, Table of n, a(n) for n = 1..5000

Gennady Eremin, Dyck Numbers, III. Enumeration and bijection with symmetric Dyck paths, arXiv:2302.02765 [math.CO], 2023.

Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318, 2023.

Formula

a(n) = A007088(A036991(n)). - Michel Marcus, Dec 26 2021

Example

s -> ss -> 0s1s -> 00s11s -> 000111s -> 00011101 = 11101.

Mathematica

Join[{0}, Select[Table[FromDigits[IntegerDigits[n, 2]], {n, 120}], Min[Accumulate[ Reverse[ IntegerDigits[#]]/.(0->-1)]]>=0&]] (* Harvey P. Dale, Apr 29 2022 *)

Prog

(Python)
def ok(n):
    if n == 0: return True
    count = {"0": 0, "1": 0}
    for bit in bin(n)[:1:-1]:
        count[bit] += 1
        if count["0"] > count["1"]: return False
    return True # A036991
nn = 1; print(1, 0)
for n in range(1, 23230):  # printing b-file
    if ok(n) == False: continue
    nn += 1; print(nn, bin(n)[2:])
(Python)
from itertools import count, islice
def A350346_gen(): # generator of terms
    yield 0
    for n in count(1):
        s = bin(n)[2:]
        c, l = 0, len(s)
        for i in range(l):
            c += int(s[l-i-1])
            if 2*c <= i:
                break
        else:
            yield int(s)
A350346_list = list(islice(A350346_gen(), 20)) # Chai Wah Wu, Dec 30 2021

Crossrefs

Cf. A007088, A036991, A014486, A063171.

Sequence in context: A264406 A057148 A076289 * A247647 A240602 A117697

Adjacent sequences: A350343 A350344 A350345 * A350347 A350348 A350349

Keyword

nonn,base

Author

Gennady Eremin, Dec 26 2021

Status

approved