A001870 Expansion of (1-x)/(1 - 3*x + x^2)^2.

1, 5, 19, 65, 210, 654, 1985, 5911, 17345, 50305, 144516, 411900, 1166209, 3283145, 9197455, 25655489, 71293590, 197452746, 545222465, 1501460635, 4124739581, 11306252545, 30928921224, 84451726200, 230204999425

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

a(n) = ((n+1)*F(2*n+3)+(2*n+3)*F(2*(n+1)))/5 with F(n)=A000045(n) (Fibonacci numbers). One half of odd-indexed A001629(n), n >= 2 (Fibonacci convolution).

Convolution of F(2n+1) (A001519) and F(2n+2) (A001906(n+1)). - Graeme McRae, Jun 07 2006

Number of reentrant corners along the lower contours of all directed column-convex polyominoes of area n+3 (a reentrant corner along the lower contour is a vertical step that is followed by a horizontal step). a(n) = Sum_{k=0..ceiling((n+1)/2)} k*A121466(n+3,k). - Emeric Deutsch, Aug 02 2006

From Wolfdieter Lang, Jan 02 2012: (Start)

a(n) = A024458(2*n), n >= 1 (bisection, even arguments).

a(n) is also the odd part of the bisection of the half-convolution of the sequence A000045(n+1), n >= 0, with itself. See a comment on A201204 for the definition of the half-convolution of a sequence with itself. There one also finds the rule for the o.g.f. which in this case is Chato(x)/2 with the o.g.f. Chato(x) = 2*(1-x)/(1-3*x+x^2)^2 of A001629(2*n+3), n >= 0.

(End)

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Elena Barcucci, Renzo Pinzani, and Renzo Sprugnoli , Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
• Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
• Éva Czabarka, Rigoberto Flórez, and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
• Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerations of peaks and valleys on non-decreasing Dyck paths, Discrete Math. 341 (10) (2018), 2789-2807. See Cor. 6.
• Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.
• Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 5-6, 14-15, 17, 19.
• Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
• Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 15.
• Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• John Riordan, Notes to N. J. A. Sloane, Jul. 1968
• John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
• Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Crossrefs

a(n) = A060921(n+1, 1)/2.

Partial sums of A030267. First differences of A001871.

Cf. A121466.

Cf. A023610.

Programs

GAP

F:=Fibonacci;; List([0..30], n-> ((n+1)*F(2*n+3)+(2*n+3)*F(2*(n+1)))/5); # G. C. Greubel, Jul 15 2019

Haskell

a001870 n = a001870_list !! n
a001870_list = uncurry c $ splitAt 1 $ tail a000045_list where
   c us vs'@(v:vs) = (sum $ zipWith (*) us vs') : c (v:us) vs
-- Reinhard Zumkeller, Oct 31 2013

Magma

I:=[1, 5, 19, 65]; [n le 4 select I[n] else 6*Self(n-1) -11*Self(n-2)+6*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 10 2012

Maple

A001870:=-(-1+z)/(z**2-3*z+1)**2; # Simon Plouffe in his 1992 dissertation.

Mathematica

CoefficientList[Series[(1-x)/(1-3*x+x^2)^2,{x,0,40}],x] (* Vincenzo Librandi, Jun 10 2012 *)
LinearRecurrence[{6,-11,6,-1},{1,5,19,65},30] (* Harvey P. Dale, Aug 17 2013 *)
With[{F=Fibonacci}, Table[((n+1)*F[2*n+3]+(2*n+3)*F[2*n+2])/5, {n,0,30}]] (* G. C. Greubel, Jul 15 2019 *)

PARI

Vec((1-x)/(1-3*x+x^2)^2+O(x^30)) \\ Charles R Greathouse IV, Sep 23 2012

Sage

f=fibonacci; [((n+1)*f(2*n+3)+(2*n+3)*f(2*n+2))/5 for n in (0..30)] # G. C. Greubel, Jul 15 2019

Formula

a(n) = Sum_{k=1..n+1} k*binomial(n+k+1, 2k). - Emeric Deutsch, Jun 11 2003

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 10 2012

a(n) = (A238846(n) + A001871(n))/2. - Philippe Deléham, Mar 06 2014

a(n) = ((2*n-1)*Fibonacci(2*n) - n*Fibonacci(2*n-1))/5 [Czabarka et al.]. - N. J. A. Sloane, Sep 18 2018

E.g.f.: exp(3*x/2)*(5*(5 + 11*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(13 + 25*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

Extensions

More terms from Christian G. Bower