A057512 -id:A057512 - cp's OEIS frontend

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

1, 1, 2, 3, 5, 6, 10, 11, 18, 21, 34, 35, 68, 69, 137, 148, 316, 317, 759, 760, 1869, 1915, 4833, 4834, 12796, 12802, 34108, 34384, 92792, 92793, 254752, 254753, 703083, 704956, 1958210, 1958231, 5485330, 5485331, 15427026, 15440591, 43618394, 43618395, 123807695, 123807696, 352561832, 352664217, 1007481494, 1007481495, 2887387009

Offset: 0

Antti Karttunen, Sep 07 2000

nonn

Greater than A003238 because there exists also parenthesizations like ((() (())) ((()) ())) and (((()) ()) (() (()))) which are fixed by recursive deep rotation, corresponding to Catalan mountain ranges below:
...../\..../\............................./\......../\
../\/\../\/\.....and.its."dual"....../\/\../\/\
./____\/____\......................./____\/____\
It's obvious that a(p) = a(p-1)+1 for all primes p.

Index entries for sequences related to parenthesizing

The first row of A079216. The leftmost edge of the triangle A079217 and also its row sums shifted by one. Occurs for first time in A073202 as row 12. Cf. A057513, A079223-A079227, A034731, A003238.

with(numtheory,divisors); A057546 := proc(n) local d; if(0=n) then RETURN(1); else RETURN(add(A079216bi(d-1,n/d),d=divisors(n))); fi; end;

a(0)=1, a(n) = A079216(n, 1) = Sum_{d|n} A079216(d-1, n/d). - Antti Karttunen, Jan 03 2003

A079216 Square array A(n>=0,k>=1) (listed antidiagonally: A(0,1)=1, A(1,1)=1, A(0,2)=1, A(2,1)=2, A(1,2)=1, A(0,3)=1, A(3,1)=3, ...) giving the number of n-edge general plane trees fixed by k-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 5, 5, 2, 1, 1, 6, 11, 3, 2, 1, 1, 10, 26, 8, 5, 2, 1, 1, 11, 66, 18, 11, 3, 2, 1, 1, 18, 161, 43, 30, 5, 5, 2, 1, 1, 21, 420, 104, 82, 6, 14, 3, 2, 1, 1, 34, 1093, 273, 233, 15, 38, 5, 5, 2, 1, 1, 35, 2916, 702, 680, 36, 111, 6, 11, 3, 2, 1, 1, 68, 7819, 1870

Offset: 0

Antti Karttunen Jan 03 2002

Note: the counts given here are inclusive, e.g. A(n,6) includes the counts A(n,3) and A(n,2) which in turn both include A(n,1).

A. Karttunen, Catalan Automorphisms
Index entries for sequences related to parenthesizing

A(n, A003418(n)) = A000108(n). The first row: A057546, second: A079223, third: A079224, fourth: A079225, fifth: A079226, sixth: A079227. Cf. also A079217-A079222.

with(combinat, composition); # composition(n,k) gives ordered partitions of integer n into k parts.
[seq(A079216(n),n=0..119)]; A079216 := n -> A079216bi(A025581(n), A002262(n)+1);
A079216bi := proc(n,k) option remember; local r; if(0 = n) then RETURN(1); else RETURN(add(PFixedByA057511(n,k,r),r=1..n)); fi; end;
PFixedByA057511 := proc(n,k,r) option remember; local ncycles, cyclen, i, c; ncycles := igcd(r,k); cyclen := r/ncycles; if(0 <> (n mod cyclen)) then RETURN(0); else add(mul(A079216bi(i-1,ilcm(r,k)),i=c),c=composition(n/cyclen,ncycles)); fi; end;

A(0, k) = 1. A(n, k) = Sum_{r=1..n where r/gcd(r, k) divides n} Sum_{c as each composition of n/(r/gcd(r, k)) into gcd(r, k) parts} Product_{i as each composant of c} A(i-1, lcm(r, k))

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 56, 153, 451, 1357, 4212, 13308, 42898, 140276, 465324, 1561955, 5300285, 18156813, 62732842, 218405402, 765657940

Offset: 0

Antti Karttunen Sep 03 2000

It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences related to rooted trees
A. Karttunen, C-program for computing empirically the initial terms of this sequence

CountCycles given in A057502, for other procedures, follow A057511 and A057501.
Similarly generated sequences: A001683, A002995, A003239, A038775, A057507. Cf. also A000081.
Occurs for first time in A073201 as row 12. Cf. A057546 and also A000081.

A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
# Or empirically:
DeepRotatePermutationCycleCounts := 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,DeepRotateL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;

a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.] - Antti Karttunen, Jan 03 2003

A079217 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=0, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 5, 0, 0, 0, 1, 6, 2, 1, 0, 0, 1, 10, 0, 0, 0, 0, 0, 1, 11, 5, 0, 1, 0, 0, 0, 1, 18, 0, 2, 0, 0, 0, 0, 0, 1, 21, 11, 0, 0, 1, 0, 0, 0, 0, 1, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 35, 26, 3, 2, 0, 1, 0, 0, 0, 0, 0, 1, 68, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 69, 66, 0, 0, 0, 0, 1, 0, 0

Offset: 0

Antti Karttunen Jan 03 2002

Index entries for sequences related to parenthesizing

The row sums equal to the left edge shifted left once = A057546 = first row of A079216 (the latter gives the Maple procedure PFixedByA057511).

Cf. A079218, A079219, A079220, A079221, A079222 and A003056 and A002262.

[seq(A079217(n),n=0..119)]; A079217 := n -> PFixedByA057511(A003056(n)+1,1, A002262(n)+1);

