|
|
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
|
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
|
FindStat - Combinatorial Statistic Finder, Dyck paths.
|
|
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
|
|
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"]
(Python)
return [0] + [int(bin(k)[2::]) for k in range(1, limit) if is_A014486(k)]
(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))
|
|
CROSSREFS
|
A014486 gives these terms as converted from decimal to binary system.
|
|
KEYWORD
|
base,nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|