|
%I #107 Mar 15 2024 21:30:27
%S 0,10,1010,1100,101010,101100,110010,110100,111000,10101010,10101100,
%T 10110010,10110100,10111000,11001010,11001100,11010010,11010100,
%U 11011000,11100010,11100100,11101000,11110000,1010101010,1010101100,1010110010,1010110100,1010111000
%N Dyck language interpreted as binary numbers in ascending order.
%C a(n) is the binary expansion of A014486(n). - _Joerg Arndt_, Feb 27 2013
%C Replacing "1" by "(" and "0" by ")" yields well-formed bracket expressions (the first term being the empty string)
%C , (), ()(), (()), ()()(), ()(()), (())(), (()()), ((())), ()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((()))), ()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()(()()()), ()(()(())), ()((()))(), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), (()()())(), (()()()()), (()()(())), (()(()))(), (()(())()), (()(()())), (()((()))), ((()))()(), ((()))(()), ((())())(), ((())()()), ((())(())), ((()()))(), ((()())()), ((()()())), ((()(()))), (((())))(), (((()))()), (((())())), (((()()))), ((((()))))
%C The term a(0)=0 stands for the empty string. - _Joerg Arndt_, Feb 27 2013
%D 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).
%H Paolo Xausa, <a href="/A063171/b063171.txt">Table of n, a(n) for n = 0..23713</a> (terms 0..2055 from Reinhard Zumkeller)
%H Gennady Eremin, <a href="https://arxiv.org/abs/1909.07675">Dynamics of balanced parentheses, lexicographic series and Dyck polynomials</a>, arXiv:1909.07675 [math.CO], 2019.
%H FindStat - Combinatorial Statistic Finder, <a href="https://www.findstat.org/CollectionsDatabase/DyckPaths/">Dyck paths</a>.
%H A. Karttunen, <a href="https://web.archive.org/web/20070202072844/http://ndirty.cute.fi/~karttu/matikka/Nekomorphisms/a014486.ps.gz">Illustration of initial terms up to size n=7</a>.
%H A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a>.
%H Zoltán Kása, <a href="https://doi.org/10.48550/arXiv.1002.2625">Generating and ranking of Dyck words</a>, arXiv:1002.2625 [cs.DM], Feb 2010.
%H Peter Luschny, <a href="/A063171/a063171_1.txt">A Python implementation of Knuth's algorithms P and U</a>.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1603.00077">Topologically Distinct Sets of Non-intersecting Circles in the Plane</a>, arXiv:1603.00077 [math.CO], 2016.
%H Indranil Ghosh, <a href="/A063171/a063171.txt">Python program for computing this sequence</a>.
%H Paolo Xausa, <a href="/A063171/a063171_5.txt">A Mathematica implementation of Knuth's algorithms P and U</a>.
%F Chomsky-2 grammar with axiom s, terminal alphabet {0, 1} and three rules s -> ss, s -> 1s0, s -> 10.
%F a(n) = A071152(n)/2.
%F a(n) = A007088(A014486(n)).
%e s -> ss -> 1s0s -> 11s00s -> 111000s -> 11100010
%p seq(convert(d, binary), d in select(isA014486, [seq(0..640)])); # _Peter Luschny_, Mar 13 2024
%t 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 *)
%t (* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
%t alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
%t FromDigits /@ Reap[
%t While[True,
%t Sow[a]; a[[m]] = 0;
%t If[a[[m - 1]] == 0,
%t a[[--m]] = 1, j = m - 1; k = 2*n - 1;
%t While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
%t If[j == 1, Break[]];
%t a[[j]] = 1; m = 2*n - 1]
%t ]][[2, 1]]];
%t Join[{{0}, {10}}, Array[alist, 4, 2]] (* _Paolo Xausa_, Mar 15 2024 *)
%o (Haskell)
%o import Data.Set (singleton, deleteFindMin, union, fromList)
%o newtype Word = Word String deriving (Eq, Show, Read)
%o instance Ord Word where
%o Word us <= Word vs | length us == length vs = us <= vs
%o | otherwise = length us <= length vs
%o a063171 n = a063171_list !! (n-1)
%o a063171_list = dyck $ singleton (Word "S") where
%o dyck s | null ws = (read w :: Integer) : dyck s'
%o | otherwise = dyck $ union s' (fromList $ concatMap gen ws)
%o where ws = filter ((== 'S') . head . snd) $
%o map (`splitAt` w) [0..length w - 1]
%o (Word w, s') = deleteFindMin s
%o gen (us,vs) = map (Word . (us ++) . (++ tail vs)) ["10", "1S0", "SS"]
%o -- _Reinhard Zumkeller_, Mar 09 2011
%o (Python)
%o def A063171_list(limit):
%o return [0] + [int(bin(k)[2::]) for k in range(1, limit) if is_A014486(k)]
%o print(A063171_list(700)) # _Peter Luschny_, Jul 30 2022
%o (Python)
%o from itertools import count, islice
%o from sympy.utilities.iterables import multiset_permutations
%o def A063171_gen(): # generator of terms
%o yield 0
%o for l in count(1):
%o for s in multiset_permutations('0'*l+'1'*(l-1)):
%o c, m = 0, (l<<1)-1
%o for i in range(m):
%o if s[i] == '1':
%o c += 2
%o if c<i:
%o break
%o else:
%o yield 10**m+int(''.join(s))
%o A063171_list = list(islice(A063171_gen(),30)) # _Chai Wah Wu_, Nov 28 2023
%Y Cf. A007088, A071153.
%Y A014486 gives these terms as converted from decimal to binary system.
%K base,nonn
%O 0,2
%A _Reinhard Zumkeller_, Jul 09 2001
%E a(0)=0 prepended by _Joerg Arndt_, Feb 27 2013
|
