

A004253


a(n) = 5*a(n1)  a(n2), with a(1)=1, a(2)=4.
(Formerly M3553)


31



1, 4, 19, 91, 436, 2089, 10009, 47956, 229771, 1100899, 5274724, 25272721, 121088881, 580171684, 2779769539, 13318676011, 63813610516, 305749376569, 1464933272329, 7018916985076, 33629651653051, 161129341280179
(list;
graph;
refs;
listen;
history;
text;
internal format)



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*nk, k)*j^(nk) = (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 01avoiding 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 (2n2) X (2n2) 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
Rightshifted Binomial Transform of the leftshifted 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(n1, 5), y(n) = x(n1)], for n =oo..+oo, with the Chebyshev Spolynomials (A049310), with S(1, 0) = 0, and S(n, x) =  S(n2, 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(n1), for n >= 1, in terms of Spolynomials 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(n1) = S(n1, 5)  S(n2, 5) and Y(n) = (x(n)  x(n1))/3 = S(n1, 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(n1)^2 / a(n2)), 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 466467 (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), 129154.
F. A. Haight, On a generalization of Pythagoras' theorem, pp. 7377 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), 129154.
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. 76114. 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. 7377 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 3Spheres That Bound Rational Homology 4Balls, arXiv:2208.14850 [math.GT], 2022.
Per Hakan Lundow, Computation of matching polynomials and the number of 1factors 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 mpermutations,(m+1)ary trees, and mparking 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 Nnumbers, not their Anumbers.
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) 311325.
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(n1).  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^(ni)*binomial(2*ni, 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)*((5sqrt(21))/2)^n)/2/sqrt(21).  Seiichi Kirikami, Sep 06 2011
a(n) = S(n1, 5)  S(n2, 5) = (1)^n*S(2*n, i*sqrt(3)), n >= 1, with the Chebyshev S polynomials (A049310), and S(n1, 5) = A004254(n), for n >= 0. See a Paul Barry formula (offset corrected).  Wolfdieter Lang, Oct 15 2020


MAPLE

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


MATHEMATICA

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


PROG

(Sage) [lucas_number1(n, 5, 1)lucas_number1(n1, 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(n1)Self(n2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
(PARI) Vec((1x)/(15*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[n1]a[n2]; 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



