login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063171 Dyck language interpreted as binary numbers in ascending order. 124
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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

(Which is actually a leading 0, shown only for zero so that it has a visible representation.) - Daniel Forgues, Feb 27 2013

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..2055

FindStat - Combinatorial Statistic Finder, Dyck paths

A. Karttunen, Illustration of initial terms up to size n=7

A. Karttunen, Catalan Automorphisms

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077, 2016.

FORMULA

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

EXAMPLE

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

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 *)

PROG

(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

CROSSREFS

a(n) = A071152(n)/2. A014486 gives these terms as converted from decimal to binary system. Cf. also A071153.

Sequence in context: A098753 A276758 A066489 * A075166 A071671 A075171

Adjacent sequences:  A063168 A063169 A063170 * A063172 A063173 A063174

KEYWORD

base,nonn

AUTHOR

Reinhard Zumkeller, Jul 09 2001

EXTENSIONS

Prepended a(0)=0, Joerg Arndt, Feb 27 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 09:42 EDT 2017. Contains 284060 sequences.