A052984 -id:A052984 - cp's OEIS frontend

A052961 Expansion of (1 - 3x) / (1 - 5x + 3*x^2).

1, 2, 7, 29, 124, 533, 2293, 9866, 42451, 182657, 785932, 3381689, 14550649, 62608178, 269388943, 1159120181, 4987434076, 21459809837, 92336746957, 397304305274, 1709511285499, 7355643511673, 31649683701868, 136181487974321, 585958388766001, 2521247479907042

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the number of tilings of a 2 X n rectangle using integer dimension tiles at least one of whose dimensions is 1, so allowable dimensions are 1 X 1, 1 X 2, 1 X 3, 1 X 4, ..., and 2 X 1. - David Callan, Aug 27 2014
a(n+1) counts closed walks on K_2 containing one loop on the index vertex and four loops on the other vertex. Equivalently the (1,1)entry of A^(n+1) where the adjacency matrix of digraph is A=(1,1;1,4). - _David Neil McGrath, Nov 05 2014
A production matrix for the sequence is M =
  1, 1, 0, 0, 0, 0, 0, ...
  1, 0, 4, 0, 0, 0, 0, ...
  1, 0, 0, 4, 0, 0, 0, ...
  1, 0, 0, 0, 4, 0, 0, ...
  1, 0, 0, 0, 0, 4, 0, ...
  1, 0, 0, 0, 0, 0, 4, ...
  ...
Take powers of M and extract the upper left term, getting the sequence starting (1, 1, 2, 7, 29, 124, ...). - Gary W. Adamson, Jul 22 2016
From Gary W. Adamson, Jul 29 2016: (Start)
The sequence is N=1 in an infinite set obtained from matrix powers of [(1,N); (1,4)], extracting the upper left terms.
The infinite set begins:
N=1  (A052961):  1,  2,  7,  29   124,  533,   2293, ...
N=2  (A052984):  1,  3, 13,  59,  269, 1227,   5597, ...
N=3  (A004253):  1,  4, 19,  91,  436, 2089,  10009, ...
N=4  (A000351):  1,  5, 25, 125,  625, 3125,  15625, ...
N=5  (A015449):  1,  6, 31, 161,  836, 4341,  22541, ...
N=6  (A124610):  1,  7, 37, 199, 1069, 5743,  30853, ...
N=7  (A111363):  1,  8, 43, 239, 1324, 7337,  40653, ...
N=8  (A123270):  1,  9, 49, 281, 1601, 9129,  52049, ...
N=9  (A188168):  1, 10, 55, 325, 1900, 11125, 65125, ...
N=10 (A092164):  1, 11, 61, 371, 2221, 13331, 79981, ...
... (End)

Karl V. Keller, Jr., Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1032
Kai Liang, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698, March 2025.
Index entries for linear recurrences with constant coefficients, signature (5,-3).

Column k=2 of A254414.

Cf. A000351, A004253, A015449, A052984, A092164, A111363, A123270, A124610, A188168.

a:=[1,2];; for n in [3..30] do a[n]:=5*a[n-1]-3*a[n-2]; od; a; # G. C. Greubel, Oct 23 2019

