A061667 a(n) = Fibonacci(2*n+1) - 2^(n-1).

1, 3, 9, 26, 73, 201, 546, 1469, 3925, 10434, 27633, 72977, 192322, 506037, 1329885, 3491810, 9161929, 24026745, 62983842, 165055853, 432445861, 1132806018, 2967020769, 7770353441, 20348233858, 53282736741, 139516753581, 365301078434, 956453590585

Offset: 1

Author

Emeric Deutsch, Jun 16 2001

Keywords

• nonn
• easy

Comments

Number of cells in the bottom row of all directed column-convex polyominoes of area n+1.

Also the binomial transform of A000071 (after removing its 2 leading zeros). - R. J. Mathar, Nov 04 2008

Equals row sums of triangle A147293. - Gary W. Adamson, Nov 05 2008

Links

• Harry J. Smith, Table of n, a(n) for n = 1..200
• 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.
• Alexander Burstein and Toufik Mansour, Words restricted by 3-letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
• Alexander Burstein and Toufik Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14; see Th. 3.8.
• Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 22.
• Index entries for linear recurrences with constant coefficients, signature (5,-7,2).

Crossrefs

Cf. A000045.

Cf. A147293. - Gary W. Adamson, Nov 05 2008

Programs

Mathematica

Table[Fibonacci[2 n + 1] - 2^(n - 1), {n, 1, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)

PARI

a(n) = { fibonacci(2*n + 1) - 2^(n - 1) } \\ Harry J. Smith, Jul 26 2009

PARI

Vec(x*(1-x)^2/((1-2*x)*(1-3*x+x^2)) + O(x^50)) \\ Michel Marcus, Nov 29 2014

Formula

G.f.: x*(1-x)^2/((1-2*x)*(1-3*x+x^2)). - corrected by Philip B. Zhang, Nov 28 2014

a(n) = Sum_{k=0..n+1} C(n+1, k)*sum{j=0..floor(k/2), Fibonacci(k-2j)}. - Paul Barry, Apr 17 2005

a(n) = 2*A001906(n+1)-A001906(n)-A000079(n). - R. J. Mathar, Nov 16 2007

From Colin Barker, Jun 05 2017: (Start)

a(n) = 2^(-1-n)*(-5*4^n - (3-sqrt(5))^n*(-5+sqrt(5)) + (3+sqrt(5))^n*(5+sqrt(5))) / 5.

a(n) = 5*a(n-1) - 7*a(n-2) + 2*a(n-3) for n>3. (End)

Extensions

Offset changed from 0 to 1 by Harry J. Smith, Jul 26 2009