The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A004253 a(n) = 5*a(n-1) - a(n-2), 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*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, 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 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 MAPLE a:=1: a:=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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 6 12:35 EDT 2022. Contains 357264 sequences. (Running on oeis4.)