A004253 a(n) = 5*a(n-1) - a(n-2), with a(1)=1, a(2)=4. (Formerly M3553)

1, 4, 19, 91, 436, 2089, 10009, 47956, 229771, 1100899, 5274724, 25272721, 121088881, 580171684, 2779769539, 13318676011, 63813610516, 305749376569, 1464933272329, 7018916985076, 33629651653051, 161129341280179

Offset

1,2

Comments

Number of domino tilings in K_3 X P_2n (or in S_4 X P_2n).

Number of perfect matchings in graph C_{3} X P_{2n}.

Number of perfect matchings in S_4 X P_2n.

In general, Sum_{k=0..n} binomial(2*n-k, k)*j^(n-k) = (-1)^n * U(2*n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005

a(n) = L(n,5), where L is defined as in A108299; see also A030221 for L(n,-5). - Reinhard Zumkeller, Jun 01 2005

Number of 01-avoiding words of length n on alphabet {0,1,2,3,4} which do not end in 0 (e.g., at n=2, we have 02, 03, 04, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44). - Tanya Khovanova, Jan 10 2007

(sqrt(21)+5))/2 = 4.7912878... = exp(arccosh(5/2)) = 4 + 3/4 + 3/(4*19) + 3/(19*91) + 3/(91*436) + ... - Gary W. Adamson, Dec 18 2007

a(n+1) is the number of compositions of n when there are 4 types of 1 and 3 types of other natural numbers. - Milan Janjic, Aug 13 2010

For n >= 2, a(n) equals the permanent of the (2n-2) X (2n-2) tridiagonal matrix with sqrt(3)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011

Right-shifted Binomial Transform of the left-shifted A030195. - R. J. Mathar, Oct 15 2012

Values of x (or y) in the solutions to x^2 - 5xy + y^2 + 3 = 0. - Colin Barker, Feb 04 2014

From Wolfdieter Lang, Oct 15 2020: (Start)

All positive solutions of the Diophantine equation x^2 + y^2 - 5*x*y = -3 (see the preceding comment) are given by [x(n) = S(n, 5) - S(n-1, 5), y(n) = x(n-1)], for n =-oo..+oo, with the Chebyshev S-polynomials (A049310), with S(-1, 0) = 0, and S(-|n|, x) = - S(|n|-2, x), for |n| >= 2.

This binary indefinite quadratic form has discriminant D = +21. There is only this family representing -3 properly with x and y positive, and there are no improper solutions.

See the formula for a(n) = x(n-1), for n >= 1, in terms of S-polynomials below.

This comment is inspired by a paper by Robert K. Moniot (private communication). See his Oct 04 2020 comment in A027941 related to the case of x^2 + y^2 - 3*x*y = -1 (special Markov solutions). (End)

From Wolfdieter Lang, Feb 08 2021: (Start)

All proper and improper solutions of the generalized Pell equation X^2 - 21*Y^2 = +4 are given, up to a combined sign change in X and Y, in terms of x(n) = a(n+1) from the preceding comment by X(n) = x(n) + x(n-1) = S(n-1, 5) - S(n-2, 5) and Y(n) = (x(n) - x(n-1))/3 = S(n-1, 5), for all integer numbers n. For positive integers X(n) = A003501(n) and Y(n) = A004254(n). X(-n) = X(n) and Y(-n) = - Y(n), for n >= 1.

The two conjugated proper families of solutions are given by [X(3*n+1), Y(3*n+1)] and [X(3*n+2), Y(3*n+2)], and the one improper family by [X(3*n), Y(3*n)], for all integer n. This follows from the mentioned paper by Robert K. Moniot. (End)

Equivalent definition: a(n) = ceiling(a(n-1)^2 / a(n-2)), with a(1)=1, a(2)=4, a(3)=19. The problem for USA Olympiad (see Andreescu and Gelca reference) asks to prove that a(n)-1 is always a multiple of 3. - Bernard Schott, Apr 13 2022

References

Titu Andreescu and Rǎzvan Gelca, Putnam and Beyond, New York, Springer, 2007, problem 311, pp. 104 and 466-467 (proposed for the USA Mathematical Olympiad by G. Heuer).

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

F. A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971.

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

Links

