A027994 -id:A027994 - cp's OEIS frontend

A005207 a(n) = (F(2*n-1) + F(n+1))/2 where F(n) is a Fibonacci number.

1, 1, 2, 4, 9, 21, 51, 127, 322, 826, 2135, 5545, 14445, 37701, 98514, 257608, 673933, 1763581, 4615823, 12082291, 31628466, 82798926, 216761547, 567474769, 1485645049, 3889431721, 10182603746, 26658304492, 69792188337, 182718064101, 478361686155, 1252366480135

Offset: 0

N. J. A. Sloane

Number of block fountains with exactly n coins in the base when mirror image fountains are identified. - Michael Woltermann (mwoltermann(AT)washjeff.edu), Oct 06 2010
a(n) = C(F(n+1)+1,2) + C(F(n)+1,2) = pairwise sums of A033192. - Ralf Stephan, Jul 06 2003
Number of (3412,54312)- and (3412,45321)-avoiding involutions in S_{n+1}. - Ralf Stephan, Jul 06 2003
Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 1. - Herbert Kociemba, May 31 2004
The sequence 1,1,2,4,9,... has g.f. 1/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x))))=(1-3*x+x^2+x^2)/(1-4*x+3*x^2+2*x^3-x^4), and general term (A001519(n)+A000045(n+1))/2. It is the binomial transform of A001519 aerated. - Paul Barry, Dec 17 2009
The Kn3 and Kn4 sums, see A180662 for their definitions, of Losanitsch's triangle A034851 lead to this sequence. - Johannes W. Meijer, Jul 14 2011
Convolution of [1,1,1,2,5,...], which is A001519 with another leading 1, and A212804. - R. J. Mathar, Apr 14 2018
a(n) is the number of Motzkin n-paths of height <= 3. - Alois P. Heinz, Nov 24 2023

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 1..300 from Vincenzo Librandi)
E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, sec. 8, arXiv:math/0307050 [math.CO], 2003.
S. Felsner, D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
M. D. McIlroy, The number of states of a dynamic storage system, Computer J., 25 (No. 3, 1982), 388-392.
M. D. McIlroy, The number of states of a dynamic storage system, Computer J., 25 (No. 3, 1982), 388-392. (Annotated scanned copy)
Heinrich Niederhausen, Inverses of Motzkin and Schroeder Paths, arXiv preprint arXiv:1105.3713 [math.CO], 2011.
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
Michael Woltermann, Problem 1826, Mathematics Magazine, 83 (2010), 304-305.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Cf. A000045, A001006, A001519, A131719.

A005207:=-(1-2*z-z^2+z^3)/(z^2-3*z+1)/(z^2+z-1); # Simon Plouffe in his 1992 dissertation with offset 0
a:= n-> (Matrix([[1,1,1,3]]). Matrix(4, (i,j)-> if i=j-1 then 1 elif j=1 then [4,-3,-2,1][i] else 0 fi)^n)[1,2]: seq(a(n), n=0..34); # Alois P. Heinz, Sep 06 2008

LinearRecurrence[{4, -3, -2, 1}, {1, 2, 4, 9}, 30] (* Jean-François Alcover, Jan 31 2016 *)

a(n)=(fibonacci(2*n-1)+fibonacci(n+1))/2

x='x+O('x^50); Vec(-x*(1-2*x-x^2+x^3)/((x^2+x-1)*(x^2-3*x+1))) \\ G. C. Greubel, Mar 05 2017

G.f.: 1-x*(1-2*x-x^2+x^3)/((x^2+x-1)*(x^2-3*x+1)).
a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4).
a(n) = (w^(2*n-1) + w^(1-2*n) + w^(n+1) - (-w)^(-1-n))/(4*w-2) where w = (1+sqrt(5))/2.
a(n) = (2/5)*Sum_{k=1..4} ( sin(Pi*k/5)^2*(1 + 2*cos(Pi*k/5))^n ). - Herbert Kociemba, May 31 2004
a(-1-2*n) = A027994(2*n); a(-2*n)=A059512(2*n+1).
Let M = an infinite tridiagonal matrix with all 1's in the super and main diagonals and [1,1,1,0,0,0,...] in the subdiagonal. Let V = vector [1,0,0,0,...]. The sequence is generated as leftmost column of M*V iterates. - Gary W. Adamson, Jun 07 2011
2*a(n) = A000045(n+1) + A001519(n). - R. J. Mathar, Apr 14 2018
a(n) mod 2 = A131719(n+3). - Alois P. Heinz, Nov 24 2023

