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

Author

Antti Karttunen, Nov 29 2003

Keywords

• nonn
• easy

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
• Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 100.

Crossrefs

Cf. A089402.

Cf. A000108.

Programs

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

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

Scheme

(define (A089408 n) (cond ((zero? n) 1) ((even? n) (* 2 (A000108 (-1+ (/ n 2))))) (else (A000108 (/ (-1+ n) 2)))))

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

a(2*j+i) = i*C(2*j,j)/(1+j), 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