I:=[1,2]; [n le 2 select I[n] else 5*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 17 2014

spec:= [S,{S = Sequence(Union(Prod(Sequence(Union(Z,Z,Z)),Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size = n), n = 0..20);
seq(coeff(series((1-3*x)/(1-5*x+3*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 23 2019

CoefficientList[Series[(1-3x)/(1-5x+3x^2),{x,0,30}],x] (* or *) LinearRecurrence[{5,-3},{1,2},30] (* Harvey P. Dale, Nov 23 2013 *)

my(x='x+O('x^30)); Vec((1-3*x)/(1-5*x+3*x^2)) \\ G. C. Greubel, Oct 23 2019

def A052961_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-3*x)/(1-5*x+3*x^2)).list()
A052961_list(30) # G. C. Greubel, Oct 23 2019

G.f.: (1-3*x)/(1-5*x+3*x^2).
a(n) = 5*a(n-1) - 3*a(n-2), with a(0) = 1, a(1) = 2.
a(n) = Sum_{alpha=RootOf(1-5*z+3*z^2)} (-1 + 9*alpha)*alpha^(-1-n)/13.
E.g.f.: (1 + sqrt(13) + (sqrt(13)-1) * exp(sqrt(13)*x)) / (2*sqrt(13) * exp(((sqrt(13)-5)*x)/2)). - Vaclav Kotesovec, Feb 16 2015
a(n) = A116415(n) - 3*A116415(n-1). - R. J. Mathar, Feb 27 2019

A104934 Expansion of (1-x)/(1 - 3x - 2x^2).

Original entry on oeis.org

1, 2, 8, 28, 100, 356, 1268, 4516, 16084, 57284, 204020, 726628, 2587924, 9217028, 32826932, 116914852, 416398420, 1483024964, 5281871732, 18811665124, 66998738836, 238619546756, 849856117940, 3026807447332, 10780134577876, 38394018628292, 136742325040628, 487015012378468, 1734529687216660

Offset: 0

Creighton Dement, Mar 29 2005

A floretion-generated sequence relating A007482, A007483, A007484. Inverse is A046717. Inverse of Fibonacci(3n+1), A033887. Binomial transform is A052984. Inverse binomial transform is A006131. Note: the conjectured relation 2*a(n) = A007482(n) + A007483(n-1) is a result of the FAMP identity dia[I] + dia[J] + dia[K] = jes + fam
Floretion Algebra Multiplication Program, FAMP Code: 1dia[I]tesseq[A*B] with A = - .25'i + .25'j + .25'k - .25i' + .25j' + .25k' - .25'ii' + .25'jj' + .25'kk' + .25'ij' + .25'ik' + .25'ji' + .25'jk' + .25'ki' + .25'kj' - .25e and B = + 'i + i' + 'ji' + 'ki' + e
a(n) is also the number of ways to build a (2 x 2 x n)-tower using (2 X 1 X 1)-bricks (see Exercise 3.15 in Aigner's book). - Vania Mascioni (vmascioni(AT)bsu.edu), Mar 09 2009
a(n) is the number of compositions of n when there are 2 types of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010
Pisano period lengths: 1, 1, 4, 1, 24, 4, 48, 1, 12, 24, 30, 4, 12, 48, 24, 1,272, 12, 18, 24, ... - R. J. Mathar, Aug 10 2012

M. Aigner, A Course in Enumeration, Springer, 2007, p.103.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
Index entries for linear recurrences with constant coefficients, signature (3,2)

Cf. A006131, A007482 (partial sums), A007483, A007484, A033887, A046717, A052984, A055099, A104935, A122542.

# Following the Pari implementation.
function a(n)
   F = BigInt[0 1; 2 3]
   Fn = F^n * [1; 2]
   Fn[1, 1]
end # Peter Luschny, Jan 06 2019

m:=35; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1 - x)/(1 - 3*x - 2*x^2)); // Vincenzo Librandi, Jul 13 2018

a := proc(n) option remember; `if`(n < 2, [1, 2][n+1], (3*a(n-1) + 2*a(n-2))) end:
seq(a(n), n=0..28); # Peter Luschny, Jan 06 2019

LinearRecurrence[{3, 2}, {1, 2}, 40] (* Vincenzo Librandi, Jul 13 2018 *)
CoefficientList[Series[(1-x)/(1-3x-2x^2),{x,0,40}],x] (* Harvey P. Dale, May 02 2019 *)

a(n)=([0,1; 2,3]^n*[1;2])[1,1] \\ Charles R Greathouse IV, Jun 20 2015

[(i*sqrt(2))^(n-1)*(i*sqrt(2)*chebyshev_U(n, -3*i/(2*sqrt(2))) - chebyshev_U(n-1, -3*i/(2*sqrt(2))) ) for n in (0..40)] # G. C. Greubel, Jun 27 2021

Define A007483(-1) = 1. Then 2*a(n) = A007482(n) + A007483(n-1) (conjecture);
  a(n+2) = 4*A007484(n) (thus 8*A007484(n) = A007482(n+2) + A007483(n+1));
  a(n+1) = 2*A055099(n);
  a(n+2) - a(n+1) - a(n) = A007484(n+1) - A007484(n).
a(0)=1, a(1)=2, a(n) = 3*a(n-1) + 2*a(n-2) for n > 1. - Philippe Deléham, Sep 19 2006
a(n) = Sum_{k=0..n} 2^k*A122542(n,k). - Philippe Deléham, Oct 08 2006
a(n) = ((17+sqrt(17))/34)*((3+sqrt(17))/2)^n + ((17-sqrt(17))/34)*((3-sqrt(17))/2)^n. - Richard Choulet, Nov 19 2008
a(n) = 2*a(n-1) + 4*Sum_{k=0..n-2} a(k) for n > 0. - Vania Mascioni (vmascioni(AT)bsu.edu), Mar 09 2009
G.f.: (1-x)/(1-3*x-2*x^2). - M. F. Hasler, Jul 12 2018
a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) - ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - G. C. Greubel, Jun 27 2021
E.g.f.: exp(3*x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, May 24 2024

A005824 a(n) = 5a(n-2) - 2a(n-4), with initial terms 0,1,1,3.

Original entry on oeis.org

0, 1, 1, 3, 5, 13, 23, 59, 105, 269, 479, 1227, 2185, 5597, 9967, 25531, 45465, 116461, 207391, 531243, 946025, 2423293, 4315343, 11053979, 19684665, 50423309, 89792639, 230008587, 409593865, 1049196317, 1868384047, 4785964411, 8522732505, 21831429421, 38876894431

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

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

Michael De Vlieger, Table of n, a(n) for n = 0..3036
Milica Anđelić and Carlos M. da Fonseca, On the constant coefficients of a certain recurrence relation: A simple proof, Heliyon (2021) Vol. 7, No. 8, e07764.
Sean A. Irvine, Walks on Graphs.
D. Panario, M. Sahin and Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.
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
Jeffrey Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Comput. 10 (1990), no. 6, 593-610.
Index entries for linear recurrences with constant coefficients, signature (0,5,0,-2).

Cf. A079162.

a[0] = 0; a[1] = 1; a[n_] := a[n] = If[ EvenQ[n], a[n - 1] + 2a[n - 2], 2a[n - 1] + a[n - 2]]; Table[a[n], {n, 0, 31}]
LinearRecurrence[{0,5,0,-2},{0,1,1,3},40] (* Harvey P. Dale, Jul 09 2015 *)

Also a(n) = a(n-1) + 2a(n-2) if n is even, else a(n) = 2a(n-1) + a(n-2).
g.f.: -x*(2*x+1)*(x-1)/(1-5*x^2+2*x^4). Simon Plouffe in his 1992 dissertation.
a(2n+1) = A052984(n). [Index corrected by R. J. Mathar, Apr 01 2009]
a(2n) = A107839(n-1). [R. J. Mathar, Apr 01 2009]
a(n) = A109165(n-1)-A109165(n-2). - R. J. Mathar, Jan 13 2025

Extended by Robert G. Wilson v, Dec 29 2002

A160232 Array read by antidiagonals: row n has g.f. ((1-x)/(1-2x))^n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 9, 12, 8, 1, 5, 14, 25, 28, 16, 1, 6, 20, 44, 66, 64, 32, 1, 7, 27, 70, 129, 168, 144, 64, 1, 8, 35, 104, 225, 360, 416, 320, 128, 1, 9, 44, 147, 363, 681, 968, 1008, 704, 256, 1, 10, 54, 200, 553, 1182, 1970, 2528, 2400, 1536, 512, 1, 11, 65

Offset: 1

N. J. A. Sloane, May 15 2010

Suggested by a question from Phyllis Chinn (Humboldt State University).
As triangle, mirror image of A105306. - Philippe Deléham, Nov 01 2011
A160232 is jointly generated with A208341 as a triangular array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1; for n > 1, u(n,x) = u(n-1,x) + x*v(n-1)x and v(n,x) = u(n-1,x) + 2x*v(n-1,x).  See the Mathematica section. - Clark Kimberling, Feb 25 2012
Subtriangle of the triangle T(n,k) given by (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 08 2012

			Array begins:
  1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, ...
  1, 2, 5, 12, 28, 64, 144, 320, 704, 1536, 3328, 7168, 15360, 32768, 69632, 147456, 311296, 655360, 1376256, ...
  1, 3, 9, 25, 66, 168, 416, 1008, 2400, 5632, 13056, 29952, 68096, 153600, 344064, 765952, 1695744, 3735552, ...
  1, 4, 14, 44, 129, 360, 968, 2528, 6448, 16128, 39680, 96256, 230656, 546816, 1284096, 2990080, 6909952, ...
  1, 5, 20, 70, 225, 681, 1970, 5500, 14920, 39520, 102592, 261760, 657920, 1632000, 4001280, 9708544, ...
  1, 6, 27, 104, 363, 1182, 3653, 10836, 31092, 86784, 236640, 632448, 1661056, 4296192, 10961664, 27630592, ...
From _Clark Kimberling_, Feb 25 2012: (Start)
As a triangle (see Comments):
  1;
  1,  1;
  1,  2,  2;
  1,  3,  5,  4;
  1,  4,  9, 12,  8;  (End)
From _Philippe Deléham_, Mar 08 2012: (Start)
(1, 0, 0, 0, 0, ...) DELTA (0, 1, 1, 0, 0, 0, ...) begins:
  1;
  1,  0;
  1,  1,  0;
  1,  2,  2,  0;
  1,  3,  5,  4,  0;
  1,  4,  9, 12,  8,  0;
  1,  5, 14, 25, 28, 16,  0; (End)

Rows give A011782, A045623, A058396, A062109, A169792-A169797.

Cf. A062110, A105306, A208341.

u[1, x_] := 1; v[1, x_] := 1; z = 13;
u[n_, x_] := u[n - 1, x] + x*v[n - 1, x];
v[n_, x_] := u[n - 1, x] + 2*x*v[n - 1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]  (* A160232 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]  (* A208341 *)
(* Clark Kimberling, Feb 25 2012 *)

From Philippe Deléham, Mar 08 2012: (Start)
As DELTA-triangle T(n,k) with 0 <= k <= n:
T(n,k) = T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k-1), T(0,0) = 1, T(1,0) = 1, T(1,1) = 0, T(n,k) = 0 if k < 0 or if k > n.
G.f.: (1-2*y*x)/(1-2*y*x-x+y*x^2).
Sum_{k=0..n, n>0} T(n,k)*x^k = A000012(n), A001519(n), A052984(n-1) for x = 0, 1, 2 respectively. (End)

A082761 Trinomial transform of the Fibonacci numbers (A000045).

Original entry on oeis.org

1, 4, 20, 104, 544, 2848, 14912, 78080, 408832, 2140672, 11208704, 58689536, 307302400, 1609056256, 8425127936, 44114542592, 230986743808, 1209462292480, 6332826779648, 33159111507968, 173623361929216, 909103725543424, 4760128905543680, 24924358531088384, 130505635564355584

Offset: 0

Emanuele Munarini, May 21 2003

Hankel transform of Sum_{k=0..n} (-1)^k*C(2k, k) (see A054108). - Paul Barry, Jan 13 2009
Hankel transform of A046748. - Paul Barry, Apr 14 2010
For positive n, a(n) equals the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(2)'s along the three central diagonals. - John M. Campbell, Jul 12 2011
The limiting ratio is: Lim_{n -> oo} a(n)/a(n-1) = 1 + phi^3. - Bob Selcoe, Mar 18 2014
Invert transform of A052984. Invert transform is A083066. Binomial transform of A033887. Binomial transform is A163073. - Michael Somos, May 26 2014

			a(5) = 2848 = 5*(544) + 4 + 20 + 104.
G.f. = 1 + 4*x + 20*x^2 + 104*x^3 + 544*x^4 + 2848*x^5 + 14912*x^6 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..150
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
Index entries for linear recurrences with constant coefficients, signature (6,-4).

Cf. A000045, A001519, A027907, A033887, A046748, A052984, A054108, A069429, A083066, A147703, A163073.

[2^n * Fibonacci(2*n+1): n in [0..40]]; // Vincenzo Librandi, Jul 15 2011

a[ n_] := 2^n Fibonacci[ 2 n + 1]; (* Michael Somos, May 26 2014 *)
a[ n_] := If[ n < 0, SeriesCoefficient[ (2 - x) / (4 - 6 x + x^2), {x, 0, -1 - n}], SeriesCoefficient[ (1 - 2 x) / (1 - 6 x + 4 x^2), {x, 0, n}]]; (* Michael Somos, Oct 22 2017 *)
LinearRecurrence[{6,-4},{1,4},30] (* Harvey P. Dale, Jul 11 2014 *)

a(n)=fibonacci(2*n+1)<Charles R Greathouse IV, Jul 15 2011

{a(n) = if( n<0, n = -1 - n; 2^(-1-2*n), 1) * polcoeff( (1 - 2*x) / (1 - 6*x + 4*x^2) + x * O(x^n), n)}; /* Michael Somos, Oct 22 2017 */

[2^n*fibonacci(2*n+1) for n in range(41)] # G. C. Greubel, Jul 28 2024

a(n) = Sum_{k=0..2*n} A027907(n, k)*A000045(k+1).
From Paul Barry, Jul 16 2003: (Start)
Third binomial transform of (1, 1, 5, 5, 25, 25, ....).
a(n) = ((1+sqrt(5))(3+sqrt(5))^n-(1-sqrt(5))*(3-sqrt(5))^n)/(2*sqrt(5)). (End)
From R. J. Mathar, Nov 04 2008: (Start)
G.f.: (1-2*x)/(1-6*x+4*x^2).
a(n) = 6*a(n-1) - 4*a(n-2). (End)
a(n) = Sum_{k=0..n} A147703(n,k)*3^k. - Philippe Deléham, Nov 14 2008
For n>=2: a(n) = 5*a(n-1) + Sum_{i=1..n-2} a(i). - Bob Selcoe, Mar 18 2014
a(n) = a(-1-n) * 2^(2*n+1) for all n in Z. - Michael Somos, Mar 18 2014
a(n) = 2^n*Fibonacci(2*n+1), or 2^n*A001519(n+1). - Bob Selcoe, May 25 2014
From Michael Somos, May 26 2014: (Start)
a(n) - a(n-1) = A069429(n).
a(n+1) * a(n-1) - a(n)^2 = 4^n.
G.f.: 1 / (1 - 4*x / (1 - x / (1 - x))). (End)
E.g.f.: exp(3*x)*(5*cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, May 24 2024

A020698 a(n) = 5a(n-1) - 2a(n-2), with a(0)=2, a(1)=9.

Original entry on oeis.org

2, 9, 41, 187, 853, 3891, 17749, 80963, 369317, 1684659, 7684661, 35053987, 159900613, 729395091, 3327174229, 15177080963, 69231056357, 315801119859, 1440543486581, 6571115193187, 29974488992773, 136730214577491, 623702094901909, 2845050045354563

Offset: 0

David W. Wilson

Coincides with Pisot sequence L(2,9) (at least for first 1000 terms).
Coincides with Pisot sequence E(2,9) (at least for first 1000 terms).
Theorem: E(2,9) satisfies a(n) = 5 a(n - 1) 2 2 a(n - 2) for n>=2. Proved using the PtoRv program of Ekhad-Sloane-Zeilberger, and implies the conjecture. - N. J. A. Sloane, Sep 09 2016
Number of ways to 3-color a 3 X (n+1) rectangular grid ignoring permutations of the colors. - Andrew Woods, Sep 07 2011

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 78).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. B. Ekhad, N. J. A. Sloane, D. Zeilberger, Automated proofs (or disproofs) of linear recurrences satisfied by Pisot Sequences, arXiv:1609.05570 [math.NT] (2016)
Index entries for linear recurrences with constant coefficients, signature (5,-2).

See A008776 for definitions of Pisot sequences.

Cf. A078099.

m:=24; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((2-x)/(1-5*x+2*x^2))); // Bruno Berselli, Sep 06 2011

I:=[2, 9]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Mar 19 2013

LinearRecurrence[{5,-2},{2,9},30] (* Vladimir Joseph Stephan Orlovsky, Jan 29 2012 *)
CoefficientList[Series[(2 - x)/(1 - 5 x + 2 x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Mar 19 2013 *)

PARI
```
a(n)=([2,1,2;1,1,1;2,1,2]^(n+1))[1,3]
```

a(k-1) = [M^k]1,3, where M is the 3 X 3 matrix [2,1,2; 1,1,1; 2,1,2]. - _Simone Severini, Jun 12 2006
If p[i]=Fibonacci(2i+1) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010
From Bruno Berselli, Sep 06 2011: (Start)
G.f.: (2-x)/(1-5*x+2*x^2).
a(n) = ((17+4*sqrt(17))*(5+sqrt(17))^n+(17-4*sqrt(17))*(5-sqrt(17))^n)/(17*2^n).
a(-n)*2^n = A052984(n-2). (End)
E.g.f.: 2*exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 4*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jun 17 2025

A152124 Number of partitions of a 2 x n rectangle into connected pieces consisting of unit squares cut along lattice lines (like a 2-d analog of a partition into integers) in which each piece has rotational symmetry.

Original entry on oeis.org

1, 2, 8, 36, 162, 746, 3420, 15738, 72352, 332850, 1530928, 7042422, 32394478, 149015678, 685471704, 3153185542, 14504703924, 66721946584, 306922286796, 1411848979422, 6494534685710, 29874996141112, 137425609255358, 632160693109496, 2907952479953454

Offset: 0

Hugo van der Sanden, Mar 23 2009

nonn

			Example: the partitions comprising a(2)=8 are:
AA AA AB AA AB BC BA AB
AA BB AB BC AC AA CA CD
I.e., exactly those of A078469(2)=12 except for the 4 rotations of the one partition that includes an asymmetric piece:
AA
AB

Hugo van der Sanden, Table of n, a(n) for n = 0..100

Cf. A078057, A152113.

Let u(n) represent the number of decompositions of a 1 x n rectangle.
Then: u(n) = 2^(n-1) for n > 0, u(n) = 1 for n = 0.
Let t(n) represent the number of decompositions of a 2 x n rectangle such that a single piece includes the whole of the leftmost and rightmost columns.
Then: t(n) = t(n-2) + sum_1^{(n-3)/2}{ 2 u(i)^2 t(n-2i-2) }
Let s(m, n) represent the number of decompositions of a 2 x n rectangle with a 1 x m spike attached to the side.
Then for m > 0: s(m, n) = sum_1^m{ s(m-i, n) } + sum_1^n{ s(i, n-i) } + sum_m^{(n+m-1)/2}{ u(i-m) sum_1^{n+m-2i}{ t(j) s(i, n+m-2i-j) } } and for m = 0: s(m, n) = sum_1^n{ s(i, n-i) } + sum_1^n{ t(i) s(0, n-i) } + sum_1^{(n-1)/2){ u(i) sum_1^{n-2i}{ t(j) s(i, n-2i-j) } } (Note that these sums can be taken to infinity if the functions are defined as zero when any argument is negative.)
We get t(n) = [ 0 1 1 1 1 3 3 13 13 59 59 269 269 1227 1227 5597 5597 25531 ... ] = A052984((n - 3) / 2) with recurrence a(n) = 5a(n-1)-2a(n-2), a(0) = 1, a(1) = 3.
This gives a much faster way to calculate values for the sequence (as s(0, n)).

Entries changed by N. J. A. Sloane to match the b-file, Oct 04 2010

A152594 a(n) = -5a(n-1)-2a(n-2), n>1 ; a(0)=1, a(1)=-1 .

Original entry on oeis.org

1, -1, 3, -13, 59, -269, 1227, -5597, 25531, -116461, 531243, -2423293, 11053979, -50423309, 230008587, -1049196317, 4785964411, -21831429421, 99585218283, -454263232573, 2072145726299, -9452202166349, 43116719379147

Offset: 0

Philippe Deléham, Dec 09 2008

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

Cf. A052984, A147703.

LinearRecurrence[{-5,-2},{1,-1},30] (* Harvey P. Dale, Jun 18 2015 *)

G.f.: (1+4*x)/(1+5*x+2*x^2).
a(n) = Sum_{k=0..n-1} A147703(n,k)*(-2)^(n-k).
a(n) = (-1)^n*A052984(n-1), n>=1 ; a(0)=1.
E.g.f.: exp(-5*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jun 17 2025

A249581 List of quadruples (r,s,t,u): the matrix M = [[9,24,16][3,10,8][1,4,4]] is raised to successive powers, then (r,s,t,u) are the square roots of M[3,1], M[3,3], M[1,1], M[1,3] respectively.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 3, 4, 5, 8, 13, 20, 23, 36, 59, 92, 105, 164, 269, 420, 479, 748, 1227, 1916, 2185, 3412, 5597, 8740, 9967, 15564, 25531, 39868, 45465, 70996, 116461, 181860, 207391, 323852, 531243, 829564, 946025, 1477268, 2423293, 3784100

Offset: 0

Russell Walsmith, Nov 03 2014

The general form of these matrices is [[t^2,2tu,u^2][rt,st+ru,su][r^2,2rs,s^2]]. Different symmetries have different properties.

Iff |r * u - s * t| = 1 then terms to the left of a(0) are all integers.

			M^0 = [[1,0,0][0,1,0][0,0,1]]. r = sqrt(M[3,1]) = a(0) = 0; s = sqrt(M[3,3]) = a(1) = 1; t = sqrt(M[1,1]) = a(2) = 1; u = sqrt(M[1,3]) = a(3) = 0.
M^1 = [[9,24,16][3,10,8][1,4,4]]. r = sqrt(M[3,1]) = a(4) = 1; s = sqrt(M[3,3]) = a(5) = 2; t = sqrt(M[1,1]) = a(6) = 3; u = sqrt(M[1,3]) = a(7) = 4.

Colin Barker, Table of n, a(n) for n = 0..1000
Russell Walsmith, DCL-Chemy III: Hyper-Quadratics
Index entries for linear recurrences with constant coefficients, signature (0,0,0,5,0,0,0,-2).

Cf. A249579, A249580, A147722, A052984.

LinearRecurrence[{0,0,0,5,0,0,0,-2},{0,1,1,0,1,2,3,4},50] (* Harvey P. Dale, Aug 01 2016 *)

concat(0, Vec(x*(4*x^6-2*x^5-3*x^4+x^3+x+1)/(2*x^8-5*x^4+1) + O(x^100))) \\ Colin Barker, Nov 04 2014

a(4n) + a(4n + 1) = a(4n + 2).
a(4n + 1) + a(4n + 2) + a(4n + 3) - a(4n) = a(4n + 5)
4a(4n) = a(4n+3).
a(4n+1) = A147722(n), a(4n+2) = A052984(n).
a(n) = 5*a(n-4)-2*a(n-8). - Colin Barker, Nov 04 2014
G.f.: x*(4*x^6-2*x^5-3*x^4+x^3+x+1) / (2*x^8-5*x^4+1). - Colin Barker, Nov 04 2014

A340309 Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).

Original entry on oeis.org

0, 6, 48, 282, 1476, 7302, 35016, 164850, 767340, 3546366, 16315248, 74837802, 342621396, 1566620022, 7157423256, 32682574050, 149184117180, 680813718126, 3106475197248, 14173073072922, 64659388538916, 294971717255142, 1345602571317096, 6138257708432850

Offset: 1

Kevin Ryde, Jan 04 2021

Vertices of the Hanoi graph are configurations of discs on pegs in the Towers of Hanoi puzzle.  Edges are a move of a disc from one peg to another.
The shortest path between a pair of vertices u,v may be unique, or there may be 2 different paths.  a(n) is the number of vertex pairs with 2 shortest paths.  Pairs are ordered, so both u,v and v,u are counted.
For a given vertex u, Hinz et al. characterize and count the destinations v which have 2 shortest paths.  Their total x_n is the number of vertex pairs in the graph of n+1 discs.  The present sequence is for n discs so a(n) = x_{n-1}.

			For n=3 discs, the Hanoi graph is
                *           \
               / \          | top
              A---*         | subgraph,
             /     \        | of n-1 = 2
            B       *       | discs
           / \     / \      |
          C---D---E---*     /
         /             \          two shortest
        *               *           paths for
       / \             / \           A to S
      *---*           *---*          B to T
     /     \         /     \         C to R
    *       *       R       *        C to U
   / \     / \     / \     / \       D to S
  *---*---*---*---S---T---U---*
Going from the top subgraph down to the bottom right subgraph, there are 5 vertex pairs with two shortest paths.  C to R goes around the middle 12-cycle either right or left, and likewise D to S.  The other pairs also go each way around the middle.  There are 6 ordered pairs of n-1 subgraphs repeating these 5 pairs.
Within the n-1 = 2 disc top subgraph, A and E are in separate n-2 subgraphs (unit triangles) and they are the only pair with two shortest paths.  Again 6 combinations of these, and in 3 subgraphs.  Total a(3) = 6*5 + 6*3*1 = 48.

Kevin Ryde, Table of n, a(n) for n = 1..500
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse, and Ciril Petr, Metric Properties of the Tower of Hanoi Graphs and Stern's Diatomic Sequence, European Journal of Combinatorics, volume 26, 2005, pages 693-708. See proposition 3.9.
Index entries for linear recurrences with constant coefficients, signature (8,-17,6).
Index entries for sequences related to Towers of Hanoi

Cf. A052984, A107839.

my(p=Mod('x, 'x^2-5*'x+2)); a(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;

With P = (5 + sqrt(17))/2 = A082486, and M = (5 - sqrt(17))/2:
a(n) = (3/(4*sqrt(17)))*( (sqrt(17)+1)*P^n - 2*sqrt(17)*3^n + (sqrt(17)-1)*M^n ). [Hinz et al.]
a(n) = (6/sqrt(17)) * Sum_{k=0..n-1} 3^k * (P^(n-1-k) - M^(n-1-k)) [Hinz et al.].
a(n) = 3*a(n-1) + 6*A107839(n-2), paths within and between subgraphs n-1.
a(n) = 8*a(n-1) - 17*a(n-2) + 6*a(n-3).
a(n) = (A052984(n) - 3^n)*3/2.
G.f.: 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x)).
G.f.: (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x).

cp's OEIS Frontend

A052961 Expansion of (1 - 3*x) / (1 - 5*x + 3*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A104934 Expansion of (1-x)/(1 - 3*x - 2*x^2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Julia

Magma

Maple

Mathematica

PARI

SageMath

Formula

A005824 a(n) = 5*a(n-2) - 2*a(n-4), with initial terms 0,1,1,3.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A160232 Array read by antidiagonals: row n has g.f. ((1-x)/(1-2x))^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A082761 Trinomial transform of the Fibonacci numbers (A000045).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

SageMath

Formula

A020698 a(n) = 5*a(n-1) - 2*a(n-2), with a(0)=2, a(1)=9.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Magma

Mathematica

A052961 Expansion of (1 - 3x) / (1 - 5x + 3*x^2).

A104934 Expansion of (1-x)/(1 - 3x - 2x^2).

A005824 a(n) = 5a(n-2) - 2a(n-4), with initial terms 0,1,1,3.

A020698 a(n) = 5a(n-1) - 2a(n-2), with a(0)=2, a(1)=9.

A152594 a(n) = -5a(n-1)-2a(n-2), n>1 ; a(0)=1, a(1)=-1 .