A133037 a(n) = A000931(n)^2.

1, 0, 0, 1, 0, 1, 1, 1, 4, 4, 9, 16, 25, 49, 81, 144, 256, 441, 784, 1369, 2401, 4225, 7396, 12996, 22801, 40000, 70225, 123201, 216225, 379456, 665856, 1168561, 2050624, 3598609, 6315169, 11082241, 19448100, 34128964, 59892121, 105103504, 184443561, 323676081

Offset: 0

Author

Omar E. Pol, Nov 02 2007

Keywords

• easy
• nonn

Comments

a(n+3) is the number of tilings of an n-board (a board with dimensions n X 1) with (1/2,1/2;2)-combs and (1/2,1/2;3)-combs. A (w,g;m)-comb is a tile composed of m pieces of dimensions w X 1 separated horizontally by gaps of width g. - Michael A. Allen, Sep 25 2024

Examples

			a(10)=9 because Padovan(10)=3 and 3^2=9.
		

Links

• Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1,1,-1).

Crossrefs

Cf. A000290, A001248, A007598. Padovan sequence: A000931.

Programs

Mathematica

a[0] = a[3] = a[5] = a[6] = 1; a[1] = a[2] = a[4] = 0; a[n_Integer] := a[n] = 2*a[n - 2] + 2*a[n - 3] - a[n - 7]; Table[a[i], {i, 0, 40}] (* Olivier Gérard, Jul 05 2011 *)
Table[RootSum[-1 - # + #^3 &, #^n (5 - 6 # + 4 #^2) &]^2/529, {n, 0,
40}] (* Eric W. Weisstein, Apr 16 2018 *)
LinearRecurrence[{1, 1, 1, -1, 1, -1}, {1, 0, 0, 1, 0, 1}, 40] (* Eric W. Weisstein, Apr 16 2018 *)

PARI

Vec(O(x^20)+(1-x-x^2-x^5)/(1-x-x^2-x^3+x^4-x^5+x^6)) \\ Charles R Greathouse IV, Jul 05 2011

Formula

a(n) = A000931(n)^2.

a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) + a(n-5) - a(n-6).

G.f.: (x^5+x^2+x-1)/(-x^6+x^5-x^4+x^3+x^2+x-1).

a(n) = a(n-2) + a(n-3) + 2*Sum_{r=8..n} ( A000930(r-8)*a(n+3-r) ) for n >= 3. - Michael A. Allen, Sep 25 2024