0,2

The binary Dyck-Language (A063171) in decimal representation.

These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated byA000108.

Is Sum_{k=1..n} a(k) / n^(5/2) bounded? -Benoit Cloitre,Aug 18 2002

This list is the intersection ofA061854andA031443.-Jason Kimberley,Jan 18 2013

The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")" ) having a(0) = 0 will do since it would stand for the empty string where the "0" s and "1" s are balanced (hence the parentheses are balanced). -Daniel Forgues,Feb 17 2013

It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length isA000108(n) and that is defined recursively by B(n,0) =A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). -Raúl Mario Torres SilvaandMichel Marcus,May 01 2020

This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given byA358505,while (2) the standard ranking of trees ordered by binary encoding is given byA358523.-Gus Wiseman,Nov 21 2022

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..2500 from Franklin T. Adams-Watters).

Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit,Additive Number Theory via Approximation by Regular Languages,arXiv:1804.07996 [cs.FL], 2018.

N. G. De Bruijn and B. J. M. Morselt,A note on plane trees,J. Combinatorial Theory 2 (1967), 27-34.

Gennady Eremin,Dynamics of balanced parentheses, lexicographic series and Dyck polynomials,arXiv:1909.07675 [math.CO], 2019.

R. K. Guy,The Second Strong Law of Small Numbers,Math. Mag, 63 (1990), no. 1, 3-20.

Antti Karttunen,Catalan ranking and unranking functions,OEIS Wiki.

Antti Karttunen,Illustration of 626 initial terms (up to size n=7) with various combinatorial interpretations of Catalan numbers encoded by this sequence.

Antti Karttunen,a089408.c - C program for computing this sequence and many of the related automorphisms.

Antti Karttunen,Some notes on Catalan's Triangle.

Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang,Finding structure in sequences of real numbers via graph theory: a problem list,arXiv:2012.04625 [math.CO], 2020-2021.

D. L. Kreher and D. R. Stinson,Combinatorial Algorithms, Generation, Enumeration and Search,CRC Press, 1998.

Thomas Finn Lidbetter,Counting, Adding, and Regular Languages,Master's Thesis, University of Waterloo, Ontario, Canada, 2018.

R. J. Mathar,Topologically Distinct Sets of Non-intersecting Circles in the Plane,arXiv:1603.00077 [math.CO], 2016.

OEIS Wiki,Combinatorial interpretations of Catalan numbers

F. Ruskey,Algorithmic Solution of Two Combinatorial Problems.

R. P. Stanley,Hipparchus, Plutarch, Schroeder and Hough,Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

R. P. Stanley,Exercises on Catalan and Related Numbers.

Paolo Xausa,A Mathematica implementation of Knuth's algorithms P and U.

Index entries for encodings of plane rooted trees(various subsets of this sequence).

Index entries for signature-permutations induced by Catalan automorphisms(permutations of natural numbers induced by various bijective operations acting on these structures)

Index entries for the sequences induced by list functions of Lisp(sequences induced by various other operations on these codes or the corresponding structures).

a(19) = 226_10 = 11100010_2 =A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depth-first fashion, with 1's in binary expansion standing for internal (branching) nodes and 0's for leaves:

0 0

\ /

1 0 0 (0)

\ / \ /

1 1

\ /

1

Note that in this coding scheme the last leaf of the binary trees (here in parentheses) is implicit. This tree can be also converted to a particular S-expression in languages like Lisp, Scheme and Prolog, if we interpret its internal nodes (1's) as cons cells with each leftward leaning branch being the "car" and the rightward leaning branch the "cdr" part of the pair, with the terminal nodes (0's) being ()'s (NILs). Thus we have (cons (cons (cons () ()) ()) (cons () ())) = '( ( ( (). () ). () ). ( (). () ) ) = (((())) ()) i.e., the same bracket expression as above, but surrounded by extra parentheses. This mapping is performed by the Scheme functionA014486->parenthesization given below.

FromGus Wiseman,Nov 21 2022: (Start)

The terms and corresponding ordered rooted trees begin:

0: o

2: (o)

10: (oo)

12: ((o))

42: (ooo)

44: (o(o))

50: ((o)o)

52: ((oo))

56: (((o)))

170: (oooo)

172: (oo(o))

178: (o(o)o)

180: (o(oo))

184: (o((o)))

(End)

# Maple procedure CatalanUnrank is adapted from the algorithm 3.24 of the CAGES book and the Scheme function CatalanUnrank from Ruskey's thesis. See the a089408.c program for the corresponding C procedures.

CatalanSequences:= proc(upto_n) local n, a, r; a:= []; for n from 0 to upto_n do for r from 0 to (binomial(2*n, n)/(n+1))-1 do a:= [op(a), CatalanUnrank(n, r)]; od; od; return a; end;

CatalanUnrank:= proc(n, rr) local r, x, y, lo, m, a; r:= (binomial(2*n, n)/(n+1))-(rr+1); y:= 0; lo:= 0; a:= 0; for x from 1 to 2*n do m:= Mn(n, x, y+1); if(r <= lo+m-1) then y:= y+1; a:= 2*a + 1; else lo:= lo+m; y:= y-1; a:= 2*a; fi; od; return a; end;

