login
Number of matchings in graph P_{3} X P_{n}.
5

%I #42 Sep 08 2022 08:44:51

%S 1,3,22,131,823,5096,31687,196785,1222550,7594361,47177097,293066688,

%T 1820552297,11309395995,70254767718,436427542283,2711118571311,

%U 16841658983944,104621568809247,649916534985369,4037327172325542

%N Number of matchings in graph P_{3} X P_{n}.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 50, 999.

%D Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

%H G. C. Greubel, <a href="/A033506/b033506.txt">Table of n, a(n) for n = 0..1000</a>

%H Svenja Huntemann, Neil A. McKay, <a href="https://arxiv.org/abs/1909.12419">Counting Domineering Positions</a>, arXiv:1909.12419 [math.CO], 2019.

%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/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.

%H R. C. Read, <a href="https://doi.org/10.1007/BF02193034">The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions</a>, Aequationes Mathematicae, 24 (1982), 47-65.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,14,0,-10,0,1).

%F G.f.: (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)). - _Sergey Perepechko_, Apr 19 2013

%p seq(coeff(series((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5 )), x, n+1), x, n), n = 0..30); # _G. C. Greubel_, Oct 26 2019

%t CoefficientList[Series[(1-2x-x^2)(1+x-x^2)/((1+x)(1-5x-9x^2+9x^3+x^4-x^5) ), {x, 0, 30}], x] (* _Harvey P. Dale_, Dec 05 2014 *)

%t LinearRecurrence[{4, 14, 0, -10, 0, 1}, {1, 3, 22, 131, 823, 5096}, 30] (* _Harvey P. Dale_, Dec 05 2014 *)

%t Table[RootSum[-1 +# +9#^2 -9#^3 -5#^4 +#^5 &, 1436541#^n + 3941068#^(n+1) -6086452#^(n+2) -2800519#^(n+3) +591744#^(n+4) &]/10204570 -(-1)^n/5, {n, 20}] (* _Eric W. Weisstein_, Oct 02 2017 *)

%o (PARI) my(x='x+O('x^30)); Vec((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2 +9*x^3+x^4-x^5))) \\ _G. C. Greubel_, Oct 26 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) )); // _G. C. Greubel_, Oct 26 2019

%o (Sage)

%o def A033506_list(prec):

%o P.<x> = PowerSeriesRing(ZZ, prec)

%o return P((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) ).list()

%o A033506_list(30) # _G. C. Greubel_, Oct 26 2019

%o (GAP) a:=[1,3,22,131,823,5096];; for n in [7..30] do a[n]:=4*a[n-1] +14*a[n-2]-10*a[n-4]+a[n-6]; od; a; # _G. C. Greubel_, Oct 26 2019

%Y Column 3 of triangle A210662. Row sums of A100245.

%Y Cf. A030186, A033507, A033508, A033509, A033510, A033511.

%K nonn

%O 0,2

%A _Per H. Lundow_