A063171 Dyck language interpreted as binary numbers in ascending order.

0, 10, 1010, 1100, 101010, 101100, 110010, 110100, 111000, 10101010, 10101100, 10110010, 10110100, 10111000, 11001010, 11001100, 11010010, 11010100, 11011000, 11100010, 11100100, 11101000, 11110000, 1010101010, 1010101100, 1010110010, 1010110100, 1010111000

Offset: 0

Author

Reinhard Zumkeller, Jul 09 2001

Keywords

• base
• nonn

Comments

a(n) is the binary expansion of A014486(n). - Joerg Arndt, Feb 27 2013

Replacing "1" by "(" and "0" by ")" yields well-formed bracket expressions (the first term being the empty string)

, (), ()(), (()), ()()(), ()(()), (())(), (()()), ((())), ()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((()))), ()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()(()()()), ()(()(())), ()((()))(), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), (()()())(), (()()()()), (()()(())), (()(()))(), (()(())()), (()(()())), (()((()))), ((()))()(), ((()))(()), ((())())(), ((())()()), ((())(())), ((()()))(), ((()())()), ((()()())), ((()(()))), (((())))(), (((()))()), (((())())), (((()()))), ((((()))))

The term a(0)=0 stands for the empty string. - Joerg Arndt, Feb 27 2013

Examples

			s -> ss -> 1s0s -> 11s00s -> 111000s -> 11100010
		

References

• Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).

Links

• Paolo Xausa, Table of n, a(n) for n = 0..23713 (terms 0..2055 from Reinhard Zumkeller)
• Gennady Eremin, Dynamics of balanced parentheses, lexicographic series and Dyck polynomials, arXiv:1909.07675 [math.CO], 2019.
• FindStat - Combinatorial Statistic Finder, Dyck paths.
• Antti Karttunen, Illustration of initial terms up to size n=7.
• Antti Karttunen, Catalan Automorphisms.
• Zoltán Kása, Generating and ranking of Dyck words, arXiv:1002.2625 [cs.DM], Feb 2010.
• Peter Luschny, A Python implementation of Knuth's algorithms P and U.
• R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
• Indranil Ghosh, Python program for computing this sequence.
• Paolo Xausa, A Mathematica implementation of Knuth's algorithms P and U.

Crossrefs

Cf. A007088, A071153.

A014486 gives these terms as converted from decimal to binary system.

Programs

Haskell

import Data.Set (singleton, deleteFindMin, union, fromList)
newtype Word = Word String deriving (Eq, Show, Read)
instance Ord Word where
   Word us <= Word vs | length us == length vs = us <= vs
                      | otherwise              = length us <= length vs
a063171 n = a063171_list !! (n-1)
a063171_list = dyck $ singleton (Word "S") where
   dyck s | null ws   = (read w :: Integer) : dyck s'
          | otherwise = dyck $ union s' (fromList $ concatMap gen ws)
          where ws = filter ((== 'S') . head . snd) $
                            map (`splitAt` w) [0..length w - 1]
                (Word w, s') = deleteFindMin s
   gen (us,vs) = map (Word . (us ++) . (++ tail vs)) ["10", "1S0", "SS"]
-- Reinhard Zumkeller, Mar 09 2011

Maple

seq(convert(d, binary), d in select(isA014486, [seq(0..640)]));  # Peter Luschny, Mar 13 2024

Mathematica

balancedQ[0] = True; balancedQ[n_] := (s = 0; Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0]); FromDigits /@ IntegerDigits[ Select[Range[0, 684], balancedQ], 2] (* Jean-François Alcover, Jul 24 2013 *)
(* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
    FromDigits /@ Reap[
    While[True,
        Sow[a]; a[[m]] = 0;
        If[a[[m - 1]] == 0,
            a[[--m]] = 1, j = m - 1; k = 2*n - 1;
            While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
            If[j == 1, Break[]];
            a[[j]] = 1; m = 2*n - 1]
    ]][[2, 1]]];
Join[{{0}, {10}}, Array[alist, 4, 2]] (* Paolo Xausa, Mar 15 2024 *)

PARI

a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, for(i=1, if(t, valuation(t, 10), 0)+1, listput(~c, t*100+10^i))); a[r+1]=Vec(c)); a; \\ Ruud H.G. van Tol, Jun 02 2024

Python

def A063171_list(limit):
    return [0] + [int(bin(k)[2::]) for k in range(1, limit) if is_A014486(k)]
print(A063171_list(700))  # Peter Luschny, Jul 30 2022

Python

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A063171_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA063171_list = list(islice(A063171_gen(),30)) # Chai Wah Wu, Nov 28 2023

Formula

Chomsky-2 grammar with axiom s, terminal alphabet {0, 1} and three rules s -> ss, s -> 1s0, s -> 10.

a(n) = A071152(n)/2.

a(n) = A007088(A014486(n)).

Extensions

a(0)=0 prepended by Joerg Arndt, Feb 27 2013