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

Author

Antti Karttunen, Dec 20 2003

Keywords

• nonn
• easy

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.

Crossrefs

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

Programs

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

Mathematica

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

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