login
Triangle read by rows giving the sum of the number of k-matchings of the graphs obtained by deleting one edge and its two vertices from the ladder graph L_n = P_2 X P_n in all possible ways.
7

%I #33 Mar 18 2020 11:07:17

%S 1,4,4,7,22,9,10,58,78,20,13,112,282,224,40,16,184,702,1052,570,78,19,

%T 274,1419,3260,3335,1338,147,22,382,2514,7928,12520,9462,2968,272,25,

%U 508,4068,16460,35955,42108,24766,6312,495,28,652,6162,30584,86330,140586,128352,60976,12996,890,31,814,8877,52352

%N Triangle read by rows giving the sum of the number of k-matchings of the graphs obtained by deleting one edge and its two vertices from the ladder graph L_n = P_2 X P_n in all possible ways.

%C T(n,k) is useful for computing the number of configurations of n indistinguishable pairs placed on the vertices of P_2 X P_n such that only one such pair is joined by an edge. The g.f. given below can be proven using the calculus of the rook polynomial associated with A046741.

%H 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 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.

%F G.f.: (1 + 2*t*z + 2*z/(1-t*z)^2)*(1-t*z)^2/(1 - z - 2*t*z - t*z^2 + t^3*z^3)^2.

%e The first few rows of T(n,k) are

%e 1;

%e 4, 4;

%e 7, 22, 9;

%e 10, 58, 78, 20;

%e 13, 112, 282, 224, 40;

%e For n = 2, the four ways of deleting an edge and its vertices from P_2 X P_2 all yield a graph with two vertices joined by an edge. This graph has 1 0-matching and 1 1-matching, thus T(2,k) = 4, 4.

%t CoefficientList[Normal[Series[(1 + 2*t*z + 2*z/(1-t*z)^2)*(1-t*z)^2/(1 - z - 2*t*z - t*z^2 + t^3*z^3)^2,{z,0,10}]],{z,t}]//MatrixForm

%Y Cf. A046741, A318244, A318267, A318268, A318269, A318270.

%K nonn,tabl

%O 1,2

%A _Donovan Young_, Aug 22 2018