A079216 - OEIS

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

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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

LINKS

Table of n, a(n) for n=0..80.

A. Karttunen, Catalan Automorphisms

Index entries for sequences related to parenthesizing

FORMULA

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

MAPLE

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;

CROSSREFS

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

Sequence in context: A168396 A049286 A308477 * A181654 A374757 A323756

Adjacent sequences: A079213 A079214 A079215 * A079217 A079218 A079219

KEYWORD

nonn,tabl

AUTHOR

Antti Karttunen Jan 03 2002

STATUS

approved