A103999 -id:A103999 - cp's OEIS frontend

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

0, 1, 1, 0, 2, 0, 1, 3, 3, 1, 0, 5, 0, 5, 0, 1, 8, 11, 11, 8, 1, 0, 13, 0, 36, 0, 13, 0, 1, 21, 41, 95, 95, 41, 21, 1, 0, 34, 0, 281, 0, 281, 0, 34, 0, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 0, 89, 0, 2245, 0, 6728, 0, 2245, 0, 89, 0, 1, 144, 571, 6336, 14824, 31529, 31529, 14824, 6336, 571, 144, 1

Offset: 1

Ralf Stephan, Oct 16 2004

There are many versions of this array (or triangle) in the OEIS. This is the main entry, which ideally collects together all the references to the literature and to other versions in the OEIS. But see A004003 for further information. - N. J. A. Sloane, Mar 14 2015

			0,  1,  0,   1,    0,    1, ...
1,  2,  3,   5,    8,   13, ...
0,  3,  0,  11,    0,   41, ...
1,  5, 11,  36,   95,  281, ...
0,  8,  0,  95,    0, 1183, ...
1, 13, 41, 281, 1183, 6728, ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
P. E. John, H. Sachs, and H. Zernitz, Problem 5. Domino covers in square chessboards, Zastosowania Matematyki (Applicationes Mathematicae) XIX 3-4 (1987), 635-641.
R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.
Darko Veljan, Kombinatorika: s teorijom grafova (Croatian) (Combinatorics with Graph Theory) mentions the value 12988816 = 2^4*901^2 for the 8 X 8 case on page 4.

Alois P. Heinz, Table of n, a(n) for n = 1..1035
M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97.
Henry Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic Journal of Combinatorics, 6 (1999), #R14.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
Steven R. Finch, Two Dimensional Monomer Dimer Constant [Broken link]
M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physical Review, 124 (1961), 1664-1672.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 363.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015.
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, arXiv:math/9801094 [math.CO], 1998.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, Discrete Math. 216 (2000), no. 1-3, 211-219.
Yuhi Kamio, Junnosuke Koizumi, and Toshihiko Nakazawa, Quadratic residues and domino tilings, arXiv:2311.13597 [math.NT], 2023.
David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52, Table 1.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
P. W. Kasteleyn, The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225.
Douglas M. McKenna, The Art of Space-Filling Domino Curves, Bridges Conference Proceedings, 2024, pp. 319-326.
L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.
J. Propp, Dimers and Dominoes
J. Propp, Enumeration of Matchings: Problems and Progress, arXiv:math/9904150v2 [math.CO], 1999.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
R. C. Read, A Note on Tiling Rectangles with Dominoes, The Fibonacci Quarterly, 18.1 (1980), 24-27.
R. P. Stanley, A combinatorial miscellany
H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics -- an exact result, Philos. Mag. (8) 6 (1961), 1061-1063.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Domino Tiling
Eric Weisstein, Illustration for T(4,4) = 36, from Domino Tilings web page (see previous link) [Included with permission]
Index entries for sequences related to dominoes

See A187596 for another version (with m >= 0, n >= 0). See A187616 for a triangular version. See also A187617, A187618.
See also A004003 for more literature on the dimer problem.
Rows 2-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.
Main diagonal is A004003.
Cf. A103997, A103999, A233320, A230031, A233427.

(Maple code for the even-numbered rows from N. J. A. Sloane, Mar 15 2015. This is not totally satisfactory since it uses floating point. However, it is useful for getting the initial values quickly.)
Digits:=100;
p:=evalf(Pi);
z:=proc(h,d) global p; evalf(cos( h*p/(2*d+1) )); end;
T:=proc(m,n) global z; round(mul( mul( 4*z(h,m)^2+4*z(k,n)^2, k=1..n), h=1..m)); end;
[seq(T(1,n),n=0..10)]; # A001519
[seq(T(2,n),n=0..10)]; # A188899
[seq(T(3,n),n=0..10)]; # A256044
[seq(T(n,n),n=0..10)]; # A004003

