A318243 -id:A318243 - 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.

0, 0, 1, 8, 39, 138, 414, 1104, 2715, 6282, 13875, 29540, 61060, 123192, 243589, 473540, 907335, 1716974, 3214066, 5959704, 10958687, 20001526, 36264579, 65359752, 117165096, 209008464, 371190217, 656540768, 1156924167, 2031676818, 3556517478

Offset: 0

Donovan Young, Aug 22 2018

The generating function has been obtained using the calculus of the rook polynomial associated with A046741.
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.
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

			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}.
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.

Muniru A Asiru, Table of n, a(n) for n = 0..2000
D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
Index entries for linear recurrences with constant coefficients, signature (5,-7,-2,10,-2,-5,1,1).

Cf. A000045, A046741, A178523, A318243, A318244, A318268, A318269, A318270.

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

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

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]

G.f.: x^2*(1 + 3*x + 6*x^2 + x^3 + 3*x^4)/((1 - x)^2*(1 - x - x^2)^3).

A318268 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 3 such pairs are joined by an edge.

Original entry on oeis.org

0, 0, 0, 2, 34, 250, 1234, 4830, 16174, 48444, 133416, 344220, 843020, 1978804, 4484228, 9865742, 21166390, 44439910, 91570126, 185614242, 370846914, 731502296, 1426514540, 2753525208, 5266164280, 9987859912, 18799814312, 35141997050, 65274659562, 120540177522

Offset: 0

Donovan Young, Aug 22 2018

This is also the number of "(n-3)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - Donovan Young, Oct 23 2018

			See example in A318267.

Andrew Howroyd, PARI program based on combinatorial definition
D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
Index entries for linear recurrences with constant coefficients, signature (7,-17,11,19,-29,-3,21,-3,-7,1,1).

Cf. A046741, A318243, A318244, A318267, A318269, A318270.

CoefficientList[Normal[Series[x^2(2*x + 20*x^2 + 46*x^3 + 40*x^4 + 30*x^5 + 4*x^6 + 4*x^7)/(1 - x)^3/(1 - x - x^2)^4, {x, 0, 30}]], x]
LinearRecurrence[{7,-17,11,19,-29,-3,21,-3,-7,1,1},{0,0,0,2,34,250,1234,4830,16174,48444,133416},30] (* Harvey P. Dale, Aug 05 2019 *)

G.f.: x^2*(2*x + 20*x^2 + 46*x^3 + 40*x^4 + 30*x^5 + 4*x^6 + 4*x^7)/(1 - x)^3/(1 - x - x^2)^4 (conjectured).

The above conjecture is true. The PARI program given in the links can be used to establish an upper limit on the order of the linear recurrence and sufficient number of terms to prove correctness. - Andrew Howroyd, Sep 03 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 03 2018

A318244 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 only one such pair is joined by an edge.

Original entry on oeis.org

1, 0, 8, 34, 347, 3666, 47484, 707480, 11971341, 226599568, 4744010444, 108834109034, 2714992695407, 73169624071138, 2118530753728184, 65582753432993648, 2161565971116312537, 75572040870327124064, 2793429487732659591888, 108847840347732886117874, 4459207771645802095292995

Offset: 1

Donovan Young, Aug 22 2018

nonn

This is a companion entry to A318243 and uses an inclusion-exclusion method on the matching numbers given there.

This is also the number of "1-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - Donovan Young, Oct 23 2018

			For the case n = 2, if one pair is joined by an edge, then the remaining pair is forced to be joined by the remaining edge. Thus a(2) = 0.

D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.

Cf. A046741, A318243, A318267, A318268, A318269, A318270. When no pair is joined by an edge, the number of configurations is given by A265167.

a(n) = Sum_{k=0..n-1} (-1)^k*(2*n-2*k-3)!! * A318243(n,k) where and 0!! = (-1)!! = 1; proved by inclusion-exclusion.

A318269 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 4 such pairs are joined by an edge.

Original entry on oeis.org

0, 0, 0, 0, 21, 347, 2919, 17050, 78815, 309075, 1072617, 3386970, 9921030, 27338000, 71614370, 179788174, 435311905, 1021684125, 2333955085, 5207067714, 11377225161, 24403026561, 51484962205, 107024887620, 219528748908, 444886466640, 891735024852, 1769575953980

Offset: 0

Donovan Young, Aug 23 2018

This is also the number of "(n-4)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - Donovan Young, Oct 23 2018

			See example in A318267.

D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
Index entries for linear recurrences with constant coefficients, signature (9,-31,44,4,-84,66,46,-74,-4,36,-4,-9,1,1).

Cf. A046741, A318243, A318244, A318267, A318268, A318270.

CoefficientList[Normal[Series[x^2(5*x^10 + 10*x^9 + 93*x^8 + 230*x^7 + 502*x^6 + 612*x^5 + 447*x^4 + 158*x^3 + 21*x^2)/(1 - x)^4/(1 - x - x^2)^5, {x, 0, 30}]], x]

G.f.: x^2*(5*x^10 + 10*x^9 + 93*x^8 + 230*x^7 + 502*x^6 + 612*x^5 + 447*x^4 + 158*x^3 + 21*x^2)/(1 - x)^4/(1 - x - x^2)^5 (conjectured).

The above conjecture is true. See A318268. - Andrew Howroyd, Sep 03 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 03 2018

A318270 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 5 such pairs are joined by an edge.

Original entry on oeis.org

0, 0, 0, 0, 0, 186, 3666, 36714, 253386, 1369260, 6209700, 24668742, 88338174, 290968686, 894709790, 2597386330, 7181246394, 19040425628, 48684375292, 120592523460, 290476059204, 682548818802, 1568744083242, 3534725236308, 7823387477220, 17037467831748

