|
%I M3553 #173 Feb 13 2024 08:14:25
%S 1,4,19,91,436,2089,10009,47956,229771,1100899,5274724,25272721,
%T 121088881,580171684,2779769539,13318676011,63813610516,305749376569,
%U 1464933272329,7018916985076,33629651653051,161129341280179
%N a(n) = 5*a(n-1) - a(n-2), with a(1)=1, a(2)=4.
%C Number of domino tilings in K_3 X P_2n (or in S_4 X P_2n).
%C Number of perfect matchings in graph C_{3} X P_{2n}.
%C Number of perfect matchings in S_4 X P_2n.
%C 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
%C a(n) = L(n,5), where L is defined as in A108299; see also A030221 for L(n,-5). - _Reinhard Zumkeller_, Jun 01 2005
%C 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
%C (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
%C 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
%C 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
%C Right-shifted Binomial Transform of the left-shifted A030195. - _R. J. Mathar_, Oct 15 2012
%C Values of x (or y) in the solutions to x^2 - 5xy + y^2 + 3 = 0. - _Colin Barker_, Feb 04 2014
%C From _Wolfdieter Lang_, Oct 15 2020: (Start)
%C 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.
%C 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.
%C See the formula for a(n) = x(n-1), for n >= 1, in terms of S-polynomials below.
%C 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)
%C From _Wolfdieter Lang_, Feb 08 2021: (Start)
%C 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.
%C 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)
%C 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
%D 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).
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A004253/b004253.txt">Table of n, a(n) for n = 1..200</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H Alex Fink, Richard K. Guy, and Mark Krusemeyer, <a href="https://doi.org/10.11575/cdm.v3i2.61940">Partitions with parts occurring at most thrice</a>, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.
%H Frank A. Haight, <a href="/A004253/a004253_1.pdf">Letter to N. J. A. Sloane, Sep 06 1976</a>
%H Frank A. Haight, <a href="/A004253/a004253.pdf">On a generalization of Pythagoras' theorem</a>, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971. [Annotated scanned copy]
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=422">Encyclopedia of Combinatorial Structures 422</a>
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H Lisa Lokteva, <a href="https://arxiv.org/abs/2208.14850">Constructing Rational Homology 3-Spheres That Bound Rational Homology 4-Balls</a>, arXiv:2208.14850 [math.GT], 2022.
%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors.pdf">Computation of matching polynomials and the number of 1-factors in polygraphs</a>, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.
%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962, 2014
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.
%H James A. Sellers, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Sellers/sellers4.html">Domino Tilings and Products of Fibonacci and Pell Numbers</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2
%H F. M. van Lamoen, <a href="http://forumgeom.fau.edu/FG2006volume6/FG200637index.html">Square wreaths around hexagons</a>, Forum Geometricorum, 6 (2006) 311-325.
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-1).
%F G.f.: x*(1 - x) / (1 - 5*x + x^2). _Simon Plouffe_ in his 1992 dissertation.[offset 0]
%F For n>1, a(n) = A005386(n) + A005386(n-1). - _Floor van Lamoen_, Dec 13 2006
%F 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]
%F 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]
%F For n>0, a(n)*a(n+3) = 15 + a(n+1)*a(n+2). - _Ralf Stephan_, May 29 2004
%F a(n) = Sum_{k=0..n} binomial(n+k, 2k)*3^k. - _Paul Barry_, Jul 26 2004[offset 0]
%F 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]
%F [a(n), A004254(n)] = the 2 X 2 matrix [1,3; 1,4]^n * [1,0]. - _Gary W. Adamson_, Mar 19 2008
%F 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
%F 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
%F From _Peter Bala_, Feb 10 2024: (Start)
%F a(n) = a(1-n).
%F a(n) = A004254(n) + A004254(1-n).
%F 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.
%F a(n)^2 + a(n+1)^2 - 5*a(n)*a(n+1) = - 3.
%F 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)
%p 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
%t LinearRecurrence[{5, -1}, {1, 4}, 22] (* _Jean-François Alcover_, Sep 27 2017 *)
%o (Sage) [lucas_number1(n,5,1)-lucas_number1(n-1,5,1) for n in range(1, 23)] # _Zerinvary Lajos_, Nov 10 2009
%o (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
%o (PARI) Vec((1-x)/(1-5*x+x^2)+O(x^30)) \\ _Charles R Greathouse IV_, Jul 01 2013
%o (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
%Y Cf. A003501, A004254, A030221, A049310, A004254 (partial sums), A290902 (first differences).
%Y Row 5 of array A094954.
%Y Cf. similar sequences listed in A238379.
%K nonn,easy
%O 1,2
%A _Frans J. Faase_, _Per H. Lundow_
%E Additional comments from _James A. Sellers_ and _N. J. A. Sloane_, May 03 2002
%E More terms from _Ray Chandler_, Nov 17 2003
| 