|
%I #44 Sep 08 2022 08:44:51
%S 1,5,71,823,10012,120465,1453535,17525619,211351945,2548684656,
%T 30734932553,370635224561,4469527322891,53898461609719,
%U 649966808093412,7838012982224913,94519361817920403,1139818186429110279,13745178487929574337,165754445655292452448
%N Number of matchings in graph P_{4} X P_{n}.
%D H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Phys., 26(1985), 157-167.
%H Alois P. Heinz, <a href="/A033507/b033507.txt">Table of n, a(n) for n = 0..500</a>
%H David Friedhelm Kind, <a href="https://doi.org/10.13140/RG.2.2.11182.54086">The Gunport Problem: An Evolutionary Approach</a>, De Montfort University (Leicester, UK, 2020).
%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 <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (9,41,-41,-111,91,29,-23,-1,1).
%F From _Sergey Perepechko_, Apr 24 2013: (Start)
%F a(n) = 9*a(n-1) +41*a(n-2) -41*a(n-3) -111*a(n-4) +91*a(n-5) +29*a(n-6) -23*a(n-7) -a(n-8) +a(n-9).
%F G.f.: (1-x) * (1 -3*x -18*x^2 +2*x^3 +12*x^4 +x^5 -x^6) / (1 -9*x -41*x^2 +41*x^3 +111*x^4 -91*x^5 -29*x^6 +23*x^7 +x^8 -x^9). (End)
%e a(1) = 5: the graph is
%e . o-o-o-o
%e and the five matchings are
%e . o o o o
%e . o-o o o
%e . o o-o o
%e . o o o-o
%e . o-o o-o
%p a:=array(0..20,[1, 5, 71, 823, 10012, 120465, 1453535, 17525619, 211351945]):
%p for j from 9 to 20 do
%p a[j]:=9*a[j-1]+41*a[j-2]-41*a[j-3]-111*a[j-4]+91*a[j-5]+
%p 29*a[j-6]-23*a[j-7]-a[j-8]+a[j-9]
%p od:
%p convert(a,list);
%p # _Sergey Perepechko_, Apr 24 2013
%t LinearRecurrence[{9,41,-41,-111,91,29,-23,-1,1},{1,5,71,823,10012,120465, 1453535,17525619,211351945},30] (* _Harvey P. Dale_, Mar 27 2015 *)
%o (PARI) my(x='x+O('x^30)); Vec((1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9)) \\ _G. C. Greubel_, Oct 26 2019
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9) )); // _G. C. Greubel_, Oct 26 2019
%o (Sage)
%o def A033507_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( (1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9) ).list()
%o A033507_list(30) # _G. C. Greubel_, Oct 26 2019
%o (GAP) a:=[1,5,71,823,10012,120465, 1453535,17525619,211351945];; for n in [10..30] do a[n]:=9*a[n-1]+41*a[n-2]-41*a[n-3]-111*a[n-4]+91*a[n-5] +29*a[n-6]-23*a[n-7]-a[n-8]+a[n-9]; od; a; # _G. C. Greubel_, Oct 26 2019
%Y Column 4 of triangle A210662. Row sums of A100265.
%Y For perfect matchings see A005178.
%Y Cf. A033508-A033511.
%Y Bisection (even part) gives A260034.
%K nonn
%O 0,2
%A _Per H. Lundow_
%E Edited by _N. J. A. Sloane_, Nov 15 2009
|