Offset: 0

Donovan Young, Aug 23 2018

This is also the number of "(n-5)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - Donovan Young, Oct 23 2018

			See example in A318267.

D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
Index entries for linear recurrences with constant coefficients, signature (11,-49,105,-75,-123,278,-82,-250,210,90,-150,-5,55,-5,-11,1,1).

Cf. A046741, A318243, A318244, A318267, A318268, A318269.

CoefficientList[Normal[Series[x^2(6*x^13+20*x^12+228*x^11+888*x^10+3012*x^9+6612*x^8+10020*x^7+9636*x^6+5502*x^5+1620*x^4+186*x^3)/(1-x)^5/(1-x-x^2)^6,{x,0,30}]],x]

G.f.: x^2*(6*x^13 + 20*x^12 + 228*x^11 + 888*x^10 + 3012*x^9 + 6612*x^8 + 10020*x^7 + 9636*x^6 + 5502*x^5 + 1620*x^4 + 186*x^3)/(1 - x)^5/(1 - x - x^2)^6 (conjectured).

The above conjecture is true. See A318268. - Andrew Howroyd, Sep 03 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 03 2018

A325753 Triangle read by rows giving the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that exactly k such pairs are joined by an edge.

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 2, 8, 2, 3, 21, 34, 39, 6, 5, 186, 347, 250, 138, 16, 8, 2113, 3666, 2919, 1234, 414, 36, 13, 27856, 47484, 36714, 17050, 4830, 1104, 76, 21, 422481, 707480, 545788, 253386, 78815, 16174, 2715, 152, 34, 7241480, 11971341, 9195198, 4317996, 1369260, 309075, 48444, 6282, 294, 55

Offset: 0

Donovan Young, May 18 2019

This is the number of "k-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. First column is A265167, second column is A318244. Diagonals are given by A000045, A178523, A318267, A318268, A318269, A318270.

			The first few rows of T(n,k) are:
   1;
   0,  1;
   1,  0,  2;
   2,  8,  2,  3;
  21, 34, 39,  6, 5;
  ...
For n = 2 there is only one way to place the two pairs such that neither is joined by an edge, hence T(2,0)=1. If one pair is joined by an edge, the other is forced to be, hence T(2,1) = 0, and since the pairs can be joined horizontally or vertically T(2,2) = 2.

D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.

Cf. A046741, A178523, A265167, A318243, A318244, A318267, A318268, A318269, A318270.

CoefficientList[Normal[Series[Sum[Factorial2[2*k-1]*y^k*(1-(1-z)*y)^k/(1+(1-z)*y)^k/(1+(1-z)*y-(1-z)^2*y^2)^(k+1),{k,0,20}],{y,0,20}]],{y,z}];

G.f.: Sum_{j>=0} (2*j-1)!! * y^j * (1-(1-z)*y)^j / (1+(1-z)*y)^j / (1+(1-z)*y-(1-z)^2*y^2)^(j+1).

A325754 Triangle read by rows giving the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that exactly k such pairs are joined by a horizontal edge.

Original entry on oeis.org

1, 1, 0, 2, 0, 1, 7, 4, 4, 0, 43, 38, 21, 2, 1, 372, 360, 168, 36, 9, 0, 4027, 3972, 1818, 478, 93, 6, 1, 51871, 51444, 23760, 6640, 1260, 144, 16, 0, 773186, 768732, 358723, 103154, 20205, 2734, 278, 12, 1, 13083385, 13027060, 6129670, 1796740, 363595, 52900, 5650, 400, 25, 0

Offset: 0

Donovan Young, May 19 2019

This is the number of "k-horizontal-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young].

			The first few rows of T(n,k) are:
  1;
  1,  0;
  2,  0,  1;
  7,  4,  4,  0;
  43, 38, 21, 2, 1;
  ...
For n=2, let the vertex set of P_2 X P_2 be {A,B,C,D} and the edge set be {AB, AC, BD, CD}, where AB and CD are horizontal edges. For k=0, we may place the pairs on A, C and B, D or on A, D and B, C, hence T(2,0) = 2. If we place a pair on one of the horizontal edges we are forced to place the other pair on the remaining horizontal edge, hence T(2,1)=0 and T(2,2)=1.

D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.

Cf. A046741, A055140, A079267 A178523, A265167, A318243, A318244, A318267, A318268, A318269, A318270, A325753.

CoefficientList[Normal[Series[Sum[Factorial2[2*k-1]*y^k/(1-(1-z)*y)/(1+(1-z)*y)^(2*k+1), {k, 0, 20}], {y, 0, 20}]], {y, z}];

G.f.: Sum_{j>=0} (2*j-1)!! y^j/(1-(1-z)*y)/(1+(1-z)*y)^(2*j+1).

E.g.f.: exp((sqrt(1 - 2 y)-1) (1 - z))/sqrt(1 - 2 y) - exp((y - 2) (1 - z)) sqrt(Pi/2) sqrt(1 - z) (-erfi(sqrt(2) sqrt(1 - z)) + erfi(((1 + sqrt(1 - 2 y)) sqrt(1 - z))/sqrt(2))).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

Formula

A318268 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 3 such pairs are joined by an edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A318244 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 only one such pair is joined by an edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A318269 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 4 such pairs are joined by an edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A318270 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 5 such pairs are joined by an edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A325753 Triangle read by rows giving the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that exactly k such pairs are joined by an edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325754 Triangle read by rows giving the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that exactly k such pairs are joined by a horizontal edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica