This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A004253 a(n) = 5*a(n-1) - a(n-2). (Formerly M3553) 27

%I M3553

%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).

%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(2n-k,k)j^(n-k)}=(-1)^n*U(2n,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

%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 Hamilton cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%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 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, 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="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 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.: (1 - x) / (1 - 5*x + x^2).

%F For n>1 a(n)=b(n)+b(n-1) with b(n) as in A005386. - _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

%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

%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

%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

%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

%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

%p A004253:=-(-1+z)/(1-5*z+z**2); [_Simon Plouffe_ in his 1992 dissertation.]

%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 xrange(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^99)) \\ _Charles R Greathouse IV_, Jul 01 2013

%Y Cf. A030221, A003501, A004254.

%Y Partial sums are in A004254.

%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

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

Last modified February 20 01:26 EST 2018. Contains 299357 sequences. (Running on oeis4.)