login
The OEIS is supported by the many generous donors 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. 136
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 (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
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.
A. Karttunen, Catalan Automorphisms.
Zoltán Kása, Generating and ranking of Dyck words, arXiv:1002.2625 [cs.DM], Feb 2010.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
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)).
EXAMPLE
s -> ss -> 1s0s -> 11s00s -> 111000s -> 11100010
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 *)
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
(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 c<i:
break
else:
yield 10**m+int(''.join(s))
A063171_list = list(islice(A063171_gen(), 30)) # Chai Wah Wu, Nov 28 2023
CROSSREFS
A014486 gives these terms as converted from decimal to binary system.
Sequence in context: A098753 A276758 A066489 * A075166 A071671 A075171
KEYWORD
base,nonn,changed
AUTHOR
Reinhard Zumkeller, Jul 09 2001
EXTENSIONS
a(0)=0 prepended by 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)