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 39 results. Next

A057502 Permutation of natural numbers: rotations of non-crossing handshakes encoded by A014486 (to opposite direction of A057501).

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 03 2000

Keywords

Comments

In A057501 and A057502, the cycles between (A014138(n-1)+1)-th and (A014138(n))-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A002995(n+1) equivalence classes of planar trees, thus the latter sequence can be produced also with Maple procedure RotHandshakesPermutationCycleCounts given below.

Links

Crossrefs

Inverse of A057501 and the car/cdr-flipped conjugate of A069774, i.e. A057502(n) = A057163(A069774(A057163(n))). Cf. also A057507, A057510, A057513, A069771, A069772.

Programs

  • Maple
    map(CatalanRankGlobal,map(RotateHandshakesR, A014486));
RotateHandshakesR := n -> pars2binexp(deepreverse(RotateHandshakesP(deepreverse(binexp2pars(n)))));
deepreverse := proc(a) if 0 = nops(a) or list <> whattype(a) then (a) else [op(deepreverse(cdr(a))), deepreverse(a[1])]; fi; end;
with(group); CountCycles := b -> (nops(convert(b,'disjcyc')) + (nops(b)-convert(map(nops,convert(b,'disjcyc')),`+`)));
RotHandshakesPermutationCycleCounts := 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,RotateHandshakes(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
# For other procedures, follow A057501.

A082315 Permutation A057501 applied twice ("squared").

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003, Proposed by Wouter Meeussen

Keywords

Links

Crossrefs

Inverse of A082316. a(n) = A082313(A057164(n)). Occurs in A073200 as row 34359740687. Cf. also A082317-A082324.
Number of cycles: A054357. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

Formula

a(n) = A057501(A057501(n)).

A082313 Involution of natural numbers: A057501-conjugate of A057164.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003. Proposed by Wouter Meeussen in Dec 15 2001

Keywords

Comments

Note: This is isomorphic with Meeussen's "skewcatacycleft" operation acting on the interpretation (gg) of the exercise 19 by Stanley.

Links

Crossrefs

a(n) = A069888(A057502(n)). Occurs in A073200 as row 604463486276865131809167. Cf. also A082314, A082315, A082333, A082334.
Number of cycles: A007123. Number of fixed-points: A001405. Max. cycle size: A046698. LCM of cycle sizes: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

Formula

a(n) = A057501(A057164(A057502(n)))

A082317 Permutation A057501 applied thrice ("cubed").

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003

Keywords

Links

Crossrefs

Inverse of A082318. Occurs in A073200 as row 11150372599265311570767859136464952601119119. Cf. also A082319-A082324.

Formula

a(n) = A057501(A082315(n))

A082321 Permutation A057501 applied five times ("^5").

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003

Keywords

Links

Crossrefs

Inverse of A082322. Occurs in A073200. Cf. also A082323-A082324.

Formula

a(n) = A082315(A082317(n))

A082319 Permutation A057501 applied four times ("^4"), permutation A082315 squared.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003

Keywords

Links

Crossrefs

Inverse of A082320. Occurs in A073200. Cf. also A082321-A082324.

Formula

a(n) = A082315(A082315(n))

A082323 Permutation A057501 applied six times ("^6"), permutation A082317 squared, permutation A082315 cubed.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Apr 17 2003

Keywords

Links

Crossrefs

Inverse of A082324. a(n) = A057501(A082321(n)). Occurs in A073200.

Formula

a(n) = A082317(A082317(n)) = A082315(A082315(A082315(n)))

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

A073200 Number of simple Catalan bijections of type B.

Original entry on oeis.org

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0
Offset: 0

Views

Author

Antti Karttunen, Jun 25 2002

Keywords

Comments

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

Links

  • A. Karttunen, Gatomorphisms (With the complete source and explanation)

Crossrefs

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 03 2000

Keywords

Comments

This is equivalent to map M given by Donaghey on page 81 of his paper "Automorphisms on ..." and also equivalent to the transformation procedure depicted in the picture (23) of Donaghey-Shapiro paper.
This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

References

  • D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

Links

Crossrefs

Inverse: A057506.
The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.
Other related permutations: A057501, A057503, A057161.
Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.
Row 17 of table A122288.
Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.

Programs

  • Maple
    map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));
DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));
DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);
DeepRotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := DeepRotateTriangularization(BinTreeRightBranch(n))*2; z := z + (2^w)*s; w := w + binwidth(s); z := z + (2^w); w := w + 1; n := floor(n/2); od; RETURN(z); end;

Formula

a(0) = 0, and for n>=1, a(n) = A085201(a(A072771(n)), A057548(a(A072772(n)))). [This recurrence reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to unary form of function 'list'].
As a composition of related permutations:
a(n) = A057164(A057163(n)).
a(n) = A057163(A057506(A057163(n))).
Showing 1-10 of 39 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.