|
| |
|
|
A004253
|
|
a(n) = 5*a(n-1) - a(n-2).
(Formerly M3553)
|
|
18
| |
|
|
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; 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. 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. [From Milan R. Janjic (agnus(AT)blic.net), 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. [From John M. Campbell, Jul 08 2011]
|
|
|
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.
P. H. Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research report, No 12, 1996, Department of Math., Umea University, Sweden.
F. M. van Lamoen, Square wreaths around hexagons, Forum Geometricorum, 6 (2006) 311-325.
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
F. Faase, Counting Hamilton cycles in product graphs
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 422
Tanya Khovanova, Recursive Sequences
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}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, Article in Forum Geometricorum
Index entries for sequences related to dominoes
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
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). - R. 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, Sept 6 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 (zerinvarylajos(AT)yahoo.com), Jul 26 2006
A004253:=-(-1+z)/(1-5*z+z**2); [S. Plouffe in his 1992 dissertation.]
|
|
|
PROG
| (Sage) [lucas_number1(n, 5, 1)-lucas_number1(n-1, 5, 1) for n in xrange(1, 23)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 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
|
|
|
CROSSREFS
| Cf. A030221, A003501.
Partial sums are in A004254.
Row 5 of array A094954.
Cf. A004254.
Sequence in context: A181880 A010907 A087449 * A151253 A121179 A131552
Adjacent sequences: A004250 A004251 A004252 * A004254 A004255 A004256
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frans Faase (Frans_LiXia(AT)wxs.nl), Per Hakan Lundow (phl(AT)theophys.kth.se)
|
|
|
EXTENSIONS
| Additional comments from James Sellers and N. J. A. Sloane (njas(AT)research.att.com), May 03, 2002
More terms from Ray Chandler (rayjchandler(AT)sbcglobal.net), Nov 17 2003
|
| |
|
|
