login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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

%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 INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&amp;service=Search&amp;searchTerms=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 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 to sequences with 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.]

%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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 22 16:49 EST 2014. Contains 252364 sequences.