| Displaying 1-6 of 6 results found.
page
1
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
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
Permutation A069768 applied four times or permutation A073291 applied twice.
+20
2
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
Number of simple Catalan bijections of type B.
+10
91
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
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)
PROG
(Scheme functions showing how to compute the row where either the recursive composition of foo (with rectype 0-4) or an ordinary composition of lhs and rhs occur in this table, where foo, lhs and rhs are also indices to this table):
(define (index-for-recursive-sgtb foo rectype) (+ 2 (* 10 foo) (* 2 rectype)))
(define (index-for-composed-sgtb lhs rhs) (let ((new-lhs (cond ((< lhs 2) lhs) ((even? lhs) (1+ (/ lhs 2))) (else (error "Only the primitive Catalan bijections A069770 (0) & A072796 (1) or one of the recursively composed Catalan bijections (even numbers >= 2) can occur at the left side of the composition. Odd number not allowed: " lhs))))) (1+ (packA054238 (* 2 new-lhs) rhs)))) (define ( A000695 n) (if (zero? n) n (+ (modulo n 2) (* 4 ( A000695 (floor->exact (/ n 2)))))))
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 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:.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".
Signature-permutation of Catalan bijection "Knack".
+10
32
0, 1, 3, 2, 8, 7, 6, 4, 5, 22, 21, 20, 17, 18, 19, 16, 14, 9, 10, 15, 11, 12, 13, 64, 63, 62, 58, 59, 61, 57, 54, 45, 46, 55, 48, 49, 50, 60, 56, 53, 44, 47, 51, 42, 37, 23, 24, 38, 25, 26, 27, 52, 43, 39, 28, 29, 40, 30, 31, 32, 41, 33, 34, 35, 36, 196, 195, 194, 189, 190
COMMENTS
This automorphism of binary trees first swaps the left and right subtree of the root and then proceeds recursively to the (new) left subtree, to do the same operation there. This is one of those Catalan bijections which extend to a unique automorphism of the infinite binary tree, which in this case is A153142. See further comments there and in A153141. This bijection, Knack, is a ENIPS-transformation of the simple swap: ENIPS(* A069770) (i.e., row 1 of A122204). Furthermore, Knack and Knick (the inverse, A069767) have a special property, that FORK and KROF transforms (explained in A122201 and A122202) transform them to their own inverses, i.e., to each other: FORK(Knick) = KROF(Knick) = Knack and FORK(Knack) = KROF(Knack) = Knick, thus this occurs also as row 1 in A122288 and naturally, the double-fork fixes both, e.g., FORK(FORK(Knack)) = Knack. Note: the name in Finnish is "Naks".
REFERENCES
A. Karttunen, paper in preparation.
PROG
(Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
(CONSTRUCTIVE VERSION:) (define (* A069768 s) (cond ((not (pair? s)) s) (else (cons (* A069768 (cdr s)) (car s)))))
Permutation A069767 applied twice ("squared").
+10
12
0, 1, 2, 3, 5, 4, 6, 8, 7, 12, 13, 11, 10, 9, 15, 14, 19, 21, 22, 16, 20, 18, 17, 31, 32, 34, 35, 36, 30, 33, 29, 26, 27, 28, 25, 24, 23, 40, 41, 39, 38, 37, 52, 51, 56, 58, 59, 60, 62, 63, 64, 43, 42, 53, 57, 61, 47, 55, 49, 50, 44, 54, 48, 46, 45, 87, 88, 90, 91, 92, 96, 97
CROSSREFS
Inverse permutation: A073291. Occurs for first time in A073200 as row 105. A073267 gives essentially (apart from the first two terms) the counts of elements fixed. Cf. A073292- A073299.
Search completed in 0.007 seconds
| 