A055244 Number of certain stackings of n+1 squares on a double staircase.

1, 1, 3, 6, 12, 23, 43, 79, 143, 256, 454, 799, 1397, 2429, 4203, 7242, 12432, 21271, 36287, 61739, 104791, 177476, 299978, 506111, 852457, 1433593, 2407443, 4037454, 6762708, 11314391, 18909139, 31569799, 52657247, 87751624

Offset

0,3

Comments

a(n)= G_{n+1} of Turban reference eq.(3.9).

Equals A046854 * [1,2,3,...]. - Gary W. Adamson, Dec 23 2008

(1 + x + 3x^2 + 6x^3 + ...) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + ...) * (1 + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + ...). -Gary W. Adamson, Jul 27 2010

Column 1 of A194540. - R. H. Hardin, Aug 28 2011

References

L. Turban, Lattice animals on a staircase and Fibonacci numbers, J.Phys. A 33 (2000) 2587-2595.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

G.f.: (1-x+x^3)/(1-x-x^2)^2. (from Turban reference eq.(3.3) with t=1).

a(n) = ((n+5)*F(n+1)+(2*n-3)*F(n))/5 with F(n)=A000045(n) (Fibonacci numbers) (from Turban reference eq.(3.9)).

a(n) = A001629(n+1) + F(n-1). - Gary W. Adamson, Jul 27 2007

a(n) = (((n-4)*n-6)*a(n-2) + ((n-5)*n-11)*a(n-1)) / ((n-6)*n-1). - Jean-François Alcover, Mar 11 2014

Maple

a:= n-> (Matrix([[1, -1, 2, -4]]). Matrix(4, (i, j)-> if (i=j-1) then 1 elif j=1 then [2, 1, -2, -1][i] else 0 fi)^(n))[1, 1] ; seq (a(n), n=0..33); # Alois P. Heinz, Aug 05 2008

Mathematica

a[0] = a[1] = 1; a[n_] := a[n] = (((n-4)*n-6)*a[n-2] + ((n-5)*n-11)*a[n-1]) / ((n-6)*n-1); Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 11 2014 *)
CoefficientList[Series[(1 - x + x^3)/(1 - x - x^2)^2, {x, 0, 50}], x] (* Vincenzo Librandi, Mar 13 2014 *)
LinearRecurrence[{2, 1, -2, -1}, {1, 1, 3, 6}, 60] (* Harvey P. Dale, Jul 13 2022 *)

Crossrefs

Cf. A000045, A001629, A046854, A055245.

Sequence in context: A162506 A328609 A227681 * A089068 A018180 A079735

Adjacent sequences: A055241 A055242 A055243 * A055245 A055246 A055247

Keyword

nonn,easy

Author

Wolfdieter Lang, May 10 2000

Status

approved