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

 

Logo

The submissions stack has been unacceptably high for several months now. Please voluntarily restrict your submissions and please help with the editing. (We don't want to have to impose further limits.)

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

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

%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 August 29 03:21 EDT 2015. Contains 261184 sequences.