cp's OEIS Frontend

A318267 a(n) is the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that all but two such pairs are joined by an edge.

%I A318267 #46 Mar 18 2020 10:58:11
%S A318267 0,0,1,8,39,138,414,1104,2715,6282,13875,29540,61060,123192,243589,
%T A318267 473540,907335,1716974,3214066,5959704,10958687,20001526,36264579,
%U A318267 65359752,117165096,209008464,371190217,656540768,1156924167,2031676818,3556517478
%N A318267 a(n) is the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that all but two such pairs are joined by an edge.
%C A318267 The generating function has been obtained using the calculus of the rook polynomial associated with A046741.
%C A318267 The case of all but one pair joined by an edge is given by A178523(n-1). The case of all pairs joined by an edge is given by A000045(n+1), i.e., the number of perfect matchings in the ladder graph.
%C A318267 This is also the number of "(n-2)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - _Donovan Young_, Oct 23 2018
%H A318267 Muniru A Asiru, <a href="/A318267/b318267.txt">Table of n, a(n) for n = 0..2000</a>
%H A318267 D. Young, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Young/young2.html">The Number of Domino Matchings in the Game of Memory</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
%H A318267 Donovan Young, <a href="https://arxiv.org/abs/1905.13165">Generating Functions for Domino Matchings in the 2 * k Game of Memory</a>, arXiv:1905.13165 [math.CO], 2019. Also in <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">J. Int. Seq.</a>, Vol. 22 (2019), Article 19.8.7.
%H A318267 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,-2,10,-2,-5,1,1).
%F A318267 G.f.: x^2*(1 + 3*x + 6*x^2 + x^3 + 3*x^4)/((1 - x)^2*(1 - x - x^2)^3).
%e A318267 Consider the case n=3. Let the 2 X 3 grid have vertex set {O(0, 0), A(1, 0), B(2, 0), C(2, 1), D(1, 1), E(0, 1)} and edge set {OA, AB, ED, DC, OE, AD, BC}.
%e A318267 If DC represents the one pair which is joined by an edge, the remaining pairs must be placed on AE and OB; there are three other such configurations where the joined pair is placed instead on ED, OA, or AB. Our count is now at 4. If the joined pair is placed on OE then the remaining pairs must be placed on BD and AC; there is one other such configuration where the joined pair is placed on BC, bringing the count to 6. Finally, let the joined pair be placed on AD, then the remaining pairs may be placed either on OB, EC or on OC, EB, and thus we have a(3) = 8.
%p A318267 seq(coeff(series(x^2*(1+3*x+6*x^2+x^3+3*x^4)/((1-x)^2*(1-x-x^2)^3),x,n+1), x, n), n = 0 .. 30); # _Muniru A Asiru_, Oct 23 2018
%t A318267 CoefficientList[Normal[Series[x^2(1 + 3*x + 6*x^2 + x^3 + 3*x^4)/(1 - x)^2/(1 - x - x^2)^3, {x, 0, 30}]], x]
%o A318267 (GAP) a:=[0, 0, 1, 8, 39, 138, 414, 1104];;  for n in [9..35] do a[n]:=5*a[n-1]-7*a[n-2]-2*a[n-3]+10*a[n-4]-2*a[n-5]-5*a[n-6]+a[n-7]+a[n-8]; od; a; # _Muniru A Asiru_, Oct 23 2018
%Y A318267 Cf. A000045, A046741, A178523, A318243, A318244, A318268, A318269, A318270.
%K A318267 nonn,easy
%O A318267 0,4
%A A318267 _Donovan Young_, Aug 22 2018