cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 16 results. Next

A057163 Signature-permutation of a Catalan automorphism: Reflect a rooted plane binary tree; Deutsch's 1998 involution on Dyck paths.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Aug 18 2000

Keywords

Comments

Deutsch shows in his 1999 paper that this automorphism maps the number of doublerises of Dyck paths to number of valleys and height of the first peak to the number of returns, i.e., that A126306(n) = A127284(a(n)) and A126307(n) = A057515(a(n)) hold for all n.
The A000108(n-2) n-gon triangularizations can be reflected over n axes of symmetry, which all can be generated by appropriate compositions of the permutations A057161/A057162 and A057163.
Composition with A057164 gives signature permutation for Donaghey's Map M (A057505/A057506). Embeds into itself in scale n:2n+1 as a(n) = A083928(a(A080298(n))). A127302(a(n)) = A127302(n) and A057123(A057163(n)) = A057164(A057123(n)) hold for all n.

Examples

			This involution (self-inverse permutation) of natural numbers is induced when we reflect the rooted plane binary trees encoded by A014486. E.g., we have A014486(5) = 44 (101100 in binary), A014486(7) = 52 (110100 in binary) and these encode the following rooted plane binary trees, which are reflections of each other:
    0   0             0   0
     \ /               \ /
      1   0         0   1
       \ /           \ /
    0   1             1   0
     \ /               \ /
      1                 1
thus a(5)=7 and a(7)=5.

Links

Crossrefs

This automorphism conjugates between the car/cdr-flipped variants of other automorphisms, e.g., A057162(n) = a(A057161(a(n))), A069768(n) = a(A069767(a(n))), A069769(n) = a(A057508(a(n))), A069773(n) = a(A057501(a(n))), A069774(n) = a(A057502(a(n))), A069775(n) = a(A057509(a(n))), A069776(n) = a(A057510(a(n))), A069787(n) = a(A057164(a(n))).
Row 1 of tables A122201 and A122202, that is, obtained with FORK (and KROF) transformation from even simpler automorphism *A069770. Cf. A122351.

Programs

  • Maple
    a(n) = A080300(ReflectBinTree(A014486(n)))
ReflectBinTree := n -> ReflectBinTree2(n)/2; ReflectBinTree2 := n -> (`if`((0 = n),n,ReflectBinTreeAux(A030101(n))));
ReflectBinTreeAux := proc(n) local a,b; a := ReflectBinTree2(BinTreeLeftBranch(n)); b := ReflectBinTree2(BinTreeRightBranch(n)); RETURN((2^(A070939(b)+A070939(a))) + (b * (2^(A070939(a)))) + a); end;
NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end;
BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+A070939(BinTreeLeftBranch(n))))));
  • Mathematica
    A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; tree[n_] := Block[{func, num = Append[IntegerDigits[n, 2], 0]}, func := If[num[[1]] == 0, num = Drop[num, 1]; 0, num = Drop[num, 1]; 1[func, func]]; func]; A057163L[n_] := Function[x, FirstPosition[x, FromDigits[Most@Cases[tree[#] /. 1 -> Reverse@*1, 0 | 1, All, Heads -> True], 2]][[1]] - 1 & /@ x][Select[Range[0, 2^n], A014486Q]]; A057163L[11] (* JungHwan Min, Dec 11 2016 *)

Formula

a(n) = A083927(A057164(A057123(n))).

Extensions

Equivalence with Deutsch's 1998 involution realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 16 2002

Keywords

Comments

This is the simplest possible Catalan automorphism after the identity bijection (A001477). It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those vectices):
A B B A
\ / --> \ /
x x
(a . b) -----> (b . a)
Applying this permutation recursively to the right hand side branch of the binary trees produces permutations A069767 and A069768 (that occur at the same index 1 in tables A122203 and A122204), and applying this recursively to the both branches of binary trees (as in pre- or postorder traversal) produces A057163 (which occurs at the same index 1 in tables A122201 and A122202) that reflects the whole binary tree.
For this permutation, A127302(a(n)) = A127302(n) for all n, [or equally, A153835(a(n)) = A153835(n)], and likewise for all such recursive derivations as mentioned above.

Examples

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping their left and right hand subtrees are:
.
                        \/     \/                     \/     \/
     \/         \/     \/       \/       \/ \/       \/       \/
      \/       \/       \/       \/       \_/       \/       \/
a(n)=  3        2        7        8        6        4        5
thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.

Links

Crossrefs

Row 1 of A089840.
The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331.
Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126.
Cf. also A127302, A153835.

Formula

a(n) = A154125(A154126(n)) = A154126(A154125(n)).
a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).

Extensions

Entry revised by Antti Karttunen, Oct 11 2006 and Mar 30 2024

A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 11 2002

Keywords

Comments

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.)
...B...C.......A...B
....\./.........\./
.A...x....-->....x...C.................A..().........()..A..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> ((a . b) . c) ____ (a . ()) --> (() . a)
That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.

Links

Crossrefs

This automorphism has several variants, where the first clause is same (rotate binary tree to the left, if possible), but something else is done (than just swapping sides), in case the right hand side is empty: A082335, A082349, A123499, A123695. The following automorphisms can be derived recursively from this one: A057502, A074681, A074683, A074685, A074687, A074690, A089865, A120706, A122321, A122332. See also somewhat similar ones: A069773, A071660, A071656, A071658, A072091, A072095, A072093.
Inverse: A074680.
Row 12 of A089840.
Occurs also in A073200 as row 557243 because a(n) = A073283(A073280(A072796(n))). a(n) = A083927(A123498(A057123(n))).
Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n)] of this permutation).

