A014486 -id:A014486 - cp's OEIS frontend

A089855 Permutation of natural numbers induced by Catalan Automorphism *A089855 acting on the binary trees/parenthesizations encoded by A014486/A063171.

0, 1, 2, 3, 4, 5, 7, 8, 6, 9, 10, 11, 12, 13, 17, 18, 20, 21, 22, 16, 19, 14, 15, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 44, 47, 53, 56, 60, 42, 51, 37, 38, 43, 52, 39, 40, 41, 65, 66, 67, 68, 69, 70, 71, 72

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.A...B...........B...C
..\./.............\./
...x...C....-->....x...A...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . c) . a) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp if possible, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A089857. a(n) = A089860(A069770(n)) = A069770(A074680(n)) = A057163(A089853(A057163(n))). Row 9 of A089840.

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089855) added by Antti Karttunen, Jun 04 2011

A089857 Permutation of natural numbers induced by Catalan Automorphism *A089857 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 6, 7, 9, 10, 11, 12, 13, 21, 22, 19, 14, 15, 20, 16, 17, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 58, 59, 62, 63, 64, 56, 60, 51, 37, 38, 52, 39, 40, 41, 57, 61, 53, 42, 43, 54, 44, 45, 46, 55, 47, 48, 49, 50, 65, 66, 67, 68, 69, 70, 71, 72

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

.A...B...........C...A
..\./.............\./
...x...C....-->....x...B...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . a) . b) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 11 of A089840. Inverse of A089855. a(n) = A074679(A069770(n)) = A069770(A089862(n)) = A057163(A089851(A057163(n))).

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089857) added by Antti Karttunen, Jun 04 2011

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

0, 1, 3, 2, 8, 6, 7, 4, 5, 22, 19, 20, 14, 15, 21, 16, 17, 9, 10, 18, 11, 12, 13, 64, 60, 61, 51, 52, 62, 53, 54, 37, 38, 55, 39, 40, 41, 63, 56, 57, 42, 43, 58, 44, 45, 23, 24, 46, 25, 26, 27, 59, 47, 48, 28, 29, 49, 30, 31, 32, 50, 33, 34, 35, 36, 196, 191, 192, 177, 178

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated clockwise.

In A057161 and A057162, the cycles between A014138(n-1)-th and A014138(n)-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A001683(n+2) equivalence classes of flexagons (or unlabeled plane boron trees), thus the latter sequence can be counted with the Maple procedure A057162_CycleCounts given below. Cf. also the comments in A057161.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057161.
Also, an "ENIPS"-transform of A069773, and thus occurs as row 17 of A130402.
Other related permutations: A057163, A057164, A057501, A057503, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularizationR(A014486[n]))
RotateTriangularizationR := n -> ReflectBinTree(RotateTriangularization(ReflectBinTree(n)));
with(group); A057162_CycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,RotateTriangularization(CatalanUnrank(n,r)))]; od; a := [op(a),(`if`((n < 2),1,nops(convert(b,'disjcyc'))))]; od; RETURN(a); end;
# See also the code in A057161.

As a composition of related permutations:
a(n) = A069768(A057508(n)).
a(n) = A057163(A057161(A057163(n))).
a(n) = A057164(A057503(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 143.]

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 56, 153, 451, 1357, 4212, 13308, 42898, 140276, 465324, 1561955, 5300285, 18156813, 62732842, 218405402, 765657940

Offset: 0

Antti Karttunen Sep 03 2000

It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences related to rooted trees
A. Karttunen, C-program for computing empirically the initial terms of this sequence

CountCycles given in A057502, for other procedures, follow A057511 and A057501.
Similarly generated sequences: A001683, A002995, A003239, A038775, A057507. Cf. also A000081.
Occurs for first time in A073201 as row 12. Cf. A057546 and also A000081.

A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
# Or empirically:
DeepRotatePermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,DeepRotateL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;

a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.] - Antti Karttunen, Jan 03 2003

A057514 Number of peaks in mountain ranges encoded by A014486, number of leaves in the corresponding rooted plane trees (the root node is never counted as a leaf).

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 2, 2, 1, 4, 3, 3, 3, 2, 3, 2, 3, 3, 2, 2, 2, 2, 1, 5, 4, 4, 4, 3, 4, 3, 4, 4, 3, 3, 3, 3, 2, 4, 3, 3, 3, 2, 4, 3, 4, 4, 3, 3, 3, 3, 2, 3, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2, 2, 1, 6, 5, 5, 5, 4, 5, 4, 5, 5, 4, 4, 4, 4, 3, 5, 4, 4, 4, 3, 5, 4, 5, 5, 4, 4, 4, 4, 3, 4, 3, 4, 4, 3, 4, 4, 4, 3, 3, 3, 3

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Sum_{i=A014137(n)..(A014137(n+1)-1)} a(i) = A001700(n), i.e., A001700(n) gives the total number of leaves in all ordered trees with n + 1 edges.

Indranil Ghosh, Table of n, a(n) for n = 0..3485
Antti Karttunen, Gatomorphisms and other excursions ... (Includes Scheme program)
Antti Karttunen, Newer version of the Scheme code collection

Cf. A000108, A000120, A001700, A003188, A005811, A014137, A014486, A057515.

a(n)-1 gives the number of zeros in A071153(n) (for n>=1).

def a005811(n): return bin(n^(n>>1))[2:].count("1")
def ok(n): # This function after Peter Luschny
    B=bin(n)[2:] if n!=0 else 0
    s=0
    for b in B:
        s+=1 if b=="1" else -1
        if s<0: return 0
    return s==0