A079222 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=2, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by the six-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 3, 1, 14, 14, 9, 0, 1, 38, 42, 28, 2, 0, 1, 111, 124, 90, 0, 0, 6, 1, 332, 379, 285, 5, 0, 27, 0, 1, 1029, 1178, 914, 0, 0, 110, 0, 0, 1, 3232, 3742, 2955, 14, 1, 429, 0, 0, 0, 1, 10374, 12024, 9666, 0, 0, 1614, 0, 0, 0, 0, 1, 33679, 39200, 31853, 42, 0

Offset: 0

Antti Karttunen Jan 03 2002

Note: the counts given here are inclusive, i.e. T(n,d) includes also the counts A079218(n,d) and A079219(n,d).

The row sums equal to the left edge shifted left once = A079227 = sixth row of A079216 (the latter gives the Maple procedure PFixedByA057511). Cf. also A079217-A079221 and A003056 & A002262.

[seq(A079222(n),n=0..119)]; A079222 := n -> PFixedByA057511(A003056(n)+1,6, A002262(n)+1);

A079223 Number of Catalan objects fixed by two-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 66, 161, 420, 1093, 2916, 7819, 21304, 58321, 161233, 448090, 1253252, 3521389, 9941693, 28175716, 80152141, 228747967, 654817275, 1879602446, 5408974390, 15601662378, 45098766532, 130624550412

Offset: 0

Antti Karttunen Jan 03 2002

nonn

The second row of A079216. The leftmost edge of the triangle A079218 and also its row sums shifted by one. Occurs for first time in A073202 as row 245. Cf. A057546, A079224, A079225, A079226, A079227.

Maple
```
A079223 := n -> A079216bi(n,2);
```

a(n) = A079216(n, 2)

A079227 Number of Catalan objects fixed by six-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 5, 14, 38, 111, 332, 1029, 3232, 10374, 33679, 110722, 367252, 1228558, 4138120, 14025473, 47792389, 163643066, 562722427, 1942548520, 6729230281, 23385132060, 81503084084, 284815902739, 997741303308, 3503112067273

Offset: 0

Antti Karttunen Jan 03 2002

nonn

The sixth row of A079216. The leftmost edge of the triangle A079222 and also its row sums shifted by one. Occurs in A073202 as row 170143779648513184865579715159814351615. Cf. A057546, A079223-A079226.

Maple
```
A079227 := n -> A079216bi(n,6);
```

a(n) = A079216(n, 6)

A082326 Permutation of natural numbers: A057163-conjugate of A057512.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 17 2003

nonn

Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A082325. a(n) = A069787(A082325(A069787(n))). a(n) = A082328(A082853(n))+A082852(n). Occurs in A073200 as row 1794. Cf. also A082337-A082338.
Differs from A082341 first time at n=39: a(39)=49, while A082341(39)=48.
Number of cycles: A057513. Number of fixed-points: A057546. Max. cycle size: A000793. LCM of cycle sizes: A003418. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

a(n) = A057163(A057512(A057163(n)))

A079218 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=2, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by the two-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 0, 1, 11, 14, 0, 0, 1, 26, 36, 1, 2, 0, 1, 66, 94, 0, 0, 0, 0, 1, 161, 253, 0, 5, 0, 0, 0, 1, 420, 668, 2, 0, 0, 2, 0, 0, 1, 1093, 1807, 0, 14, 1, 0, 0, 0, 0, 1, 2916, 4902, 0, 0, 0, 0, 0, 0, 0, 0, 1, 7819, 13436, 5, 36, 0, 5, 0, 2, 0, 0, 0, 1, 21304, 37016, 0, 0, 0, 0

Offset: 0

Antti Karttunen Jan 03 2002

Note: the counts given here are inclusive, i.e. T(n,d) includes also the count A079217(n,d).

The row sums equal to the left edge shifted left once = A079223 = second row of A079216 (the latter gives the Maple procedure PFixedByA057511). Cf. also A079217-A079222 and A003056 & A002262.

[seq(A079218(n),n=0..119)]; A079218 := n -> PFixedByA057511(A003056(n)+1,2, A002262(n)+1);

A079219 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=0, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by the three-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 3, 1, 3, 1, 8, 0, 9, 0, 1, 18, 2, 22, 0, 0, 1, 43, 0, 60, 0, 0, 0, 1, 104, 5, 159, 1, 0, 3, 0, 1, 273, 0, 428, 0, 0, 0, 0, 0, 1, 702, 14, 1143, 0, 1, 9, 0, 0, 0, 1, 1870, 0, 3114, 0, 0, 0, 0, 0, 0, 0, 1, 4985, 38, 8505, 2, 0, 28, 0, 0, 3, 0, 0, 1, 13562, 0, 23475, 0, 0, 0, 0

Offset: 0

Antti Karttunen Jan 03 2002

Note: the counts given here are inclusive, i.e. T(n,d) includes also the count A079217(n,d).

The row sums equal to the left edge shifted left once = A079224 = third row of A079216 (the latter gives the Maple procedure PFixedByA057511). Cf. also A079217-A079222 and A003056 and A002262.

[seq(A079219(n),n=0..119)]; A079219 := n -> PFixedByA057511(A003056(n)+1,3, A002262(n)+1);

cp's OEIS Frontend

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A079217 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=0, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A079223 Number of Catalan objects fixed by two-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A079227 Number of Catalan objects fixed by six-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A082326 Permutation of natural numbers: A057163-conjugate of A057512.

Views

Author

Keywords

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Views

Author

Keywords

Comments

Crossrefs