T. D. Noe, Table of n, a(n) for n = 1..200

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.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.

Frank A. Haight, Letter to N. J. A. Sloane, Sep 06 1976

Frank A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971. [Annotated scanned copy]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 422

Tanya Khovanova, Recursive Sequences

Lisa Lokteva, Constructing Rational Homology 3-Spheres That Bound Rational Homology 4-Balls, arXiv:2208.14850 [math.GT], 2022.

Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.

Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014

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

John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.

James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2

F. M. van Lamoen, Square wreaths around hexagons, Forum Geometricorum, 6 (2006) 311-325.

Index entries for sequences related to dominoes

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

Formula

G.f.: x*(1 - x) / (1 - 5*x + x^2). Simon Plouffe in his 1992 dissertation.[offset 0]

For n>1, a(n) = A005386(n) + A005386(n-1). - Floor van Lamoen, Dec 13 2006

a(n) ~ (1/2 + 1/14*sqrt(21))*(1/2*(5 + sqrt(21)))^n. - Joe Keane (jgk(AT)jgk.org), May 16 2002[offset 0]

Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i), then q(n, 3)=a(n). - Benoit Cloitre, Nov 10 2002 [offset 0]

For n>0, a(n)*a(n+3) = 15 + a(n+1)*a(n+2). - Ralf Stephan, May 29 2004

a(n) = Sum_{k=0..n} binomial(n+k, 2k)*3^k. - Paul Barry, Jul 26 2004[offset 0]

a(n) = (-1)^n*U(2n, i*sqrt(3)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005[offset 0]

[a(n), A004254(n)] = the 2 X 2 matrix [1,3; 1,4]^n * [1,0]. - Gary W. Adamson, Mar 19 2008

a(n) = ((sqrt(21)-3)*((5+sqrt(21))/2)^n + (sqrt(21)+3)*((5-sqrt(21))/2)^n)/2/sqrt(21). - Seiichi Kirikami, Sep 06 2011

a(n) = S(n-1, 5) - S(n-2, 5) = (-1)^n*S(2*n, i*sqrt(3)), n >= 1, with the Chebyshev S polynomials (A049310), and S(n-1, 5) = A004254(n), for n >= 0. See a Paul Barry formula (offset corrected). - Wolfdieter Lang, Oct 15 2020

From Peter Bala, Feb 10 2024: (Start)

a(n) = a(1-n).

a(n) = A004254(n) + A004254(1-n).

For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 3*A004254(j)*A004254(k). The case j = 1, k = 2 is given above.

a(n)^2 + a(n+1)^2 - 5*a(n)*a(n+1) = - 3.

More generally, a(n)^2 + a(n+k)^2 - (A004254(k+1) - A004254(k-1))*a(n)*a(n+k) = -3*A004254(k)^2. (End)

Maple

a[0]:=1: a[1]:=1: for n from 2 to 26 do a[n]:=5*a[n-1]-a[n-2] od: seq(a[n], n=1..22); # Zerinvary Lajos, Jul 26 2006

Mathematica

LinearRecurrence[{5, -1}, {1, 4}, 22] (* Jean-François Alcover, Sep 27 2017 *)

Prog

(Sage) [lucas_number1(n, 5, 1)-lucas_number1(n-1, 5, 1) for n in range(1, 23)] # Zerinvary Lajos, Nov 10 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 4 else 5*Self(n-1)-Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
(PARI) Vec((1-x)/(1-5*x+x^2)+O(x^30)) \\ Charles R Greathouse IV, Jul 01 2013
(GAP) a:=[1, 4];; for n in [3..30] do a[n]:=5*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Oct 23 2019

Crossrefs

Cf. A003501, A004254, A030221, A049310, A004254 (partial sums), A290902 (first differences).

Row 5 of array A094954.

Cf. similar sequences listed in A238379.

Sequence in context: A010907 A229242 A087449 * A218988 A151253 A121179

Adjacent sequences: A004250 A004251 A004252 * A004254 A004255 A004256

Keyword

nonn,easy

Author

Frans J. Faase, Per H. Lundow

Extensions

Additional comments from James A. Sellers and N. J. A. Sloane, May 03 2002

More terms from Ray Chandler, Nov 17 2003

Status

approved