|
%I #81 Sep 08 2022 08:44:32
%S 1,8,95,1183,14824,185921,2332097,29253160,366944287,4602858719,
%T 57737128904,724240365697,9084693297025,113956161827912,
%U 1429438110270431,17930520634652959,224916047725262248,2821291671062267585,35389589910135145793,443918325373278904936
%N Number of perfect matchings (or domino tilings) in P_5 X P_2n.
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%D R. P. Stanley, Enumerative Combinatorics I, p. 292.
%H Alois P. Heinz, <a href="/A003775/b003775.txt">Table of n, a(n) for n = 0..300</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.pdf">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 Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H David Klarner and Jordan Pollack, <a href="http://dx.doi.org/10.1016/0012-365X(80)90098-9">Domino tilings of rectangles with fixed width</a>, Disc. Math. 32 (1980) 45-52.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 4.
%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 Thotsaporn ”Aek” Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/57-5/thanatipanonda.pdf">Statistics of Domino Tilings on a Rectangular Board</a>, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (15,-32,15,-1).
%F If b(n) denotes the number of perfect matchings (or domino tilings) in P_5 X P_n we have:
%F b(1) = 0,
%F b(2) = 8,
%F b(3) = 0,
%F b(4) = 95,
%F b(5) = 0,
%F b(6) = 1183,
%F b(7) = 0,
%F b(8) = 14824 and
%F b(n) = 15b(n-2) - 32b(n-4) + 15b(n-6) - b(n-8).
%F G.f.: (1-x)*(1 - 6*x + x^2)/(1 - 15*x + 32*x^2 - 15*x^3 + x^4).
%F Let M be the 4 X 4 matrix |1 0 2 8 | 0 1 0 2 | 2 1 5 21| 1 1 1 8 |; then a(n) = M^n(4, 4). - _Philippe Deléham_, Aug 08 2003
%F Limit_{n -> infinity} a(n)/a(n-1) = (3 + sqrt(5))*(5 + sqrt(21))/4 = 12.54375443458... - _Philippe Deléham_, Jun 13 2005
%F a(n) = ((35 + 7*sqrt(5) + 5*sqrt(21) + sqrt(105))*((3+sqrt(5))*(5+sqrt(21))/4)^n + (35 - 7*sqrt(5) + 5*sqrt(21) - sqrt(105))*((3-sqrt(5))*(5+sqrt(21))/4)^n + (35 + 7*sqrt(5) - 5*sqrt(21) - sqrt(105))*((3+sqrt(5))*(5-sqrt(21))/4)^n + (35 - 7*sqrt(5) - 5*sqrt(21) + sqrt(105))*((3-sqrt(5))*(5-sqrt(21))/4)^n)/140. - _Tim Monahan_, Aug 13 2011
%p a:= n-> (<<15|-32|15|-1>, <1|0|0|0>, <0|1|0|0>, <0|0|1|0>>^n. <<8, 1, 1, 8>>)[2, 1]: seq(a(n), n=0..20); # _Alois P. Heinz_, Sep 24 2011
%t a = 3; b = 5; c = 7; d = a*c; e = b*c; g = a*b*c; f[n_] := Simplify[((e + c*Sqrt[b] + b*Sqrt[d] + Sqrt[g])*((a + Sqrt[b])*(b + Sqrt[d])/4)^n + (e - c*Sqrt[b] + b*Sqrt[d] - Sqrt[g])*((a - Sqrt[b])*(b + Sqrt[d])/4)^n + (e + c*Sqrt[b] - b*Sqrt[d] - Sqrt[g])*((a + Sqrt[b])*(b - Sqrt[d])/4)^n + (e - c*Sqrt[b] - 5*Sqrt[d] + Sqrt[g])*((a - Sqrt[b])*(b - Sqrt[d])/4)^n)/ 140]; Array[f, 17, 0] (* _Robert G. Wilson v_, Aug 13 2011 *)
%t a[n_] := (MatrixPower[{{15, -32, 15, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}, n].{8, 1, 1, 8})[[2]]; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jan 31 2016, after _Alois P. Heinz_ *)
%t a[0] = 1; a[n_] := Product[2(2+Cos[j Pi/3]+Cos[2k Pi/(2n+1)]), {k, 1, n}, {j, 1, 2}] // Round;
%t Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Aug 20 2018 *)
%t LinearRecurrence[{15, -32, 15, -1}, {1, 8, 95, 1183}, 20] (* _Vincenzo Librandi_, Aug 20 2018 *)
%o (Magma) I:=[1,8,95,1183]; [n le 4 select I[n] else 15*Self(n-1)-32*Self(n-2)+15*Self(n-3)-Self(n-4): n in [1..30]]; // _Vincenzo Librandi_, Aug 20 2018
%Y Row 5 of array A099390.
%Y Bisection of A189003.
%K nonn
%O 0,2
%A _Frans J. Faase_
%E Recurrence from Faase's web page added by _N. J. A. Sloane_, Feb 03 2009
|
