

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.


374



0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, 906, 908, 914
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The binary DyckLanguage (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, noncrossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.
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 nth row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k1) + D(n, k1) 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
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


REFERENCES

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, AddisonWesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).


LINKS



EXAMPLE

a(19) = 226_10 = 11100010_2 = A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depthfirst 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 Sexpression 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.
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

# 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+m1) then y := y+1; a := 2*a + 1; else lo := lo+m; y := y1; a := 2*a; fi; od; return a; end;
Mn := (n, x, y) > binomial(2*nx, n((x+y)/2))  binomial(2*nx, n1((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:


MATHEMATICA

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 ]] (* JeanFranç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 *)


PROG

(MIT/GNU Scheme) (define (A014486 n) (let ((w/2 (A072643 n))) (CatalanUnrank w/2 (if (zero? n) 0 ( n (A014137 (1+ w/2)))))))
;;; 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':
(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))))))
;;; This converts the totally balanced binary string 'n' into the corresponding Sexpression:
(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 ((excdr (cdr stack))) (setcdr! stack (car excdr)) (setcar! excdr stack) excdr))
(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, N1, 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)
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
(Python)
from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen(): # generator of terms
yield 0
for l in count(1):
for s in multiset_permutations('0'*l+'1'*(l1)):
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)


CROSSREFS

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.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The MatulaGoebel number of the ordered tree is A127301.
The standard ranking of the ordered tree is A358523.
The depth of the ordered tree is A358550.
Nodes of the ordered tree are counted by A358551.


KEYWORD

nonn,nice,easy,base,changed


AUTHOR



EXTENSIONS

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


STATUS

approved



