A089408 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089864.

1, 1, 2, 1, 2, 2, 4, 5, 10, 14, 28, 42, 84, 132, 264, 429, 858, 1430, 2860, 4862, 9724, 16796, 33592, 58786, 117572, 208012, 416024, 742900, 1485800, 2674440, 5348880, 9694845, 19389690, 35357670, 70715340, 129644790, 259289580, 477638700

Offset

0,3

Comments

The number of n-node binary trees fixed by the corresponding automorphism(s). Essentially A000108 interleaved with A068875.

Links

Indranil Ghosh, Table of n, a(n) for n = 0..1000

Antti Karttunen, C-program for computing the initial terms of this sequence

Formula

a(0)=1, a(2n) = 2*A000108(n-1), a(2n+1) = A000108(n)

G.f.: (1+4x-(1+2x)sqrt(1-4x^2))/(2x). - Paul Barry, Apr 11 2005

C(2*j,j)/(1+j)*i, i=1..2), j >= 0. - Zerinvary Lajos, Apr 29 2007

D-finite with recurrence: (n+1)*a(n) - 2*a(n-1) + 4(3-n)*a(n-2) = 0. - R. J. Mathar, Dec 17 2011, corrected by Georg Fischer, Feb 13 2020

Maple

seq(seq(binomial(2*j, j)/(1+j)*i, i=1..2), j=0..19); # Zerinvary Lajos, Apr 29 2007

Mathematica

a[0] = 1; a[n_] := If[EvenQ[n], 2*CatalanNumber[n/2 - 1], CatalanNumber[(n-1)/2]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 24 2013 *)

Prog

(Scheme) (define (A089408 n) (cond ((zero? n) 1) ((even? n) (* 2 (A000108 (-1+ (/ n 2))))) (else (A000108 (/ (-1+ n) 2)))))
(Python)
from sympy import catalan
def a(n): return 1 if n==0 else 2*catalan(n//2 - 1) if n%2==0 else catalan((n - 1)//2) # Indranil Ghosh, May 23 2017

Crossrefs

Cf. A089402.

Cf. A000108.

Sequence in context: A225044 A325246 A193691 * A350287 A208888 A258783

Adjacent sequences: A089405 A089406 A089407 * A089409 A089410 A089411

Keyword

nonn,easy

Author

Antti Karttunen, Nov 29 2003

Status

approved