cp's OEIS Frontend

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

%I A014486 #228 Aug 18 2025 06:28:48
%S A014486 0,2,10,12,42,44,50,52,56,170,172,178,180,184,202,204,210,212,216,226,
%T A014486 228,232,240,682,684,690,692,696,714,716,722,724,728,738,740,744,752,
%U A014486 810,812,818,820,824,842,844,850,852,856,866,868,872,880,906,908,914
%N A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.
%C A014486 The binary Dyck-Language (A063171) in decimal representation.
%C A014486 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 by A000108.
%C A014486 Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - _Benoit Cloitre_, Aug 18 2002
%C A014486 This list is the intersection of A061854 and A031443. - _Jason Kimberley_, Jan 18 2013
%C A014486 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
%C A014486 It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(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 Silva_ and _Michel Marcus_, May 01 2020
%C A014486 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 by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - _Gus Wiseman_, Nov 21 2022
%D A014486 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 A014486 Paolo Xausa, <a href="/A014486/b014486.txt">Table of n, a(n) for n = 0..23713</a> (terms 0..2500 from Franklin T. Adams-Watters).
%H A014486 Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit, <a href="https://arxiv.org/abs/1804.07996">Additive Number Theory via Approximation by Regular Languages</a>, arXiv:1804.07996 [cs.FL], 2018.
%H A014486 N. G. De Bruijn and B. J. M. Morselt, <a href="http://dx.doi.org/10.1016/S0021-9800(67)80111-X">A note on plane trees</a>, J. Combinatorial Theory 2 (1967), 27-34.
%H A014486 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 A014486 R. K. Guy, <a href="http://www.jstor.org/stable/2691503">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20.
%H A014486 Antti Karttunen, <a href="http://oeis.org/wiki/Catalan_ranking_and_unranking_functions">Catalan ranking and unranking functions</a>, OEIS Wiki.
%H A014486 Antti Karttunen, <a href="/A014486/a014486.pdf">Illustration of 626 initial terms (up to size n=7) with various combinatorial interpretations of Catalan numbers encoded by this sequence</a>.
%H A014486 Antti Karttunen, <a href="/A089408/a089408.c.txt">a089408.c - C program for computing this sequence and many of the related automorphisms</a>.
%H A014486 Antti Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/tab9766.htm">Some notes on Catalan's Triangle</a>.
%H A014486 Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625 [math.CO], 2020-2021.
%H A014486 D. L. Kreher and D. R. Stinson, <a href="http://www.math.mtu.edu/~kreher/cages.html">Combinatorial Algorithms, Generation, Enumeration and Search</a>, CRC Press, 1998.
%H A014486 Thomas Finn Lidbetter, <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/14254/Lidbetter_Thomas.pdf">Counting, Adding, and Regular Languages</a>, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
%H A014486 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 A014486 OEIS Wiki, <a href="/wiki/Combinatorial_interpretations_of_Catalan_numbers">Combinatorial interpretations of Catalan numbers</a>
%H A014486 Frank Ruskey, <a href="http://webhome.cs.uvic.ca/~ruskey/Publications/Thesis/Thesis.html">Algorithmic Solution of Two Combinatorial Problems</a>.
%H A014486 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers.html">Hipparchus, Plutarch, Schroeder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
%H A014486 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catalan.pdf">Exercises on Catalan and Related Numbers</a>.
%H A014486 Paolo Xausa, <a href="/A063171/a063171_5.txt">A Mathematica implementation of Knuth's algorithms P and U</a>.
%H A014486 <a href="/index/Ro#RootedTreePlanEncodings">Index entries for encodings of plane rooted trees</a> (various subsets of this sequence).
%H A014486 <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H A014486 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a> (permutations of natural numbers induced by various bijective operations acting on these structures)
%H A014486 <a href="/index/Li#ListFunsOfLisp">Index entries for the sequences induced by list functions of Lisp</a> (sequences induced by various other operations on these codes or the corresponding structures).
%e A014486 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:
%e A014486   0   0
%e A014486    \ /
%e A014486     1   0 0  (0)
%e A014486      \ /   \ /
%e A014486       1     1
%e A014486        \   /
%e A014486          1
%e A014486 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 function A014486->parenthesization given below.
%e A014486 From _Gus Wiseman_, Nov 21 2022: (Start)
%e A014486 The terms and corresponding ordered rooted trees begin:
%e A014486     0: o
%e A014486     2: (o)
%e A014486    10: (oo)
%e A014486    12: ((o))
%e A014486    42: (ooo)
%e A014486    44: (o(o))
%e A014486    50: ((o)o)
%e A014486    52: ((oo))
%e A014486    56: (((o)))
%e A014486   170: (oooo)
%e A014486   172: (oo(o))
%e A014486   178: (o(o)o)
%e A014486   180: (o(oo))
%e A014486   184: (o((o)))
%e A014486 (End)
%p A014486 # 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.
%p A014486 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;
%p A014486 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;
%p A014486 Mn := (n,x,y) -> binomial(2*n-x,n-((x+y)/2)) - binomial(2*n-x,n-1-((x+y)/2));
%p A014486 # Alternative:
%p A014486 bin := n -> ListTools:-Reverse(convert(n, base, 2)):
%p A014486 isA014486 := proc(n): local B, s, b; s := 0;
%p A014486     if n > 0 then
%p A014486       for b in bin(n) do
%p A014486           s := s + ifelse(b = 1, 1, -1);
%p A014486            if 0 > s then return false fi;
%p A014486       od fi;
%p A014486   s = 0 end:
%p A014486 select(isA014486, [seq(0..240)]);  # _Peter Luschny_, Mar 13 2024
%t A014486 cat[ n_ ] := (2 n)!/n!/(n+1)!; b2d[li_List] := Fold[2#1+#2&, 0, li]
%t A014486 d2b[n_Integer] := IntegerDigits[n, 2]
%t A014486 tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]
%t A014486 nexttree[t_] := Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]
%t A014486 wood[ n_ /; n<8 ] := NestList[ nexttree, tree[ n ], cat[ n ]-1 ]
%t A014486 Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten
%t A014486 (* Alternative code *)
%t A014486 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 *)
%t A014486 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 *)
%t A014486 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 *)
%t A014486 (* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
%t A014486 alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
%t A014486     FromDigits[#, 2]& /@ Reap[
%t A014486     While[True,
%t A014486         Sow[a]; a[[m]] = 0;
%t A014486         If[a[[m - 1]] == 0,
%t A014486             a[[--m]] = 1, j = m - 1; k = 2*n - 1;
%t A014486             While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
%t A014486             If[j == 1, Break[]];
%t A014486             a[[j]] = 1; m = 2*n - 1]
%t A014486     ]][[2, 1]]];
%t A014486 Join[{{0}, {2}}, Array[alist, 4, 2]] (* _Paolo Xausa_, Mar 16 2024 *)
%o A014486 (MIT/GNU Scheme) (define (A014486 n) (let ((w/2 (A072643 n))) (CatalanUnrank w/2 (if (zero? n) 0 (- n (A014137 (-1+ w/2)))))))
%o A014486 ;;; Here 'm' is the row on A009766 and 'y' is the position on row 'm' of A009766, both >= 0. The resulting totally balanced binary string is computed into variable 'a':
%o A014486 (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) (A009766 m (-1+ y))) (loop (* 2 a) (-1+ m) y rank (A009766 (-1+ m) y))))))
%o A014486 ;;; This converts the totally balanced binary string 'n' into the corresponding S-expression:
%o A014486 (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))))))
%o A014486 (define (cons2top! stack) (let ((ex-cdr (cdr stack))) (set-cdr! stack (car ex-cdr)) (set-car! ex-cdr stack) ex-cdr))
%o A014486 (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
%o A014486 (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
%o A014486 (SageMath)
%o A014486 def is_A014486(n) :
%o A014486     B = bin(n)[2::] if n != 0 else 0
%o A014486     s = 0
%o A014486     for b in B :
%o A014486         s += 1 if b=='1' else -1
%o A014486         if 0 > s : return False
%o A014486     return 0 == s
%o A014486 def A014486_list(n): return [k for k in (1..n) if is_A014486(k) ]
%o A014486 A014486_list(888) # _Peter Luschny_, Aug 10 2012
%o A014486 (Python)
%o A014486 from itertools import count, islice
%o A014486 from sympy.utilities.iterables import multiset_permutations
%o A014486 def A014486_gen(): # generator of terms
%o A014486     yield 0
%o A014486     for l in count(1):
%o A014486         for s in multiset_permutations('0'*l+'1'*(l-1)):
%o A014486             c, m = 0, (l<<1)-1
%o A014486             for i in range(m):
%o A014486                 if s[i] == '1':
%o A014486                     c += 2
%o A014486                 if c<i:
%o A014486                     break
%o A014486             else:
%o A014486                 yield (1<<m)+int(''.join(s),2)
%o A014486 A014486_list = list(islice(A014486_gen(),30)) # _Chai Wah Wu_, Nov 28 2023
%Y A014486 Characteristic function: A080116. Inverse function: A080300.
%Y A014486 The terms of binary width 2n are counted by A000108(n). Subset of A036990. 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.
%Y A014486 Cf. also A009766, A014137, A071156, A079436, A085184, A213704.
%Y A014486 Cf. A020988, A089309, A007814.
%Y A014486 Branches of the ordered tree are counted by A057515.
%Y A014486 Edges of the ordered tree are counted by A072643.
%Y A014486 The Matula-Goebel number of the ordered tree is A127301.
%Y A014486 The standard ranking of the ordered tree is A358523.
%Y A014486 The depth of the ordered tree is A358550.
%Y A014486 Nodes of the ordered tree are counted by A358551.
%Y A014486 Cf. A000081, A001263, A358505, A358524.
%K A014486 nonn,nice,easy,base,changed
%O A014486 0,2
%A A014486 _Wouter Meeussen_
%E A014486 Additional comments from _Antti Karttunen_, Aug 11 2000 and May 25 2004
%E A014486 Added a(0)=0 (which had been removed in June 2011), _Joerg Arndt_, Feb 27 2013