A090826 Convolution of Catalan and Fibonacci numbers.

0, 1, 2, 5, 12, 31, 85, 248, 762, 2440, 8064, 27300, 94150, 329462, 1166512, 4170414, 15031771, 54559855, 199236416, 731434971, 2697934577, 9993489968, 37157691565, 138633745173, 518851050388, 1947388942885, 7328186394725

Offset

0,3

Comments

Also (with a(0)=1 instead of 0): Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089867/A089868, i.e., the number of n-node binary trees fixed by the corresponding automorphism(s).

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).

Tian-Xiao He and Renzo Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), no. 12, 3962-3974. [N. J. A. Sloane, Nov 26 2011]

Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.

Formula

CONV(A000045, A000108).

G.f.: (1-(1-4x)^(1/2))/(2(1-x-x^2)). The generating function for the convolution of Catalan and Fibonacci numbers is simply the generating functions of the Catalan and Fibonacci numbers multiplied together. - Molly Leonard (maleonard1(AT)stthomas.edu), Aug 04 2006

For n>1, a(n) = a(n-1) + a(n-2) + A000108(n-1). - Gerald McGarvey, Sep 19 2008

Conjecture: n*a(n) + (-5*n+6)*a(n-1) + 3*(n-2)*a(n-2) + 2*(2*n-3)*a(n-3)=0. - R. J. Mathar, Jul 09 2013

a(n) = A139375(n,1) for n > 0. - Reinhard Zumkeller, Aug 28 2013

a(n) ~ 2^(2*n + 2) / (11*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 10 2018

Mathematica

CoefficientList[Series[(1-(1-4x)^(1/2))/(2(1-x-x^2)), {x, 0, 30}], x]  (* Harvey P. Dale, Apr 05 2011 *)

Prog

(MIT Scheme) (define (A090826 n) (convolve A000045 A000108 n))
(define (convolve fun1 fun2 upto_n) (let loop ((i 0) (j upto_n)) (if (> i upto_n) 0 (+ (* (fun1 i) (fun2 j)) (loop (+ i 1) (- j 1))))))
(Haskell)
import Data.List (inits)
a090826 n = a090826_list !! n
a090826_list = map (sum . zipWith (*) a000045_list . reverse) $
                   tail $ inits a000108_list
-- Reinhard Zumkeller, Aug 28 2013

Crossrefs

Cf. Catalan numbers: A000108, Fibonacci numbers: A000045.

Sequence in context: A160999 A014329 A045633 * A132441 A000840 A362635

Adjacent sequences: A090823 A090824 A090825 * A090827 A090828 A090829

Keyword

nonn,easy

Author

Antti Karttunen, Dec 20 2003

Status

approved