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.
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.
FORMULA
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))
(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
CROSSREFS
KEYWORD
base,nonn
AUTHOR
Reinhard Zumkeller, Jul 09 2001
EXTENSIONS
a(0)=0 prepended by Joerg Arndt, Feb 27 2013
STATUS
approved