Search: id:A014486
Results 1-1 of 1 results found.

%I A014486
%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
%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 (benoit7848c(AT)orange.fr), 
               Aug 18 2002
%D A014486 N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial 
               Theory 2 (1967), 27-34
%D A014486 R. K. Guy, The second strong law of small numbers. Math. Mag. 63 (1990), 
               no. 1, 3-20.
%H A014486 Franklin T. Adams-Watters, <a href="b014486.txt">Table of n, a(n) for 
               n = 0..2500</a>
%H A014486 A. Karttunen, <a href="a014486.ps.gz">Illustration of 626 initial terms 
               (up to size n=7) with various structures and natural isomorphisms 
               between them</a>
%H A014486 A. Karttunen, <a href="a089408.c.txt">gatomorf.c - C program for computing 
               this sequence and many of the related automorphisms</a>
%H A014486 A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/tab9766.htm">
               Some notes on Catalan's Triangle</a>
%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 F. Ruskey, <a href="http://www.cs.uvic.ca/~fruskey/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 <a href="Sindx_Ro.html#RootedTreePlanEncodings">Index entries for encodings 
               of plane rooted trees</a> (various subsets of this sequence).
%H A014486 <a href="Sindx_Par.html#parens">Index entries for sequences related to 
               parenthesizing</a>
%H A014486 <a href="Sindx_Per.html#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="Sindx_Li.html#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[dec] = 11100010[bin] = 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 epression as above, but surrounded by extra parentheses. 
               This mapping is effected by the Scheme function A014486->parenthesization 
               given below.
%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 gatomorf.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));
%t A014486 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}]]
%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
%o A014486 (MIT 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'): (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:) (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))
%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, A072643, A079436, A085184.
%Y A014486 Sequence in context: A055701 A154391 A035928 this_sequence A166751 A071162 
               A075165
%Y A014486 Adjacent sequences: A014483 A014484 A014485 this_sequence A014487 A014488 
               A014489
%K A014486 nonn,nice,easy,base
%O A014486 0,2
%A A014486 Wouter Meeussen (wouter.meeussen(AT)pandora.be)
%E A014486 Additional comments from Antti Karttunen, Aug 11 2000 and May 25 2004.

Search completed in 0.003 seconds