A069768 -id:A069768 - cp's OEIS frontend

A073299 Permutation A069768 applied six times or permutation A073291 "cubed" or permutation A073293 "squared".

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A073298. Cf. A073290-A073297.

a(n) = A069768^6(n) = A073291(A073291(A073291(n))) = A073293(A073293(n))

A073287 Permutation of natural numbers induced by the composition of the Catalan bijections A069768 & A069770.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

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

Inverse permutation: A073286. Occurs for first time in A073200 as row 69. Counts of the fixed elements: A073268.

a(n) = A069768(A069770(n)).

A073431 Number of separate orbits/cycles to which the Catalan bijections A069767/A069768 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 28, 65, 160, 408, 1074, 2898, 7998, 22508, 64426, 187251, 551730, 1645840, 4964876, 15130808, 46545788, 144424944, 451715460

Offset: 0

Antti Karttunen, Jul 31 2002

nonn

Occurs for first time in A073201 as row 6 (and 8). Column sums of the square array A074079/Row sums of the triangle A074080.

A073431 := proc(n) local i; (1/2^n) * add((2^(n-i))*A073346bi(n,i),i=0..n); end;

a(0)=1, a(n) = (1/(2^(n-1))) * Sum_{i=1..(2^(n-1))} (Sum_{j=0..A007814(i)} A073346(n, j)) = (1/(2^(n-2))) * Sum_{i=1..(2^(n-1))} A073346(n, A007814(i)) - 1 = (1/2^n) * Sum_{i=0..n} (2^(n-i))*A073346(n, i) = Sum_{i=0..n} A074079(n, i)

A074080 Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 0, 3, 5, 3, 1, 1, 0, 3, 10, 9, 4, 1, 0, 1, 3, 17, 24, 14, 5, 1, 0, 1, 3, 28, 57, 44, 20, 6, 1, 0, 0, 5, 41, 128, 128, 71, 27, 7, 1, 0, 1, 4, 60, 271, 354, 234, 106, 35, 8, 1, 0, 0, 5, 81, 549, 937, 738, 384, 150, 44, 9, 1, 0, 0, 5, 106, 1061

Offset: 0

Antti Karttunen, Aug 19 2002

			If we take the fifth such sub-permutation, i.e., the subsequence A069767[23..64]: [45,46,48,49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,43,52,40,31,32,41,34,35,36,42,51,39,30,33,38,29,26,27,37,28,25,24,23], subtract 22 from each term and convert the resulting permutation of [1..42] to disjoint cycle notation, we get:
(17,31),(20,21,30,29),(3,26,12,40),(6,32,8,35,7,33,11,39),(15,22,18,34,16,25,19,38),(1,23,9,36,4,27,13,41,2,24,10,37,5,28,14,42)
which implies that T(5,0) = 0 (no fixed elements), T(5,1) = 1 (one transposition), T(5,2) = 2 (two 4-cycles), T(5,3) = 2 (two 8-cycles), T(5,4) = 1 (and one 16-cycle). It is guaranteed that only cycles whose length is a power of 2 occur in A069767/A069768.

Upper triangular region of the square array A074079 (actually, only the area above its main diagonal, excluding also the leftmost column). T(n, k) = A073430(n, k)/(2^k) [with the rightmost edge of A073430 discarded]. Row sums: A073431. A000108(n) = Sum_{i=0..n-1} 2^i * T(n, i). Cf. A073346, A003056, A002262.

A074079bi := (n,k) -> A073346bi(n,k)/(2^k);
A074080 := n -> A074079bi(A003056(n)+1, A002262(n));
A003056 := n -> floor(sqrt(2*(1+n))-(1/2));
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

A073291 Permutation A069768 applied twice ("squared").

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A073290. Occurs for first time in A073200 as row 197. Cf. A073292-A073299.

a(n) = A069768(A069768(n)).

A073293 Permutation A069768 applied three times ("cubed").

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A073292. Cf. A073290-A073299.

a(n) = A069768(A069768(A069768(n))).

A073297 Permutation A069768 applied five times or composition of the permutations A073291 & A073293.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A073296. Cf. A073290-A073299.

a(n) = A069768^5(n) = A073291(A073293(n)).

A073295 Permutation A069768 applied four times or permutation A073291 applied twice.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A073294. Cf. A073290-A073299.

a(n) = A069768(A069768(A069768(A069768(n)))) = A073291(A073291(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

Antti Karttunen, Aug 18 2000

nonn

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.

			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.

JungHwan Min, Table of n, a(n) for n = 0..10000
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
Indranil Ghosh, Python program for computing this sequence, translated from Maple code.
Antti Karttunen, C program which computes this sequence.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020.
Index entries for signature-permutations induced by Catalan automorphisms

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.

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))))));

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 *)

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

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

Antti Karttunen, Apr 16 2002

nonn

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.

			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.

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.

a(n) = A154125(A154126(n)) = A154126(A154125(n)).

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

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

cp's OEIS Frontend

A073299 Permutation A069768 applied six times or permutation A073291 "cubed" or permutation A073293 "squared".

Views

Author

Keywords

Links

Crossrefs

Formula

A073287 Permutation of natural numbers induced by the composition of the Catalan bijections A069768 & A069770.

Views

Author

Keywords

Links

Crossrefs

Formula

A073431 Number of separate orbits/cycles to which the Catalan bijections A069767/A069768 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A074080 Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A073291 Permutation A069768 applied twice ("squared").

Views

Author

Keywords

Links

Crossrefs

Formula

A073293 Permutation A069768 applied three times ("cubed").

Views

Author

Keywords

Links

Crossrefs

Formula

A073297 Permutation A069768 applied five times or composition of the permutations A073291 & A073293.

Views

Author

Keywords

Links

Crossrefs

Formula

A073295 Permutation A069768 applied four times or permutation A073291 applied twice.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs