A217233 -id:A217233 - cp's OEIS frontend

A052530 a(n) = 4*a(n-1) - a(n-2), with a(0) = 0, a(1) = 2.

0, 2, 8, 30, 112, 418, 1560, 5822, 21728, 81090, 302632, 1129438, 4215120, 15731042, 58709048, 219105150, 817711552, 3051741058, 11389252680, 42505269662, 158631825968, 592022034210, 2209456310872, 8245803209278, 30773756526240

Offset: 0

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

a(n-1) and a(n+1) are the solutions for c if b = a(n) in (b^2 + c^2)/(b*c + 1) = 4 and there are no other pairs of solutions apart from consecutive pairs of terms in this sequence. Cf. A061167. - Henry Bottomley, Apr 18 2001
a(n)^2 for n >= 1 gives solutions to A007913(3*x+4) = A007913(x). - Benoit Cloitre, Apr 07 2002
For all terms k of the sequence, 3*k^2 + 4 is a perfect square. Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - Gregory V. Richardson, Oct 06 2002
a(n) = the number of compositions of the integer 2*n into even parts, where each part 2*i comes in 2*i colors. (Dedrickson, Theorem 3.2.6) An example is given below. Cf. A052529, A095263. - Peter Bala, Sep 17 2013
Except for an initial 1, this is the p-INVERT of (1, 1, 1, 1, 1, ...) for p(S) = 1 - 2*S - 2*S^2; see A291000.  - Clark Kimberling, Aug 24 2017
a(n+1) is the number of spanning trees of the graph P_n, where P_n is a 2 X n grid with two additional vertices, u and v, where u is adjacent to (1,1) and (2,1), and v is adjacent to (1,n) and (2,n). - Kevin Long, May 04 2018
a(n) is also the output of Tesler's formula for the number of perfect matchings of an m X n Mobius band where m is even and n is odd, specialized to m=2. (The twist is on the length-n side.) - Sarah-Marie Belcastro, Feb 15 2022
In general, values of x and y which satisfy (x^2 + y^2)/(x*y + 1) = k^2 are any two adjacent terms of a second-order recurrence with initial terms 0 and k and signature (k^2,-1). This can also be expressed as a first-order recurrence a(n+1) = (k^2*a(n) + sqrt((k^4-4)*a(n)^2 + 4*k^2))/2, n > 1. - Gary Detlefs, Feb 27 2024

			Colored compositions. a(2) = 8: There are two compositions of 4 into even parts, namely 4 and 2 + 2. Using primes to indicate the coloring of parts, the 8 colored compositions are 4, 4', 4'', 4''', 2 + 2, 2 + 2', 2' + 2 and 2' + 2'. - _Peter Bala_, Sep 17 2013

T. D. Noe, Table of n, a(n) for n = 0..200
K. Andersen, L. Carbone, and D. Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
C. R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, 2012, Jack N. Averitt College of Graduate Studies, Georgia Southern University.
J.-P. Ehrmann et al., Problem POLYA002, Integer pairs (x,y) for which (x^2+y^2)/(1+pxy) is an integer.
F. Goebel and A. A. Jagers, On a conjecture of Tutte concerning minimal tree numbers, J. Combin. Theory Ser. B 26 (1979), no. 3, 346-348. MR0535948 (80m:05064). [From _N. J. A. Sloane_, Feb 20 2012]
A. F. Horadam, Basic Properties of a Certain Generalized Sequence of Numbers, Fibonacci Quarterly, Vol. 3, No. 3, 1965, pp. 161-176.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 460
N. J. A. Sloane, Transforms
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A001353, A007913, A003699, A217233.

Cf. A052529, A095263.

a052530 n = a052530_list !! n
a052530_list =
   0 : 2 : zipWith (-) (map (* 4) $ tail a052530_list) a052530_list
-- Reinhard Zumkeller, Sep 29 2011

I:=[0,2]; [n le 2 select I[n] else 4*Self(n-1) - Self(n-2): n in [1..30]]; // G. C. Greubel, Feb 25 2019

spec := [S,{S=Sequence(Prod(Union(Z,Z),Sequence(Z),Sequence(Z)))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
s := sqrt(3): a := n -> ((2-s)^n-(s+2)^n)/(s*(s-2)*(s+2)):
seq(simplify(a(n)), n=0..24); # Peter Luschny, Apr 28 2020

p=1; c=2; a[0]=0; a[1]=c; a[n_]:=a[n]=p*c^2*a[n-1]-a[n-2]; Table[a[n], {n, 0, 20}]
NestList[2 # + Sqrt[4 + 3 #^2]&, 0, 200] (* Zak Seidov, Mar 31 2011 *)
LinearRecurrence[{4, -1}, {0, 2}, 25] (* T. D. Noe, Jan 09 2012 *)
CoefficientList[Series[2x/(1-4x+x^2),{x,0,30}],x] (* Harvey P. Dale, May 31 2023 *)

{ polya002(p,c,m) = local(v,w,j,a); w=0; print1(w,", "); v=c; print1(v,", "); j=1; while(j<=m,a=p*c^2*v-w; print1(a,", "); w=v; v=a; j++) };
polya002(1,2,25)

my(x='x+O('x^30)); concat([0], Vec(2*x/(1-4*x+x^2))) \\ G. C. Greubel, Feb 25 2019

first(n) = n = max(n, 2); my(res = vector(n)); res[1] = 0; res[2] = 2; for(i = 3, n, res[i] = 4 * res[i-1] - res[i-2]); res \\ David A. Corneth, Apr 28 2020

(2*x/(1-4*x+x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 25 2019

G.f.: 2*x/(1 - 4*x + x^2).
Invert transform of even numbers: a(n) = 2*Sum_{k=1..n} k*a(n-k). - Vladeta Jovovic, Apr 27 2001
From Gregory V. Richardson, Oct 06 2002: (Start)
a(n) = Sum_{alpha} -(1/3)*(-1 + 2*alpha)*alpha^(-1 - n), alpha = root of (1 - 4*Z + Z^2).
a(n) = (((2+sqrt(3))^(n+1) - (2-sqrt(3))^(n+1)) - ((2+sqrt(3))^n - (2-sqrt(3))^n) + ((2+sqrt(3))^(n-1) - (2-sqrt(3))^(n-1)))/(3*sqrt(3)). (End)
a(n) = A071954(n) - 2. - N. J. A. Sloane, Feb 20 2005
a(n) = (2*sinh(2n*arcsinh(1/sqrt(2))))/sqrt(3). - Herbert Kociemba, Apr 24 2008
a(n) = 2*A001353(n). - R. J. Mathar, Oct 26 2009
a(n) = ((3 - 2*sqrt(3))/3)*(2 - sqrt(3))^(n - 1) + ((3 + 2*sqrt(3))/3)*(2 + sqrt(3))^(n - 1). - Vincenzo Librandi, Nov 20 2010
a(n) = floor((2 + sqrt(3))^n/sqrt(3)). - Zak Seidov, Mar 31 2011
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/sqrt(3). (See Horadam for construction.) - Johannes Boot, Jan 08 2012
a(n) = A217233(n) + A217233(n-1) with A217233(-1) = -1. - Bruno Berselli, Oct 01 2012
a(n) = A001835(n+1) - A001835(n). - Kevin Long, May 04 2018
E.g.f.: (exp((2 + sqrt(3))*x) - exp((2 - sqrt(3))*x))/sqrt(3). - Franck Maminirina Ramaharo, Nov 12 2018
a(n+1) = 2*a(n) + sqrt(3*a(n)^2 + 4), n > 1. - Gary Detlefs, Feb 27 2024

More terms from James Sellers, Jun 06 2000
Edited by N. J. A. Sloane, Nov 11 2006
a(0) changed to 0 and entry revised accordingly by Max Alekseyev, Nov 15 2007
Signs in definition corrected by John W. Layman, Nov 20 2007

A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.

Original entry on oeis.org

1, 2, 9, 32, 121, 450, 1681, 6272, 23409, 87362, 326041, 1216800, 4541161, 16947842, 63250209, 236052992, 880961761, 3287794050, 12270214441, 45793063712, 170902040409, 637815097922, 2380358351281, 8883618307200, 33154114877521, 123732841202882

Offset: 0

N. J. A. Sloane

Number of tilings of a box with sides 2 X 2 X n in R^3 by boxes of sides 2 X 1 X 1 (3-dimensional dominoes). - Frans J. Faase
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Also stacking bricks.
a(n)*(-1)^n = (1-T(n+1,-2))/3, n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-2 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - Wolfdieter Lang, Oct 18 2004
Partial sums of A217233. - Bruno Berselli, Oct 01 2012
The sequence is the case P1 = 2, P2 = -8, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014

			G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Butler and S. Osborne, Counting tilings by taking walks, preprint, 2012; J. Combin. Math. Combin. Comput. 88 2014 17-25. - From _N. J. A. Sloane_, Dec 27 2012
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97
D. Deford, Seating rearrangements on arbitrary graphs, preprint 2013; involve, Vol. 7 (2014), No. 6, 787-805.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
Charles H. Jepsen, Packing a box with bricks, Math. Mag. 64 (2) (1991) 92-97, Table 1
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (36).
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
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.
Radovan Potůček, The number of fillings a 2 X 2 X n prism with 1 X 1 X 2 prisms, Equations (2024) Vol. 3, 104-114.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for sequences related to dominoes
Index entries for sequences related to bricks
Index entries for linear recurrences with constant coefficients, signature (3,3,-1).

Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums).
Column k=2 of A181206, A189650, A233308.
Cf. A100047.

a:=[1,2,9];; for n in [4..30] do a[n]:=3*a[n-1]+3*a[n-2]-a[n-3]; od; a; # G. C. Greubel, Nov 16 2018

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // G. C. Greubel, Nov 16 2018

CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 15 2012 *)
RecurrenceTable[{a[1] == 1, a[2] == 2, a[n] == BitXor[1, a[n - 1]]^2/a[n - 2]}, a, {n, 30}] (* Jon Maiga, Nov 16 2018 *)
LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* G. C. Greubel, Nov 16 2018 *)
a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* Michael Somos, Mar 17 2022 *)

