

A004253


a(n) = 5*a(n1)  a(n2).
(Formerly M3553)


27



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(2nk,k)j^(nk)}=(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 01avoiding 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 (2n2)X(2n2) 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
Rightshifted Binomial Transform of the leftshifted 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), 129154.
Fink, Alex, Richard Guy, and Mark Krusemeyer. "Partitions with parts occurring at most thrice." Contributions to Discrete Mathematics 3.2 (2008), 76114. See Section 13.
F. A. Haight, On a generalization of Pythagoras' theorem, pp. 7377 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), 129154.
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. 7377 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 1factors 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 mpermutations,(m+1)ary trees, and mparking 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.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their Nnumbers, not their Anumbers.
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) 311325.
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(n1) 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^(ni)*binomial(2*ni, 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)*((5sqrt(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[n1]a[n2] od: seq(a[n], n=1..22); # Zerinvary Lajos, Jul 26 2006
A004253:=(1+z)/(15*z+z**2); [Simon Plouffe in his 1992 dissertation.]


MATHEMATICA

LinearRecurrence[{5, 1}, {1, 4}, 22] (* JeanFrançois Alcover, Sep 27 2017 *)


PROG

(Sage) [lucas_number1(n, 5, 1)lucas_number1(n1, 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(n1)Self(n2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
(PARI) Vec((1x)/(15*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,changed


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



