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

Offset: 0

Author

Antti Karttunen Jan 03 2002

Keywords

• nonn
• tabl

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

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

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.

Programs

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;

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