A073431 -id:A073431 - cp's OEIS frontend

A069768 Signature-permutation of Catalan bijection "Knack".

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

Offset: 0

Antti Karttunen, Apr 16 2002; entry revised Dec 20 2008

nonn

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".

A. Karttunen, paper in preparation.

Inverse permutation: "Knick", A069767. "n-th powers" (i.e. n-fold applications), from n=2 to 6: A073291, A073293, A073295, A073297, A073299.
In range [A014137(n-1)..A014138(n-1)] of this permutation, the number of cycles is A073431, number of fixed points: A036987 (Fixed points themselves: A084108), Max. cycle size & LCM of all cycle sizes: A011782. See also: A074080.
A127302(a(n)) = A127302(n) for all n. a(n) = A057162(A057508(n)) = A069769(A057162(n))
Row 1 of A122204 and A122288, row 21 of A122285 and A130402, row 8 of A073200.
See also bijections A073287, A082346, A082347, A082350, A130342.

A069767 Signature-permutation of Catalan bijection "Knick".

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 6, 5, 4, 17, 18, 20, 21, 22, 16, 19, 15, 12, 13, 14, 11, 10, 9, 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, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Apr 16 2002; entry revised Dec 20 2008

nonn

This automorphism of binary trees first swaps the left and right subtree of the root and then proceeds recursively to the (new) right 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 A153141. See further comments there.
This bijection, Knick, is a SPINE-transformation of the simple swap: SPINE(*A069770) (i.e., row 1 of A122203). Furthermore, Knick and Knack (the inverse, *A069768) 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 a row 1 in A122287 and naturally, the double-fork fixes both, e.g., FORK(FORK(Knick)) = Knick. There are also other peculiar properties.
Note: the name in Finnish is "Niks".

A. Karttunen, paper in preparation.

Inverse permutation: "Knack", A069768. "n-th powers" (i.e. n-fold applications), from n=2 to 6: A073290, A073292, A073294, A073296, A073298.
In range [A014137(n-1)..A014138(n-1)] of this permutation, the number of cycles is A073431, number of fixed points: A036987 (Fixed points themselves: A084108), Max. cycle size & LCM of all cycle sizes: A011782. See also: A074080.
A127302(a(n)) = A127302(n) for all n. a(n) = A057508(A057161(n)) = A057161(A069769(n)).
Row 1 of A122203 and A122287, row 15 of A122286 and A130403, row 6 of A073200.
See also bijections A073286, A082345, A082348, A082349, A130341.

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

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

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

A073346 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and "contracted height" k.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 1, 0, 8, 8, 0, 0, 0, 0, 0, 0, 12, 16, 0, 0, 0, 0, 0, 0, 2, 12, 40, 16, 0, 0, 0, 0, 0, 0, 2, 12, 80, 48, 0, 0, 0, 0, 0, 0, 0, 0, 12, 136, 144, 32, 0, 0, 0, 0, 0, 0, 0, 2, 20, 224, 384, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16

Offset: 0

Antti Karttunen, Jul 31 2002

The height of binary trees is computed here in the same way as in A073345, except that whenever a complete binary tree of (2^k)-1 nodes with all its leaves at the same level, i.e., one of the following trees:
__________________\/\/\/\/_
___________\/\/\/\/
______________\/____\ /__
____.__\/__\/____\/__ etc.
is encountered as a terminating subtree, it is regarded just a variant of . (an empty tree, a single leaf) and contributes nothing to the height of the tree.

			The top-left corner of this square array:
1 1 0 1 0 0 0 1 ...
0 0 2 0 2 2 0 0 ...
0 0 0 4 4 8 12 12 ...
0 0 0 0 8 16 40 80 ...

H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.

Variant: A073345. The first row: A036987. Column sums: A000108. Diagonals: T(n, n) = A000007(n), T(n+1, n) = A000079(n), T(n+2, n) = A058922(n), T(n+3, n) = A074092(n) - [see the attached notes.].

A073430 gives the upper triangular region of this array. Used to compute A073431. Entries on row k are all divisible by 2^k, thus dividing them out yields the array/triangle A074079/A074080.

A073346 := n -> A073346bi(A025581(n), A002262(n));
A073346bi := proc(n,k) option remember; local i,j; if(0 = k) then RETURN(A036987(n)); fi; if(0 = n) then RETURN(0); fi; 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073346bi(floor((n-1)/2),k-1)^2) - (`if`((1=k),1,0))*A036987(n); end;
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

(See the Maple code below. Note that here we use the same convolution recurrence as with A073345, but only the initial conditions for the first two rows (k=0 and k=1) are different. Is there a nicer formula?)

Sequence number in comments corrected

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

A074079 Square array A(row,col) (listed in order A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), A(0,3), etc.), giving essentially the same information as the triangle A074080 which shows only the upper triangular region.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0, 1, 3, 5, 1, 0, 0, 0, 0, 0, 0, 1, 3, 10, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 17, 9, 1, 0, 0, 0, 0, 0, 0, 0, 1, 5, 28, 24, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 41, 57, 14, 1, 0, 0, 0

Offset: 0

Antti Karttunen, Aug 19 2002

Obtained from the square array A073346 by dividing the entries on the k-th row by 2^k. Column sums: A073431. See A074080 for explanation. Cf. also A025581, A002262.

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

A074079(n, k) = A073346(n, k)/(2^k)

cp's OEIS Frontend

A069768 Signature-permutation of Catalan bijection "Knack".

Views

Author

Keywords

Comments

References

Links

Crossrefs

A069767 Signature-permutation of Catalan bijection "Knick".

Views

Author

Keywords

Comments

References

Links

Crossrefs

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A073346 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and "contracted height" k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

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

A074079 Square array A(row,col) (listed in order A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), A(0,3), etc.), giving essentially the same information as the triangle A074080 which shows only the upper triangular region.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula