A089848 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089851/A089853.

1, 1, 2, 2, 5, 15, 42, 132, 431, 1430, 4862, 16801, 58786, 208012, 742914, 2674440, 9694845, 35357712, 129644790, 477638700, 1767263322, 6564120420, 24466267020, 91482564069, 343059613650, 1289904147324, 4861946402882, 18367353072152

Offset: 0

Author

Antti Karttunen, Nov 29 2003

Keywords

• nonn
• easy

Comments

The number of n-node binary trees fixed by the corresponding automorphism(s).

Links

• A. Karttunen, C-program for computing the initial terms of this sequence

Programs

Maple

A089848 := n -> A000108(n-1)+`if`((2 = (n mod 3)), A000108((n-2)/3),0);

Scheme

(define (A089848 n) (cond ((zero? n) 1) (else (+ (A000108 (- n 1)) (if (= 2 (modulo n 3)) (A000108 (/ (- n 2) 3)) 0)))))

Formula

a(0)=1, a(n) = A000108(n-1) if (n mod 3)=0 or 1 and a(n) = A000108(n-1)+A000108((n-2)/3) if (n mod 3)=2.