login
Dyck language interpreted as binary numbers in ascending order.
142

%I #113 Jun 02 2024 14:33:35

%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 Antti 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 Antti 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

%o (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

%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