|
|
A063171
|
|
Dyck language interpreted as binary numbers in ascending order.
|
|
125
|
|
|
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
Gennady Eremin, Dynamics of balanced parentheses, lexicographic series and Dyck polynomials, arXiv:1909.07675 [math.CO], 2019.
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.
Indranil Ghosh, Python program for computing this sequence
|
|
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
|
|
|
|