def A(n): return [0] + [i for i in range(1, n + 1) if ok(i)]
l=A(200)
print([a005811(l[i])//2 for i in range(len(l))]) # Indranil Ghosh, May 21 2017

a(n) = A005811(A014486(n))/2 = A000120(A003188(A014486(n)))/2.

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.

A074685 Permutation of natural numbers induced by the Catalan bijection gmA074685! acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 6, 7, 8, 5, 4, 15, 14, 16, 17, 18, 19, 20, 21, 11, 12, 22, 13, 10, 9, 39, 40, 41, 38, 37, 43, 42, 44, 45, 46, 47, 48, 49, 50, 52, 51, 53, 54, 55, 56, 57, 58, 29, 28, 59, 30, 31, 32, 60, 61, 62, 33, 34, 63, 35, 25, 26, 64, 36, 27, 24, 23, 113, 112, 114, 115, 116

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences that are permutations of the natural numbers

Inverse of A074686. a(n) = A057163(A074689(A057163(n))). Occurs in A073200 as row 5572436.

A080263 A014486-encoding of the branch-reduced binomial-mod-2 binary trees.

Original entry on oeis.org

2, 50, 906, 247986, 4072138, 1059204274, 272900475786, 17953590946285746, 287705670922216138, 73724537815637830834, 18880972926031430339466, 1237678872789190922262530226, 316876593058175709191975346890

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

These trees are obtained from the successive generations of Rule 90 cellular automaton (A070886) or Pascal's triangle computed modulo 2 (A047999), with alive cells of the automaton (respectively: the odd binomials) forming the vertices of the zigzag tree.

J. C. P. Miller, Periodic Forests of Stunted Trees, Phil. Tran. Roy. Soc. London A266 (1970) 63; A293 (1980) 48.

A. Karttunen, Initial terms illustrated

Same sequence in binary: A080264. Cf. A080265. Breadth-first-wise encodings of the same trees: A080268. Corresponding branch-reduced zigzag trees: A080293.

Number of edges in general trees/internal nodes in binary trees: A006046, number of zigzag-edges (those colored black in illustrations) is one less: A074330. Cf. A080978.

A085201 Array A(x,y): Position of the concatenation of binary strings A014486(x) & A014486(y) in A014486, listed antidiagonalwise as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ...

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 9, 5, 4, 5, 9, 14, 10, 9, 5, 6, 11, 23, 15, 23, 10, 6, 7, 14, 28, 24, 37, 24, 11, 7, 8, 16, 37, 29, 65, 38, 25, 12, 8, 9, 19, 42, 38, 79, 66, 39, 26, 13, 9, 10, 23, 51, 43, 107, 80, 67, 40, 27, 23, 10, 11, 25, 65, 52, 121, 108, 81, 68, 41, 65, 24, 11

Offset: 0

Antti Karttunen, Jun 23 2003

This table is induced by the 2-ary form of the list-function 'append' present in the programming languages like Lisp, Scheme and Prolog.

Index entries for the sequences induced by list functions of Lisp

Transpose: A085202. Variant: A085203. Row 1: A085223, Column 1: A072795.

Cf. also A014486, A080300, A025581, A002262.

a(0, y)=y, a(x, y) = A072764bi(A072771(x), a(A072772(x), y))

a(x, y) = A080300(A085207bi(A014486(x), A014486(y))) = A085200(A085215bi(A071155(y), A071155(x)))

A085203 Array A(x,y): Position of the totally balanced binary string obtained by concatenating the binary strings A014486(x) & A014486(y) in such a way that the latter is inserted after the least significant 1-bit of the former, followed by the remaining 0-bits, if any. Listed antidiagonalwise as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ...

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 5, 7, 3, 4, 8, 12, 8, 4, 5, 10, 21, 13, 17, 5, 6, 13, 26, 22, 31, 18, 6, 7, 15, 35, 27, 58, 32, 20, 7, 8, 18, 40, 36, 73, 59, 34, 21, 8, 9, 22, 49, 41, 100, 74, 62, 35, 22, 9, 10, 24, 63, 50, 115, 101, 76, 63, 36, 45, 10, 11, 27, 68, 64, 142, 116, 104, 77, 64, 87, 46

Offset: 0

Antti Karttunen, Jun 23 2003

This table is induced by the list-function 'app-to-xrt' whose Scheme-definition is given below, in the same way as A085201 is induced by the ordinary 'append'-function.

Transpose: A085204. Variant: A085201. Row 1: A085225, Column 1: A057548.

Cf. also A014486, A080300, A025581, A002262.

a(0, y) = y, a(x, y) = A057548(a(A072771(x), y)) if A072772(x)=0, otherwise A072764bi(A072771(x), a(A072772(x), y)).

a(x, y) = A080300(A085211bi(A014486(x), A014486(y))) = A085200(A085219bi(A071155(y), A071155(x))).

cp's OEIS Frontend

A089855 Permutation of natural numbers induced by Catalan Automorphism *A089855 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A089857 Permutation of natural numbers induced by Catalan Automorphism *A089857 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057514 Number of peaks in mountain ranges encoded by A014486, number of leaves in the corresponding rooted plane trees (the root node is never counted as a leaf).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A074685 Permutation of natural numbers induced by the Catalan bijection gmA074685! acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

A080263 A014486-encoding of the branch-reduced binomial-mod-2 binary trees.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A085201 Array A(x,y): Position of the concatenation of binary strings A014486(x) & A014486(y) in A014486, listed antidiagonalwise as A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ...

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Views

Author

Keywords