Extensions

Description clarified Oct 10 2006

A074680 Signature permutation of the seventeenth nonrecursive Catalan automorphism in table A089840. (Rotate binary tree right if possible, otherwise swap its sides.)

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 11 2002

Keywords

Comments

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..-->.....A...x................()..B.......B..()
...\./............\./..................\./...-->...\./.
....x..............x....................x...........x..
((a . b) . c) -> (a . (b . c)) __ (() . b) --> (b . ())
That is, we rotate the binary tree right, in case it is possible and otherwise (if the left hand side of a tree is a terminal node) swap the right and left subtree (so that the terminal node ends to the right hand side), i.e. apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
See also the comments at A074679.

References

  • A. Karttunen, paper in preparation, draft available by e-mail.

Links

Crossrefs

This automorphism has several variants, where the first clause is same (rotate binary tree to the right, if possible), but something else is done (than just swapping sides), in case the left hand side is empty: A082336, A082350, A123500, A123696. The following automorphisms can be derived recursively from this one: A057501, A074682, A074684, A074686, A074688, A074689, A089866, A120705, A122322, A122331. See also somewhat similar ones: A069774, A071659, A071655, A071657, A072090, A072094, A072092.
Inverse: A074679. Row 17 of A089840. Occurs also in A073200 as row 2156396687 as a(n) = A072796(A073280(A073282(n))). a(n) = A083927(A123497(A057123(n))).
Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n-1)] of this permutation).

Extensions

Description clarified Oct 10 2006

A083929 Inverse function of N -> N injection A083930.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 0

Views

Author

Antti Karttunen, May 13 2003

Keywords

Comments

a(0)=0 because A083930(0)=0, but a(n) = 0 also for those n which do not occur as values of A083930. All positive natural numbers occur here once.
It appears that A071661(n) = A083929(A071663(A083930(n))) and A071662 = A083929(A071664(A083930(n))).

Crossrefs

a(A080930(n)) = n for all n. Cf. A083925-A083928, A083935.

Formula

a(n) = A083927(A083925(n)).

A123497 Signature permutation of a nonrecursive Catalan automorphism: row 1655089 of table A089840.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Oct 11 2006

Keywords

Links

Crossrefs

Inverse: A123498. Row 1655089 of A089840. Used to construct automorphism *A123501. A074680(n) = A083927(a(A057123(n))).

A123498 Signature permutation of a nonrecursive Catalan automorphism: row 1654249 of table A089840.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Oct 11 2006

Keywords

Links

Crossrefs

Inverse: A123497. Row 1654249 of A089840. Used to construct automorphism *A123502. A074679(n) = A083927(a(A057123(n))).

A083928 Inverse function of N -> N injection A080298.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 0

Views

Author

Antti Karttunen, May 13 2003

Keywords

Comments

a(1)=0 because A080298(0)=1, but a(n) = 0 also for those n which do not occur as values of A080298. All positive natural numbers occur here once.
For example, A057163 = A083928(A057163(A080298(n))), i.e. Catalan bijection A057163 embeds into itself in scale n:2n+1 using the obvious zigzag-tree -> binary tree embedding.

Links

Crossrefs

a(A080298(n)) = n for all n. Cf. A083925-A083927, A083929, A083935.

A123501 Signature permutation of a Catalan automorphism: apply *A123497 at the root, then recurse into the left subtree of the right hand side subtree of a binary tree.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Oct 11 2006

Keywords

Links

Crossrefs

Inverse: A123502. A057501(n) = A083927(a(A057123(n))) = A083927(A085159(A057123(n))).

A130919 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057511.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 11 2007

Keywords

Comments

*A130919 = DEEPEN(*A057511) = NEPEED(*A057511) = DEEPEN(DEEPEN(*A057509)) = NEPEED(NEPEED(*A057509)). See A122283, A122284 for the definitions of DEEPEN and NEPEED transforms.

Links

Crossrefs

Inverse: A130920. A122351(n) = A083927(A130919(A057123(n))). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A130967 and A130968. Maximum cycle sizes seems to be given by A000793 (shifted once right).
Showing 1-10 of 16 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.