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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004253 a(n) = 5*a(n-1) - a(n-2).
(Formerly M3553)
26
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(2n-k,k)j^(n-k)}=(-1)^n*U(2n,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

REFERENCES

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, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

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

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, 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.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

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 sequences related to dominoes

Index entries for linear recurrences with constant coefficients, signature (5,-1)

FORMULA

G.f.: (1 - x) / (1 - 5*x + x^2).

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

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

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

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

[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

MAPLE

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

A004253:=-(-1+z)/(1-5*z+z**2); [Simon Plouffe in his 1992 dissertation.]

PROG

(Sage) [lucas_number1(n, 5, 1)-lucas_number1(n-1, 5, 1) for n in xrange(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^99)) \\ Charles R Greathouse IV, Jul 01 2013

CROSSREFS

Cf. A030221, A003501, A004254.

Partial sums are in A004254.

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

Frans J. Faase, Per H. Lundow

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 20 16:09 EDT 2017. Contains 292276 sequences.