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

Author

Wolfdieter Lang, May 10 2000

Keywords

• nonn
• easy

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
• Arnold Adelberg and Tamás Lengyel, New results on the 2-adic valuation of the central Stirling numbers S(2k, k), Harvey Mudd College (2024).
• Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Crossrefs

Cf. A000045, A001629, A046854, A055245.

Programs

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

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