a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ Charles R Greathouse IV, Aug 18 2016

a(n)=([0,1,0; 0,0,1; -1,3,3]^n*[1;2;9])[1,1] \\ Charles R Greathouse IV, Aug 18 2016

Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017

{a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* Michael Somos, Mar 17 2022 */

s=((1-x)/(1-3*x-3*x^2+x^3)).series(x,30); s.coefficients(x, sparse=False) # G. C. Greubel, Nov 16 2018

G.f.: (1-x)/((1+x)*(1-4*x+x^2)) = (1-x)/(1-3*x-3*x^2+x^3). - Simon Plouffe in his 1992 dissertation; typo corrected by Vincenzo Librandi, Oct 15 2012
Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - Don Knuth, Jul 15 1995
For n >= 4, a(n) = 3a(n-1) + 3a(n-2) - a(n-3). - Avi Peretz (njk(AT)netvision.net.il), Mar 30 2001
For n >= 3, a(n) = 4a(n-1) - a(n-2) + 2*(-1)^n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 14 2001
From Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 11 2001: The values are a(1) = 2 * 1^2, a(2) = 3^2, a(3) = 2 * 4^2, a(4) = 11^2, a(5) = 2 * 15^2, ... and in general for odd n a(n) is twice a square, for even n a(n) is a square. If we define b(n) by b(n) = sqrt(a(n)) for even n, b(n) = sqrt(a(n)/2) for odd n then apart from the first 2 elements b(n) is A002530(n+1).
a(n) + a(n+1) = A001835(n+2). - R. J. Mathar, Dec 06 2013
From Peter Bala, Apr 03 2014: (Start)
a(n) = |U(n,i/sqrt(2))|^2 where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n-1) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 2; 1, 1] and T(n,x) denotes the Chebyshev polynomial of the first kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - Colin Barker, Dec 16 2017
a(n) = (1 XOR a(n-1))^2/a(n-2). - Jon Maiga, Nov 16 2018
a(n) = a(-2-n) for all n in Z. - Michael Somos, Mar 17 2022
INVERT transform of sequence p(n), n > 0, where p is the number of nonreducible tilings by height of 2 X 2 X n using dicubes; p is (2, 5, 4, 4, 4, 4...). - Nicolas Bělohoubek, Jun 04 2024

cp's OEIS Frontend

A052530 a(n) = 4*a(n-1) - a(n-2), with a(0) = 0, a(1) = 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula