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

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,2

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.

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

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

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

Prog

(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
(PARI) Vec((1-x)/(1-3*x+x^2)^2+O(x^30)) \\ Charles R Greathouse IV, Sep 23 2012
(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
(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
(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

Crossrefs

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

Partial sums of A030267. First differences of A001871.

Cf. A121466.

Cf. A023610.

Sequence in context: A229239 A296330 A304162 * A025568 A001047 A359919

Adjacent sequences: A001867 A001868 A001869 * A001871 A001872 A001873

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from Christian G. Bower

Status

approved