T[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2*(2+Cos[2j*Pi/(m+1)]+Cos[2k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
Flatten[Table[Round[T[m-n+1, n]], {m, 1, 12}, {n, 1, m}]] (* Jean-François Alcover, Nov 25 2011, updated May 28 2022 *)

{T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ Seiichi Manyama, Apr 13 2020

T(m, n) = Product_{j=1..ceiling(m/2)} Product_{k=1..ceiling(n/2)} (4*cos(j*Pi/(m+1))^2 + 4*cos(k*Pi/(n+1))^2).

Old link fixed and new link added by Frans J. Faase, Feb 04 2009

Entry edited by N. J. A. Sloane, Mar 15 2015

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

Original entry on oeis.org

2, 4, 14, 52, 194, 724, 2702, 10084, 37634, 140452, 524174, 1956244, 7300802, 27246964, 101687054, 379501252, 1416317954, 5285770564, 19726764302, 73621286644, 274758382274, 1025412242452, 3826890587534, 14282150107684, 53301709843202, 198924689265124

Offset: 0

N. J. A. Sloane

a(n) gives values of x satisfying x^2 - 3*y^2 = 4; corresponding y values are given by 2*A001353(n).
If M is any given term of the sequence, then the next one is 2*M + sqrt(3*M^2 - 12). - Lekraj Beedassy, Feb 18 2002
For n > 0, the three numbers a(n) - 1, a(n), and a(n) + 1 form a Fleenor-Heronian triangle, i.e., a Heronian triangle with consecutive sides, whose area A(n) may be obtained from the relation [4*A(n)]^2 = 3([a(2n)]^2 - 4); or A(n) = 3*A001353(2*n)/2 and whose semiperimeter is 3*a[n]/2. The sequence is symmetrical about a[0], i.e., a[-n] = a[n].
For n > 0, a(n) + 2 is the number of dimer tilings of a 2*n X 2 Klein bottle (cf. A103999).
Tsumura shows that, for prime p, a(p) is composite (contrary to a conjecture of Juricevic). - Charles R Greathouse IV, Apr 13 2010
Except for the first term, positive values of x (or y) satisfying x^2 - 4*x*y + y^2 + 12 = 0. - Colin Barker, Feb 04 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 14*x*y + y^2 + 192 = 0. - Colin Barker, Feb 16 2014
A268281(n) - 1 is a member of this sequence iff A268281(n) is prime. - Frank M Jackson, Feb 27 2016
a(n) gives values of x satisfying 3*x^2 - 4*y^2 = 12; corresponding y values are given by A005320. - Sture Sjöstedt, Dec 19 2017
Middle side lengths of almost-equilateral Heronian triangles. - Wesley Ivan Hurt, May 20 2020
For all elements k of the sequence, 3*(k-2)*(k+2) is a square. - Davide Rotondo, Oct 25 2020

B. C. Berndt, Ramanujan's Notebooks Part IV, Springer-Verlag, see p. 82.
J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p.91.
Michael P. Cohen, Generating Heronian Triangles With Consecutive Integer Sides. Journal of Recreational Mathematics, vol. 30 no. 2 1999-2000 p. 123.
L. E. Dickson, History of The Theory of Numbers, Vol. 2 pp. 197;198;200;201. Chelsea NY.
Charles R. Fleenor, Heronian Triangles with Consecutive Integer Sides, Journal of Recreational Mathematics, Volume 28, no. 2 (1996-7) 113-115.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
V. D. To, "Finding All Fleenor-Heronian Triangles", Journal of Recreational Mathematics vol. 32 no.4 2003-4 pp. 298-301 Baywood NY.

T. D. Noe, Table of n, a(n) for n=0..200
P. Bala, Some simple continued fraction expansions for an infinite product, Part 1
R. A. Beauregard and E. R. Suryanarayan, The Brahmagupta Triangles, The College Mathematics Journal 29(1) 13-7 1998 MAA.
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, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv preprint arXiv:1505.06339 [math.NT], 2015.
K. S. Brown's Mathpages, Some Properties of the Lucas Sequence(2, 4, 14, 52, 194, ...)
H. W. Gould, A triangle with integral sides and area, Fib. Quart., 11 (1973), 27-39.
Tanya Khovanova, Recursive Sequences
E. Keith Lloyd, The Standard Deviation of 1, 2, ..., n: Pell's Equation and Rational Triangles, Math. Gaz. vol 81 (1997), 231-243.
S. Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, 18 (2015), #15.11.6.
Hideyuki Ohtskua, proposer, Problem B-1351, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 3 (2024), p. 258.
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, An interesting continued fraction, Math. Mag., 48 (1975), 207-211.
Jeffrey Shallit, An interesting continued fraction, Math. Mag., 48 (1975), 207-211. [Annotated scanned copy]
Yu Tsumura, On compositeness of special types of integers, arXiv:1004.1244 [math.NT], 2010.
Eric Weisstein's World of Mathematics, Heronian Triangle
Wikipedia, Heronian triangle
A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A001075, A001353, A001835.
Cf. A011945 (areas), A334277 (perimeters).
Cf. this sequence (middle side lengths), A016064 (smallest side lengths), A335025 (largest side lengths).
Cf. A001570, A002530, A005320, A006051, A048788, A174500, A268281.
Cf. A011943, A102344, A019673, A105531.

a003500 n = a003500_list !! n
a003500_list = 2 : 4 : zipWith (-)
   (map (* 4) $ tail a003500_list) a003500_list
-- Reinhard Zumkeller, Dec 17 2011

I:=[2,4]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 14 2018

A003500 := proc(n) option remember; if n <= 1 then 2*n+2 else 4*procname(n-1)-procname(n-2); fi;
end proc;

a[0]=2; a[1]=4; a[n_]:= a[n]= 4a[n-1] -a[n-2]; Table[a[n], {n, 0, 23}]
LinearRecurrence[{4,-1},{2,4},30] (* Harvey P. Dale, Aug 20 2011 *)
Table[Round@LucasL[2n, Sqrt[2]], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)

x='x+O('x^99); Vec(-2*(-1+2*x)/(1-4*x+x^2)) \\ Altug Alkan, Apr 04 2016

[lucas_number2(n,4,1) for n in range(0, 24)] # Zerinvary Lajos, May 14 2009

a(n) = ( 2 + sqrt(3) )^n + ( 2 - sqrt(3) )^n.
a(n) = 2*A001075(n).
G.f.: 2*(1 - 2*x)/(1 - 4*x + x^2). Simon Plouffe in his 1992 dissertation.
a(n) = A001835(n) + A001835(n+1).
a(n) = trace of n-th power of the 2 X 2 matrix [1 2 / 1 3]. - Gary W. Adamson, Jun 30 2003 [corrected by Joerg Arndt, Jun 18 2020]
From the addition formula, a(n+m) = a(n)*a(m) - a(m-n), it is easy to derive multiplication formulas, such as: a(2*n) = (a(n))^2 - 2, a(3*n) = (a(n))^3 - 3*(a(n)), a(4*n) = (a(n))^4 - 4*(a(n))^2 + 2, a(5*n) = (a(n))^5 - 5*(a(n))^3 + 5*(a(n)), a(6*n) = (a(n))^6 - 6*(a(n))^4 + 9*(a(n))^2 - 2, etc. The absolute values of the coefficients in the expansions are given by the triangle A034807. - John Blythe Dobson, Nov 04 2007
a(n) = 2*A001353(n+1) - 4*A001353(n). - R. J. Mathar, Nov 16 2007
From Peter Bala, Jan 06 2013: (Start)
Let F(x) = Product_{n=0..infinity} (1 + x^(4*n + 1))/(1 + x^(4*n + 3)). Let alpha = 2 - sqrt(3). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.24561 99455 06551 88869 ... = 2 + 1/(4 + 1/(14 + 1/(52 + ...))). Cf. A174500.
Also F(-alpha) = 0.74544 81786 39692 68884 ... has the continued fraction representation 1 - 1/(4 - 1/(14 - 1/(52 - ...))) and the simple continued fraction expansion 1/(1 + 1/((4 - 2) + 1/(1 + 1/((14 - 2) + 1/(1 + 1/((52 - 2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((4^2 - 4) + 1/(1 + 1/((14^2 - 4) + 1/(1 + 1/((52^2 - 4) + 1/(1 + ...))))))).
(End)
a(2^n) = A003010(n). - John Blythe Dobson, Mar 10 2014
a(n) = [x^n] ( (1 + 4*x + sqrt(1 + 8*x + 12*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
E.g.f.: 2*exp(2*x)*cosh(sqrt(3)*x). - Ilya Gutkovskiy, Apr 27 2016
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*n*(n - k - 1)!/(k!*(n - 2*k)!)*4^(n - 2*k) for n >= 1. - Peter Luschny, May 10 2016
From Peter Bala, Oct 15 2019: (Start)
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; -1, 4].
Consequently the Gauss congruences hold: a(n*p^k) = a(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. See Zarelua and also Stanley (Ch. 5, Ex. 5.2(a) and its solution).
2*Sum_{n >= 1} 1/( a(n) - 6/a(n) ) = 1.
6*Sum_{n >= 1} (-1)^(n+1)/( a(n) + 2/a(n) ) = 1.
8*Sum_{n >= 1} 1/( a(n) + 24/(a(n) - 12/(a(n))) ) = 1.
8*Sum_{n >= 1} (-1)^(n+1)/( a(n) + 8/(a(n) + 4/(a(n))) ) = 1.
Series acceleration formulas for sums of reciprocals:
Sum_{n >= 1} 1/a(n) = 1/2 - 6*Sum_{n >= 1} 1/(a(n)*(a(n)^2 - 6)),
Sum_{n >= 1} 1/a(n) = 1/8 + 24*Sum_{n >= 1} 1/(a(n)*(a(n)^2 + 12)),
Sum_{n >= 1} (-1)^(n+1)/a(n) = 1/6 + 2*Sum_{n >= 1} (-1)^(n+1)/(a(n)*(a(n)^2 + 2)) and
Sum_{n >= 1} (-1)^(n+1)/a(n) = 1/8 + 8*Sum_{n >= 1} (-1)^(n+1)/(a(n)*(a(n)^2 + 12)).
Sum_{n >= 1} 1/a(n) = ( theta_3(2-sqrt(3))^2 - 1 )/4 = 0.34770 07561 66992 06261 .... See Borwein and Borwein, Proposition 3.5 (i), p.91.
Sum_{n >= 1} (-1)^(n+1)/a(n) = ( 1 - theta_3(sqrt(3)-2)^2 )/4. Cf. A003499 and A153415. (End)
a(n) = tan(Pi/12)^n + tan(5*Pi/12)^n. - Greg Dresden, Oct 01 2020
From Wolfdieter Lang, Sep 06 2021: (Start)
a(n) = S(n, 4) - S(n-2, 4) = 2*T(n, 2), for n >= 0, with S and T Chebyshev polynomials, with S(-1, x) = 0 and S(-2, x) = -1. S(n, 4) = A001353(n+1), for n >= -1, and T(n, 2) = A001075(n).
a(2*k) = A067902(k), a(2*k+1) = 4*A001570(k+1), for k >= 0. (End)
a(n) = sqrt(2 + 2*A011943(n+1)) = sqrt(2 + 2*A102344(n+1)), n>0. - Ralf Steiner, Sep 23 2021
Sum_{n>=1} arctan(3/a(n)^2) = Pi/6 - arctan(1/3) = A019673 - A105531 (Ohtskua, 2024). - Amiram Eldar, Aug 29 2024

More terms from James Sellers, May 03 2000

Additional comments from Lekraj Beedassy, Feb 14 2002

A003499 a(n) = 6*a(n-1) - a(n-2), with a(0) = 2, a(1) = 6.

Original entry on oeis.org

2, 6, 34, 198, 1154, 6726, 39202, 228486, 1331714, 7761798, 45239074, 263672646, 1536796802, 8957108166, 52205852194, 304278004998, 1773462177794, 10336495061766, 60245508192802, 351136554095046, 2046573816377474, 11928306344169798, 69523264248641314

Offset: 0

N. J. A. Sloane

Two times Chebyshev polynomials of the first kind evaluated at 3.
Also 2(a(2*n)-2) and a(2*n+1)-2 are perfect squares. - Mario Catalani (mario.catalani(AT)unito.it), Mar 31 2003
Chebyshev polynomials of the first kind evaluated at 3, then multiplied by 2. - Michael Somos, Apr 07 2003
Also gives solutions > 2 to the equation x^2 - 3 = floor(x*r*floor(x/r)) where r=sqrt(2). - Benoit Cloitre, Feb 14 2004
Output of Lu and Wu's formula for the number of perfect matchings of an m X n Klein bottle where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
It appears that for prime P = 8*n +- 3, that a((P-1)/2) == -6 (mod P) and for all composites C = 8*n +- 3, there is at least one i < (C-1)/2 such that a(i) == -6 (mod P). Only a few of the primes P of the form 8*n +-3, e.g., 29, had such an i less than (P-1)/2. As for primes P = 8*n +- 1, it seems that the sum of the two adjacent terms, a((P-1)/2) and a((P+1)/2), is congruent to 8 (mod P). - Kenneth J Ramsey, Feb 14 2012 and Mar 05 2012
For n >= 1, a(n) is also the curvature of circles (rounded to the nearest integer) successively inscribed toward angle 90 degree of tangent lines, starting with a unit circle. The expansion factor is 5.828427... or 1/(3 - 2*sqrt(2)), which is also 3 + 2*sqrt(2) or A156035. See illustration in links. - Kival Ngaokrajang, Sep 04 2013
Except for the first term, positive values of x (or y) satisfying x^2 - 6*x*y + y^2 + 32 = 0. - Colin Barker, Feb 08 2014

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 198.
Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002; pp. 480-481.
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 2001, Wiley, pp. 77-79.
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..300
Seyed Hassan Alavi, Ashraf Daneshkhah, and Cheryl E. Praeger, Symmetries of biplanes, arXiv:2004.04535 [math.GR], 2020. See Lemma 7.9 p. 21.
Peter Bala, Some simple continued fraction expansions for an infinite product, Part 1
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.
P. Bhadouria, D. Jhala, and B. Singh, Binomial Transforms of the k-Lucas Sequences and its Properties, The Journal of Mathematics and Computer Science (JMCS), Volume 8, Issue 1, Pages 81-92; sequence K_3.
S. Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, 2014, 5, 2226-2234.
Refik Keskin and Olcay Karaatli, Some New Properties of Balancing Numbers and Square Triangular Numbers, Journal of Integer Sequences, Vol. 15 (2012), #12.1.4.
Tanya Khovanova, Recursive Sequences
W. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, arXiv:cond-mat/0110035 [cond-mat.stat-mech], 2001-2002; Physics Letters A, 293(2002), 235-246. [From Sarah-Marie Belcastro, Jul 04 2009]
Kival Ngaokrajang, Illustration of initial terms
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, An interesting continued fraction, Math. Mag., 48 (1975), 207-211.
Jeffrey Shallit, An interesting continued fraction, Math. Mag., 48 (1975), 207-211. [Annotated scanned copy]
Soumeya M. Tebtoub, Hacène Belbachir, and László Németh, Integer sequences and ellipse chains inside a hyperbola, Proceedings of the 1st International Conference on Algebras, Graphs and Ordered Sets (ALGOS 2020), hal-02918958 [math.cs], 17-18.
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (6,-1).

A081555(n) = 1 + a(n).
Bisection of A002203.
First row of array A103999.
Row 1 * 2 of array A188645. A174501.

a:=[2,6];; for n in [3..25] do a[n]:=6*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Jan 16 2020

I:=[2,6]; [n le 2 select I[n] else 6*Self(n-1) -Self(n-2): n in [1..25]]; // G. C. Greubel, Jan 16 2020

R:=PowerSeriesRing(Integers(), 25); Coefficients(R!( (2-6*x)/(1 - 6*x + x^2) )); // Marius A. Burtea, Jan 16 2020

A003499:=-2*(-1+3*z)/(1-6*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation

a[0]=2; a[1]=6; a[n_]:= 6a[n-1] -a[n-2]; Table[a[n], {n,0,25}] (* Robert G. Wilson v, Jan 30 2004 *)
Table[Tr[MatrixPower[{{6, -1}, {1, 0}}, n]], {n, 25}] (* Artur Jasinski, Apr 22 2008 *)
LinearRecurrence[{6, -1}, {2, 6}, 25] (* Vladimir Joseph Stephan Orlovsky, Feb 26 2012 *)
CoefficientList[Series[(2-6x)/(1-6x+x^2), {x,0,25}], x] (* Vincenzo Librandi, Jun 07 2013 *)
(* From Eric W. Weisstein, Apr 17 2018 *)
Table[(3-2Sqrt[2])^n + (3+2Sqrt[2])^n, {n,0,25}]//Expand
Table[(1+Sqrt[2])^(2n) + (1-Sqrt[2])^(2n), {n,0,25}]//FullSimplify
Join[{2}, Table[Fibonacci[4n, 2]/Fibonacci[2n, 2], {n, 25}]]
2*ChebyshevT[Range[0, 25], 3] (* End *)

PARI
```
a(n)=2*real((3+quadgen(32))^n)
```
PARI
```
a(n)=2*subst(poltchebi(abs(n)),x,3)
```

a(n)=if(n<0,a(-n),polsym(1-6*x+x^2,n)[n+1])

[lucas_number2(n,6,1) for n in range(37)] # Zerinvary Lajos, Jun 25 2008

G.f.: (2-6*x)/(1 - 6*x + x^2).
a(n) = (3+2*sqrt(2))^n + (3-2*sqrt(2))^n = 2*A001541(n).
For all sequence elements n, 2*n^2 - 8 is a perfect square. Limit_{n->infinity} a(n)/a(n-1) = 3 + 2*sqrt(2). - Gregory V. Richardson, Oct 06 2002
a(2*n)+2 is a perfect square, 2(a(2*n+1)+2) is a perfect square. a(n), a(n-1) and A077445(n), n > 0, satisfy the Diophantine equation x^2 + y^2 - 3*z^2 = -8. - Mario Catalani (mario.catalani(AT)unito.it), Mar 24 2003
a(n+1) is the trace of n-th power of matrix {{6, -1}, {1, 0}}. - Artur Jasinski, Apr 22 2008
a(n) = Product_{r=1..n} (4*sin^2((4*r-1)*Pi/(4*n)) + 4). [Lu/Wu] - Sarah-Marie Belcastro, Jul 04 2009
a(n) = (1 + sqrt(2))^(2*n) + (1 + sqrt(2))^(-2*n). - Gerson Washiski Barbosa, Sep 19 2010
For n > 0, a(n) = A001653(n) + A001653(n+1). - Charlie Marion, Dec 27 2011
For n > 0, a(n) = b(4*n)/b(2*n) where b(n) is the Pell sequence, A000129. - Kenneth J Ramsey, Feb 14 2012
From Peter Bala, Jan 06 2013: (Start)
Let F(x) = Product_{n >= 0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 3 - 2*sqrt(2). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.16585 37786 96882 80543 ... = 2 + 1/(6 + 1/(34 + 1/(198 + ...))). Cf. A174501.
Also F(-alpha) = 0.83251219269380007634 ... has the continued fraction representation 1 - 1/(6 - 1/(34 - 1/(198 - ...))) and the simple continued fraction expansion 1/(1 + 1/((6-2) + 1/(1 + 1/((34-2) + 1/(1 + 1/((198-2) + 1/(1 + ...))))))). Cf. A174501 and A003500.
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((6^2-4) + 1/(1 + 1/((34^2-4) + 1/(1 + 1/((198^2-4) + 1/(1 + ...))))))).
(End)
G.f.: G(0), where G(k) = 1 + 1/(1 - x*(8*k-9)/( x*(8*k-1) - 3/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 12 2013
Inverse binomial transform of A228568 [Bhadouria]. - R. J. Mathar, Nov 10 2013
From Peter Bala, Oct 16 2019: (Start)
4*Sum_{n >= 1} 1/(a(n) - 8/a(n)) = 1.
8*Sum_{n >= 1} (-1)^(n+1)/(a(n) + 4/a(n)) = 1.
Series acceleration formulas for sum of reciprocals:
Sum_{n >= 1} 1/a(n) = 1/4 - 8*Sum_{n >= 1} 1/(a(n)*(a(n)^2 - 8)) and
Sum_{n >= 1} (-1)^(n+1)/a(n) = 1/8 + 4*Sum_{n >= 1} (-1)^(n+1)/(a(n)*(a(n)^2 + 4)).
Sum_{n >= 1} 1/a(n) = ( (theta_3(3-2*sqrt(2)))^2 - 1 )/4 and
Sum_{n >= 1} (-1)^(n+1)/a(n) = ( 1 - (theta_3(2*sqrt(2)-3))^2 )/4, where theta_3(x) = 1 + 2*Sum_{n >= 1} x^(n^2) (see A000122). Cf. A153415 and A067902.
(End)
E.g.f.: 2*exp(3*x)*cosh(2*sqrt(2)*x). - Stefano Spezia, Oct 18 2019
a(2*n)+2 = a(n)^2. - Greg Dresden and Shraya Pal, Jun 29 2021

A103997 Square array T(M,N) read by antidiagonals: number of dimer tilings of a 2M X 2N Moebius strip.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 11, 7, 1, 1, 41, 71, 18, 1, 1, 153, 769, 539, 47, 1, 1, 571, 8449, 17753, 4271, 123, 1, 1, 2131, 93127, 603126, 434657, 34276, 322, 1, 1, 7953, 1027207, 20721019, 46069729, 10894561, 276119, 843, 1, 1, 29681, 11332097, 714790675, 4974089647, 3625549353, 275770321, 2226851, 2207, 1

Offset: 0

Ralf Stephan, Feb 26 2005

			Array begins:
  1,   1,     1,        1,          1,             1,               1,
  1,   3,     7,       18,         47,           123,             322,
  1,  11,    71,      539,       4271,         34276,          276119,
  1,  41,   769,    17753,     434657,      10894561,       275770321,
  1, 153,  8449,   603126,   46069729,    3625549353,    289625349454,
  1, 571, 93127, 20721019, 4974089647, 1234496016491, 312007855309063,
  ...

Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter and Tianyuan Xu, Sandpiles and Dominos, El. J. Comb., 22 (2015), P1.66. See Theorem 18.
W. T. Lu and F. Y. Wu, Dimer statistics on the Moebius strip and the Klein bottle, arXiv:cond-mat/9906154 [cond-mat.stat-mech], 1999.
Index entries for sequences related to dominoes

Rows include A005248, A103998.
Columns 1..7 give A001835(n+1), A334135, A334179, A334180, A334181, A334182, A334183.
Main diagonal gives A334124.
Cf. A099390, A103999, A341741, A334178, A256045, A348566.

T[M_, N_] := Product[4Sin[(4n-1)Pi/(4N)]^2 + 4Cos[m Pi/(2M+1)]^2, {n, 1, N}, {m, 1, M}];
Table[T[M - N, N] // Round, {M, 0, 9}, {N, 0, M}] // Flatten (* Jean-François Alcover, Dec 03 2018 *)

T(M, N) = Product_{m=1..M} (Product_{n=1..N} 4*sin(Pi*(4*n-1)/(4*N))^2 + 4*cos(Pi*m/(2*M + 1))^2).

For k > 0, T(n,k) = 2^n * sqrt(Resultant(U_{2*n}(x/2), T_{2*k}(i*x/2))), where T_n(x) is a Chebyshev polynomial of the first kind, U_n(x) is a Chebyshev polynomial of the second kind and i = sqrt(-1). - Seiichi Manyama, Apr 15 2020

A341741 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals downwards: number of perfect matchings in the graph C_{2n} x C_k.

Original entry on oeis.org

2, 8, 2, 14, 36, 2, 36, 50, 200, 2, 82, 272, 224, 1156, 2, 200, 722, 3108, 1058, 6728, 2, 478, 3108, 9922, 39952, 5054, 39204, 2, 1156, 10082, 90176, 155682, 537636, 24200, 228488, 2, 2786, 39952, 401998, 3113860, 2540032, 7379216, 115934, 1331716, 2

Offset: 1

Seiichi Manyama, Feb 18 2021

Dimer tilings of 2n x k toroidal grid.

			Square array begins:
  2,     8,    14,      36,       82,        200, ...
  2,    36,    50,     272,      722,       3108, ...
  2,   200,   224,    3108,     9922,      90176, ...
  2,  1156,  1058,   39952,   155682,    3113860, ...
  2,  6728,  5054,  537636,  2540032,  114557000, ...
  2, 39204, 24200, 7379216, 41934482, 4357599552, ...

Seiichi Manyama, Antidiagonals n = 1..50, flattened
P. W. Kasteleyn, The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225. See Eq. (25).
Index entries for sequences related to dominoes

Columns 1..12 give A007395, A162484(2*n), A231087, A220864(2*n), A231485, A232804(2*n), A230033, A253678(2*n), A281583, A281679(2*n), A308761, A309018(2*n).
Rows 1..6 give A162484, A220864, A232804, A253678, A281679, A309018.
T(n,2*n) gives A335586.
Cf. A341533, A341738, A341739.
Cf. A099390, A103997, A103999.

T(n,k) = A341533(n,k)/2 + A341738(n,k) + 2 * ((k+1) mod 2) * A341739(n,ceiling(k/2)).
T(n, 2k) = T(k, 2n).
If k is odd, T(n,k) = A341533(n,k) = 2*A341738(n,k).

New name from Andrey Zabolotskiy, Dec 26 2021

A067902 a(n) = 14*a(n-1) - a(n-2); a(0) = 2, a(1) = 14.

Original entry on oeis.org

2, 14, 194, 2702, 37634, 524174, 7300802, 101687054, 1416317954, 19726764302, 274758382274, 3826890587534, 53301709843202, 742397047217294, 10340256951198914, 144021200269567502, 2005956546822746114, 27939370455248878094, 389145229826661547202, 5420093847118012782734

Offset: 0

Lekraj Beedassy, May 13 2003

Solves for x in x^2 - 3*y^2 = 4. [Complete nonnegative solutions are in A003500 and A052530. - Wolfdieter Lang, Sep 05 2021]
For n>0, a(n)+2 is the number of dimer tilings of a 4 X 2n Klein bottle (cf. A103999).
This is the Lucas sequence V(14,1). In addition to the comment above: If x = a(n) then y(n) = (a(n+1) - a(n-1))/24, n >= 1. - Klaus Purath, Aug 17 2021

			G.f. = 2 + 14*x + 194*x^2 + 2702*x^3 + 37634*x^4 + 524174*x^5 + ...

G. C. Greubel, Table of n, a(n) for n = 0..850
Tanya Khovanova, Recursive Sequences
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for linear recurrences with constant coefficients, signature (14,-1).
Index entries for sequences related to Chebyshev polynomials.

Cf. A067900, A302332.
Row 2 * 2 of array A188644.
Cf. A001075, A001353, A003500, A052530.

m:=7;; a:=[2,14];; for n in [3..20] do a[n]:=2*m*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Dec 23 2019

[Floor((2+Sqrt(3))^(2*n)+(1+Sqrt(3))^(-n)): n in [0..19]]; // Vincenzo Librandi, Mar 31 2011

a := proc(n) option remember: if n=0 then RETURN(2) fi: if n=1 then RETURN(14) fi: 14*a(n-1)-a(n-2): end: for n from 0 to 30 do printf(`%d,`,a(n)) od:
seq( simplify(2*ChebyshevT(n, 7)), n=0..20); # G. C. Greubel, Dec 23 2019

a[0]=2; a[1]=14; a[n_]:= 14a[n-1] -a[n-2]; Table[a[n], {n,0,20}] (* Robert G. Wilson v, Jan 30 2004 *)
2*ChebyshevT[Range[21] -1, 7] (* G. C. Greubel, Dec 23 2019 *)

vector( 21, n, 2*polchebyshev(n-1, 1, 7) ) \\ G. C. Greubel, Dec 23 2019

[lucas_number2(n,14,1) for n in range(0,20)] # Zerinvary Lajos, Jun 26 2008

[2*chebyshev_T(n,7) for n in (0..20)] # G. C. Greubel, Dec 23 2019

G.f.: 2*(1-7*x)/(1-14*x+x^2). - N. J. A. Sloane, Nov 22 2006
a(n) = p^n + q^n, where p = 7 + 4*sqrt(3) and q = 7 - 4*sqrt(3). - Tanya Khovanova, Feb 06 2007
a(n) = 2*A011943(n+1). - R. J. Mathar, Sep 27 2014
From Peter Bala, Oct 16 2019: (Start)
Let F(x) = Product_{n >= 0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 7 - 4*sqrt(3). This sequence gives the partial denominators in the simple continued fraction expansion of 1 + F(alpha) = 2.07140228197873197080... = 2 + 1/(14 + 1/(194 + 1/(2702 + ...))). Cf. A005248.
12*Sum_{n >= 1} 1/(a(n) - 16/a(n)) = 1.
16*Sum_{n >= 1} (-1)^(n+1)/(a(n) + 12/a(n)) = 1.
Series acceleration formula for sum of reciprocals:
Sum_{n >= 1} 1/a(n) = 1/12 - 16*Sum_{n >= 1} 1/(a(n)*(a(n)^2 - 16)).
Sum_{n >= 1} 1/a(n) = ( (theta_3(7-4*sqrt(3)))^2 - 1 )/4, where theta_3(x) = 1 + 2*Sum_{n >= 1} x^(n^2) (see A000122). Cf. A153415 and A003499.
(End)
From Klaus Purath, Aug 17 2021: (Start)
a(n) = (a(n-1)*a(n-2) + 2688)/a(n-3), n >= 3.
a(n) = (a(n-1)^2 + 192)/a(n-2), n >= 2.
a(2*n) = A302332(n-1) + A302332(n), n >= 1.
a(2*n+1) = 14*A302332(n). (End)
a(n) = A003500(2*n) = S(2*n,4) - S(2*n-2, 4) = 2*T(2*n,2), for n >= 0, with Chebyshev S and T. S(n, 4) = A001353(n+1) and T(n, 2) = A001075(n). - Wolfdieter Lang, Sep 06 2021

A340557 a(n) = Product_{1<=j,k<=n} (4sin(Pi(4j-1)/(4n))^2 + 4sin(Pi(2k-1)/(2n))^2).

Original entry on oeis.org

1, 6, 196, 64152, 220581904, 7902001927776, 2930937179395968064, 11225532133258005621166464, 443461906581614469808503571611904, 180610519352999624076350648705004622628352

Offset: 0

Seiichi Manyama, Jan 11 2021

nonn

Main diagonal of A103999.

Table[Product[Product[(4*Sin[Pi*(4*j - 1)/(4*n)]^2 + 4*Sin[Pi*(2*k - 1)/(2*n)]^2), {j, 1, n}], {k, 1, n}], {n, 0, 15}] // Round (* Vaclav Kotesovec, Mar 18 2023 *)

default(realprecision, 120);
{a(n) = round(prod(j=1, n, prod(k=1, n, 4*sin((4*j-1)*Pi/(4*n))^2+4*sin((2*k-1)*Pi/(2*n))^2)))}

a(n) ~ 2^(1/8) * sqrt(1 + sqrt(2)) * exp(4*G*n^2/Pi), where G is Catalan's constant A006752. - Vaclav Kotesovec, Mar 18 2023

A351635 a(n) is the number of perfect matchings of an edge-labeled 2 X n Klein bottle grid graph, or equivalently the number of domino tilings of a 2 X n Klein bottle grid. (The twist is on the length-n side.)

Original entry on oeis.org

2, 6, 10, 16, 38, 54, 142, 196, 530, 726, 1978, 2704, 7382, 10086, 27550, 37636, 102818, 140454, 383722, 524176, 1432070, 1956246, 5344558, 7300804, 19946162, 27246966, 74440090, 101687056, 277814198, 379501254, 1036816702, 1416317956, 3869452610, 5285770566, 14440993738, 19726764304, 53894522342, 73621286646

Offset: 1

Sarah-Marie Belcastro, Feb 15 2022

Output of Lu and Wu's formula for the number of perfect matchings of an m X n Klein bottle grid specializes to this sequence for m=2 and the twist on the length-n side.

			a(1) = 2 because this is the number of perfect matchings of a 2 X 1 Klein bottle grid graph (one for each choice of the two non-loop edges).

Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
W. T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, 293 (2002), 235-246.
Index entries for linear recurrences with constant coefficients, signature (0,5,0,-5,0,1).

Cf. A000129, A005248, A001835, A003499, A068397, A103999, A162484, A162483.

RecurrenceTable[{a[n] ==
   a[n - 1] + a[n - 2] + Mod[n, 2] a[n - 1] - 4 Mod[n, 2], a[1] == 2,
  a[2] == 6}, a, {n, 1, 50}]

a(n) = a(n-1) + a(n-2) + (n mod 2)*a(n-1) - 4*(n mod 2).
From Stefano Spezia, Feb 15 2022: (Start)
G.f.: 2*x*(1 + 3*x - 7*x^3 - x^4 + 2*x^5)/(1 - 5*x^2 + 5*x^4 - x^6).
a(n) = 5*a(n-2) - 5*a(n-4) + a(n-6) for n > 6. (End)

cp's OEIS Frontend

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A003499 a(n) = 6*a(n-1) - a(n-2), with a(0) = 2, a(1) = 6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A103997 Square array T(M,N) read by antidiagonals: number of dimer tilings of a 2*M X 2*N Moebius strip.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A341741 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals downwards: number of perfect matchings in the graph C_{2n} x C_k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A067902 a(n) = 14*a(n-1) - a(n-2); a(0) = 2, a(1) = 14.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A103997 Square array T(M,N) read by antidiagonals: number of dimer tilings of a 2M X 2N Moebius strip.

A340557 a(n) = Product_{1<=j,k<=n} (4sin(Pi(4j-1)/(4n))^2 + 4sin(Pi(2k-1)/(2n))^2).