a(0)=1 prepended by Alois P. Heinz, Nov 24 2023

A059502 a(n) = (3nF(2n-1) + (3-n)*F(2n))/5 where F() = Fibonacci numbers A000045.

Original entry on oeis.org

0, 1, 3, 9, 27, 80, 234, 677, 1941, 5523, 15615, 43906, 122868, 342409, 950727, 2631165, 7260579, 19982612, 54865566, 150316973, 411015705, 1121818311, 3056773383, 8316416134, 22593883752, 61301547025, 166118284299, 449639574897, 1215751720491, 3283883157848

Offset: 0

Floor van Lamoen, Jan 19 2001

Substituting x(1-x)/(1-2x) into x/(1-x)^2 yields g.f. of sequence.

Variation of A059216 (and of Boustrophedon transform) applied to 1,2,3,4,...: fill an array by diagonals, each time in the same direction, say the 'up' direction. The first column is 1,2,3,4,... For the next element of a diagonal, add to the previous element the elements of the row the new element is in. The first row gives a(n).

			The array (see A059503) begins
  1 3  9 27 80 ...
  2 5 14 40 ...
  3 7 19 ...
  4 9  5 ...

Harry J. Smith, Table of n, a(n) for n = 0..200
Sergi Elizalde, Rigoberto Flórez, and José Luis Ramírez, Enumerating symmetric peaks in non-decreasing Dyck paths, Ars Mathematica Contemporanea (2021).
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. 17, 19.
Index entries for two-way infinite sequences
Index entries for sequences related to boustrophedon transform
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A000045, A000667, A059216, A059219, A027994, A059512, A059503.

[(3*n*Fibonacci(2*n-1)+(3-n)*Fibonacci(2*n))/5: n in [0..100]]; // Vincenzo Librandi, Apr 23 2011

Table[(3n Fibonacci[2n-1]+(3-n)Fibonacci[2n])/5,{n,0,30}] (* or *) CoefficientList[Series[x(1-x)(1-2x)/(1-3x+x^2)^2,{x,0,30}],x] (* Harvey P. Dale, Apr 23 2011 *)

a(n)=(3*n*fibonacci(2*n-1)+(3-n)*fibonacci(2*n))/5

a(n) = 2*a(n-1) + Sum{m<=n-2} a(m) + A001519(n-2).
G.f.: x*(1 - x)*(1 - 2*x)/(1 - 3*x + x^2)^2. - Emeric Deutsch, Oct 07 2002
a(n) = A147703(n,1). - Philippe Deléham, Nov 29 2008
a(n) = A001871(n-1) - 3*A001871(n-2) + 2*A001871(n-3). - R. J. Mathar, Apr 09 2019
E.g.f.: 2*exp(3*x/2)*(5*x*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

A056014 a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.

Original entry on oeis.org

0, 0, 0, 1, 4, 13, 38, 106, 288, 771, 2046, 5401, 14212, 37324, 97904, 256621, 672336, 1760997, 4611642, 12075526, 31617520, 82781215, 216732890, 567428401, 1485570024, 3889310328, 10182407328, 26657986681, 69791674108

Offset: 0

Asher Auel, Jun 06 2000

With a(0)=0, a(1)=1, a(2)=1, a(3)=2, this recurrence produces a(n)=A000045(n) (Fibonacci numbers).

Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 4. - Herbert Kociemba, Jun 16 2004

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Éva Czabarka, Rigoberto Flórez, and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), Article 15.1.6.
Henrik Eriksson and Markus Jonsson, Level sizes of the Bulgarian solitaire game tree, Fib. Q., 35:3 (2017), 243-251.
Hideyuki Othsuka, Problem B-1345, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 1 (2024), p. 85.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Cf. A000045, A000079, A051450, A056015, A094966.

a(1-2n)=A059512(2n), a(-2n)=A027994(2n-1).

I:=[0, 0, 0, 1]; [n le 4 select I[n] else 4*Self(n-1)-3*Self(n-2)-2*Self(n-3)+Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 23 2012

Table[(Fibonacci[2n-1]-Fibonacci[n+1])/2,{n,0,40}]  (* Harvey P. Dale, Mar 24 2011 *)
LinearRecurrence[{4,-3,-2,1},{0,0, 0,1},40] (* Vincenzo Librandi, Jun 23 2012 *)

a(n)=(fibonacci(2*n-1)-fibonacci(n+1))/2

a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4), a(0)=a(1)=a(2)=0, a(3)=1.
Convolution of Fibonacci numbers F(n) with F(2n). - Benoit Cloitre, Jun 07 2004
G.f.: x^3/((1 - x - x^2)*(1 - 3*x + x^2)). - Herbert Kociemba, Jun 16 2004
Binomial transform of x^3/(1-3x^2+x^4), or (essentially) F(2n) with interpolated zeros. a(n)=sum{k=0..n, binomial(n, k)((3/2-sqrt(5)/2)^(k/2)((sqrt(5)/20+1/4)(-1)^k-sqrt(5)/20-1/4)+ (sqrt(5)/2+3/2)^(k/2)((sqrt(5)/20-1/4)(-1)^k-sqrt(5)/20+1/4))}. - Paul Barry, Jul 26 2004
Convolution of the powers of 2 (A000079) with the number of positive rational knots with 2n+1 crossings (A051450), with three leading zeros. - Graeme McRae, Jun 28 2006
a(n) = (A001519(n) - A000045(n+1))/2. - R. J. Mathar, Jun 24 2011
a(n) = Sum_{k=1..n-1} binomial(n-1, k) * A094966(k-1) (Othsuka, 2024). - Amiram Eldar, Feb 29 2024

A059512 For n>=2, the number of (s(0), s(1), ..., s(n-1)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,....,n-1, s(0) = 2, s(n-1) = 2.

Original entry on oeis.org

0, 1, 1, 3, 7, 18, 46, 119, 309, 805, 2101, 5490, 14356, 37557, 98281, 257231, 673323, 1762594, 4614226, 12079707, 31624285, 82792161, 216750601, 567457058, 1485616392, 3889385353, 10182528721, 26658183099, 69791991919

Offset: 0

Floor van Lamoen, Jan 21 2001

Substituting x(1-x)/(1-2x) into x/(1-x^2) yields g.f. of sequence.

Cf. A000667, A059216, A059219, A059502, A027994.

a(1-2n)=A005207(2n), a(-2n)=A056014(2n+1).

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

a(n)=(fibonacci(2*n-1)+fibonacci(n-2))/2

a(n) = 2a(n-1) + Sum{mA000045).
G.f.: x(1-x)(1-2x)/((1-x-x^2)(1-3x+x^2)).
a(n+1)=sum{k=0..floor(n/2), C(n,2k)*F(2k+1)}. [From Paul Barry, Oct 14 2009]

A125171 Riordan array ((1-x)/(1-3*x+x^2),x/(1-x)) read by rows.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 13, 8, 4, 1, 34, 21, 12, 5, 1, 89, 55, 33, 17, 6, 1, 233, 144, 88, 50, 23, 7, 1, 610, 377, 232, 138, 73, 30, 8, 1, 1597, 987, 609, 370, 211, 103, 38, 9, 1, 4181, 2584, 1596, 979, 581, 314, 141, 47, 10, 1, 10946, 6765, 4180, 2575, 1560, 895, 455, 188, 57, 11, 1, 28657, 17711, 10945, 6755, 4135, 2455, 1350, 643

Offset: 0

Gary W. Adamson, Nov 22 2006

Partial column sums triangle of odd-indexed Fibonacci numbers.
Left border = odd-indexed Fibonacci numbers, next-to-left border = even-indexed Fibonacci numbers. Row sums = A061667: (1, 3, 9, 26, 73, 201, ...).
Diagonal sums are A027994(n). - Philippe Deléham, Jan 14 2014

			(6,3) = 33 = 12 + 21 = (5,3) + (5,2). First few rows of the triangle are:
   1;
   2,  1;
   5,  3,  1;
  13,  8,  4,  1;
  34, 21, 12,  5,  1;
  89, 55, 33, 17,  6,  1;
  ...

Vincenzo Librandi, Table of n, a(n) for n = 0..568
Peter Bala, A note on the diagonals of a proper Riordan Array

Cf. A027994, A061667 (row sums).

C := proc (n, k) if 0 <= k and k <= n then factorial(n)/(factorial(k)*factorial(n-k)) else 0 end if;
end proc:
with(combinat):
for n from 0 to 10 do
    seq(C(n, n-k) + add(fibonacci(2*i)*C(n-i, n-k-i), i = 1..n), k = 0..n);
end do; # Peter Bala, Mar 21 2018

T(n,k)=if(k==n,1,if(k<=1,fibonacci(2*n-1),T(n-1,k)+T(n-1,k-1)));
for(n=1,15,for(k=1,n,print1(T(n,k),", "));print()); /* show triangle */
/* Joerg Arndt, Jun 17 2011 */

Let the left border = odd-indexed Fibonacci numbers, (1, 2, 5, 13, 34...); then for k>1, T(n,k) = T(n-1,k) + T(n-1,k-1).
G.f.: (1-x)^2/((1-3*x+x^2)*(1-x*(1+y))). - Paul Barry, Dec 05 2006
T(n,k) = 4*T(n-1,k) + T(n-1,k-1) - 4*T(n-2,k) - 3*T(n-2,k-1) + T(n-3,k) + T(n-3,k-1), T(0,0)=1, T(1,0)=2, T(1,1)=1, T(2,0)=5, T(2,1)=3, T(2,2)=1, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Jan 14 2014
Exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(13 + 8*x + 4*x^2/2! + x^3/3!) = 13 + 21*x + 33*x^2/2! + 50*x^3/3! + 73*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ). - Peter Bala, Dec 21 2014
T(n,k) = C(n, n-k) + Sum_{i = 1..n} Fibonacci(2*i)*C(n-i, n-k-i), where C(n,k) = n!/(k!*(n-k)!) for 0 <= k <= n, otherwise 0. - Peter Bala, Mar 21 2018

