A360786 Number of ways to place two dimers on an n-cube.

0, 2, 42, 400, 2840, 17376, 97440, 516608, 2634624, 13058560, 63320576, 301707264, 1417009152, 6575120384, 30195425280, 137430827008, 620604391424, 2783097520128, 12403773407232, 54975376916480, 242441862512640, 1064326263734272, 4653131038195712, 20266193591992320

Offset

1,2

Comments

Equivalently, a(n) is the number of 2-matchings in the n-hypercube graph. A 2-matching is a pair of edges that do not share a vertex.

Links

Table of n, a(n) for n=1..24.

Krishnan Balasubramanian, Topological Indices, Graph Spectra, Entropies, Laplacians, and Matching Polynomials of n-Dimensional Hypercubes, Symmetry. 2023; 15(2):557.

Eric Weisstein's World of Mathematics, Hypercube Graph.

Eric Weisstein's World of Mathematics, Matching-Generating Polynomial.

Index entries for linear recurrences with constant coefficients, signature (18,-132,504,-1056,1152,-512).

Formula

a(n) = A192437(n, 2^(n-1)-2) for n > 1.

From Andrew Howroyd, Feb 20 2023: (Start)

a(n) = 2^(n-2)*n*(1 - 2*n + n*2^(n-1)).

a(n) = 18*a(n-1) - 132*a(n-2) + 504*a(n-3) - 1056*a(n-4) + 1152*a(n-5) - 512*a(n-6) for n > 6.

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

(End)

Example

The a(2) = 2 2-matchings are:
    o---o     o   o
              |   |
    o---o     o   o

Prog

(PARI) a(n) = 2^(n-2)*n*(1 - 2*n + n*2^(n-1)) \\ Andrew Howroyd, Feb 20 2023

Crossrefs

Column k=2 of A302235.

Third from last terms in rows of A192437.

Cf. A001787 (1-matchings), A045310 (matchings).

Sequence in context: A048373 A066563 A202865 * A070808 A229474 A157056

Adjacent sequences: A360783 A360784 A360785 * A360787 A360788 A360789

Keyword

nonn,easy

Author

Krishnan Balasubramanian, Feb 20 2023

Extensions

Terms a(13) and beyond from Andrew Howroyd, Feb 20 2023

Status

approved