A071152 -id:A071152 - cp's OEIS frontend

A063171 Dyck language interpreted as binary numbers in ascending order.

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

Offset: 0

Reinhard Zumkeller, Jul 09 2001

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

			s -> ss -> 1s0s -> 11s00s -> 111000s -> 11100010

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).

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.
Paolo Xausa, A Mathematica implementation of Knuth's algorithms P and U.

Cf. A007088, A071153.

A014486 gives these terms as converted from decimal to binary system.

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

seq(convert(d, binary), d in select(isA014486, [seq(0..640)]));  # Peter Luschny, Mar 13 2024

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 *)

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

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

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 cA063171_list = list(islice(A063171_gen(),30)) # Chai Wah Wu, Nov 28 2023

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)).

a(0)=0 prepended by Joerg Arndt, Feb 27 2013

A071153 Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Original entry on oeis.org

0, 1, 20, 11, 300, 201, 210, 120, 111, 4000, 3001, 3010, 2020, 2011, 3100, 2101, 2200, 1300, 1201, 2110, 1210, 1120, 1111, 50000, 40001, 40010, 30020, 30011, 40100, 30101, 30200, 20300, 20201, 30110, 20210, 20120, 20111, 41000, 31001, 31010

Offset: 0

Antti Karttunen, May 14 2002

Note: this finite decimal representation works only up to the 6917th term, as the 6918th such word is already (10,0,0,0,0,0,0,0,0,0). The sequence A071154 shows the initial portion of this sequence sorted.

			The 11th term of A063171 is 10110010, corresponding to parenthesization ()(())(), thus its Łukasiewicz word is 3010. The 18th term of A063171 is 11011000, corresponding to parenthesization (()(())), thus its Łukasiewicz word is 1201. I.e., in the latter example there is one list on the top-level, which in turn contains two sublists, of which the first is zero elements long and the second is a sublist containing one empty sublist (the last zero is omitted).

A. Karttunen, Gatomorphisms and other excursions amidst the plane trees and parenthesizations (Includes the complete Scheme program for computing this sequence)
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz
Index entries for sequences related to parenthesizing

For n >= 1, the number of zeros in the term a(n) is given by A057514(n)-1.
The first digit of each term is given by A057515.
Cf. A014486, A059984, A059985, A071152, A071154.
Corresponding factorial walk encoding: A071155 (A071157, A071159).
a(n) = A079436(n)/10.

cp's OEIS Frontend

A063171 Dyck language interpreted as binary numbers in ascending order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python