New description from Paul Barry, Dec 05 2006

Data error corrected by Johannes W. Meijer, Jun 16 2011

A105929 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having k columns of height 1 starting at level 0.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 3, 3, 0, 1, 16, 9, 4, 4, 0, 1, 43, 22, 13, 5, 5, 0, 1, 114, 58, 30, 18, 6, 6, 0, 1, 301, 151, 79, 40, 24, 7, 7, 0, 1, 792, 396, 202, 107, 52, 31, 8, 8, 0, 1, 2080, 1038, 526, 270, 143, 66, 39, 9, 9, 0, 1, 5456, 2722, 1370, 701, 358, 188, 82, 48, 10, 10, 0, 1

Offset: 0

Emeric Deutsch, Apr 26 2005

T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k peaks at height 1. Example: T(4,2)=3 because we have UDUDUUDD, UDUUDDUD and UUDDUDUD, where U=(1,1) and D=(1,-1). sum(T(n,k),k=0..n)=fibonacci(2n-1) (A001519). sum(k*T(n,k),k=0..n)=fibonacci(2n-1) (A001519). T(n,0)=A027994(n-2) for n>=2.

			Triangle begins:
  1;
  0,1;
  1,0,1;
  2,2,0,1;
  6,3,3,0,1;

Elena Barcucci, Alberto del Lungo, S. Fezzi, and Renzo Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
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.

Cf. A001519, A027994.

G:=(1-2*z)^2/(1-3*z+z^2)/(1-z-z^2-t*z+t*z^2):Gser:=simplify(series(G,z=0,14)): P[0]:=1: for n from 1 to 12 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 12 do seq(coeff(t*P[n],t^k),k=1..n+1) od;# yields sequence in triangular form

G.f.=(1-2z)^2/[(1-3z+z^2)(1-z-z^2-tz+tz^2)].

cp's OEIS Frontend

A005207 a(n) = (F(2*n-1) + F(n+1))/2 where F(n) is a Fibonacci number.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A059502 a(n) = (3*n*F(2n-1) + (3-n)*F(2n))/5 where F() = Fibonacci numbers A000045.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A056014 a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A059512 For n>=2, the number of (s(0), s(1), ..., s(n-1)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,....,n-1, s(0) = 2, s(n-1) = 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A125171 Riordan array ((1-x)/(1-3*x+x^2),x/(1-x)) read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A105929 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having k columns of height 1 starting at level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A059502 a(n) = (3nF(2n-1) + (3-n)*F(2n))/5 where F() = Fibonacci numbers A000045.