Mn:= (n, x, y) -> binomial(2*n-x, n-((x+y)/2)) - binomial(2*n-x, n-1-((x+y)/2));

# Alternative:

bin:= n -> ListTools:-Reverse(convert(n, base, 2)):

isA014486:= proc(n): local B, s, b; s:= 0;

if n > 0 then

for b in bin(n) do

s:= s + ifelse(b = 1, 1, -1);

if 0 > s then return false fi;

od fi;

s = 0 end:

select(isA014486, [seq(0..240)]); #Peter Luschny,Mar 13 2024

cat[ n_ ]:= (2 n)!/n!/(n+1)!; b2d[li_List]:= Fold[2#1+#2&, 0, li]

d2b[n_Integer]:= IntegerDigits[n, 2]

tree[n_]:= Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]

nexttree[t_]:= Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]

wood[ n_ /; n<8 ]:= NestList[ nexttree, tree[ n ], cat[ n ]-1 ]

Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten

tbQ[n_]:=Module[{idn2=IntegerDigits[n, 2]}, Count[idn2, 1]==Length[idn2]/2&&Min[Accumulate[idn2/.{0->-1}]]>=0]; Join[{0}, Select[Range[900], tbQ]] (*Harvey P. Dale,Jul 04 2013 *)

balancedQ[0] = True; balancedQ[n_]:= Module[{s = 0}, Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0] ];A014486= FromDigits /@ IntegerDigits[Select[Range[0, 1000], balancedQ ]] (*Jean-François Alcover,Mar 05 2016 *)

A014486Q[0] = True; A014486Q[n_]:= Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; Select[Range[0, 880], A014486Q] (*JungHwan Min,Dec 11 2016 *)

(* 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[#, 2]& /@ 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}, {2}}, Array[alist, 4, 2]] (*Paolo Xausa,Mar 16 2024 *)

(MIT/GNU Scheme) (define (A014486n) (let ((w/2 (A072643n))) (CatalanUnrank w/2 (if (zero? n) 0 (- n (A014137(-1+ w/2)))))))

;;; Here 'm' is the row onA009766and 'y' is the position on row 'm' ofA009766,both >= 0. The resulting totally balanced binary string is computed into variable 'a':

(define (CatalanUnrank size rank) (let loop ((a 0) (m (-1+ size)) (y size) (rank rank) (c (A009766(-1+ size) size))) (if (negative? m) a (if (>= rank c) (loop (1+ (* 2 a)) m (-1+ y) (- rank c) (A009766m (-1+ y))) (loop (* 2 a) (-1+ m) y rank (A009766(-1+ m) y))))))

;;; This converts the totally balanced binary string 'n' into the corresponding S-expression:

(define (A014486->parenthesization n) (let loop ((n n) (stack (list (list)))) (cond ((zero? n) (car stack)) ((zero? (modulo n 2)) (loop (floor->exact (/ n 2)) (cons (list) stack))) (else (loop (floor->exact (/ n 2)) (cons2top! stack))))))

(define (cons2top! stack) (let ((ex-cdr (cdr stack))) (set-cdr! stack (car ex-cdr)) (set-car! ex-cdr stack) ex-cdr))

(PARI) isA014486(n)=my(v=binary(n), t=0); for(i=1, #v, t+=if(v[i], 1, -1); if(t<0, return(0))); t==0 \\Charles R Greathouse IV,Jun 10 2011

(PARI) a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, my(v=if(t, valuation(t, 2), 0)); for(i=0, v, listput(~c, (t<<2)+(2<<i)))); a[r+1]=Vec(c)); a; \\Ruud H.G. van Tol,May 16 2024

(SageMath)

def is_A014486(n):

B = bin(n)[2::] if n!= 0 else 0

s = 0

for b in B:

s += 1 if b=='1' else -1

if 0 > s: return False

return 0 == s

defA014486_list(n): return [k for k in (1..n) if is_A014486(k) ]

A014486_list(888) #Peter Luschny,Aug 10 2012

(Python)

from itertools import count, islice

from sympy.utilities.iterables import multiset_permutations

defA014486_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 (1<<m)+int(''.join(s), 2)

A014486_list = list(islice(A014486_gen(), 30)) #Chai Wah Wu,Nov 28 2023

Characteristic function:A080116.Inverse function:A080300.

The terms of binary width 2n are counted byA000108(n). Subset ofA036990.Number of peaks in each mountain (number of leaves in rooted plane general trees):A057514.Number of trailing zeros in the binary expansion:A080237.First differences:A085192.

Cf. alsoA009766,A014137,A071156,A079436,A085184,A213704.

Cf.A020988,A089309,A007814.

Branches of the ordered tree are counted byA057515.

Edges of the ordered tree are counted byA072643.

The Matula-Goebel number of the ordered tree isA127301.

The standard ranking of the ordered tree isA358523.

The depth of the ordered tree isA358550.

Nodes of the ordered tree are counted byA358551.

Cf.A000081,A001263,A358505,A358524.

Sequence in context:A186630A154391A035928*A166751A216649A071162

Adjacent sequences:A014483A014484A014485*A014487A014488A014489

nonn,nice,easy,base

Additional comments fromAntti Karttunen,Aug 11 2000 and May 25 2004

Added a(0)=0 (which had been removed in June 2011),Joerg Arndt,Feb 27 2013

approved