The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 8
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
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
LINKS
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.
FORMULA
G.f.: x^2*(1 + 3*x + 6*x^2 + x^3 + 3*x^4)/((1 - x)^2*(1 - x - x^2)^3).
EXAMPLE
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.
MAPLE
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
MATHEMATICA
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]
PROG
(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
CROSSREFS
Sequence in context: A101374 A163687 A060446 * A063002 A055581 A297017
KEYWORD
nonn,easy
AUTHOR
Donovan Young, Aug 22 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 29 21:02 EDT 2024. Contains 372952 sequences. (Running on oeis4.)