A302235 -id:A302235 - cp's OEIS frontend

A045310 Number of matchings in n-cube.

1, 2, 7, 108, 41025, 13803794944, 7174574164703330195841

Offset: 0

a(4) = A033532(1), a(5) = A033532(2).
a(3) = A033516(2) = A033535(2). - Alois P. Heinz, Dec 09 2013
Equivalently, the number of decompositions of an n-dimensional cube of size 2 into (zero or more) unit cubes (1 X 1 X ... X 1) and "dominoes" (2 X 1 X 1 X ... X 1). - Hugo van der Sanden, Nov 30 2016

			From _Max Alekseyev_, Nov 16 2009: (Start)
E.g., for n=2, we have
1 matching of size 0 (i.e., the empty matching)
4 matchings of size 1 (i.e., an edge)
2 matchings of size 2 (that are the perfect matchings).
So a(2) = 1 + 4 + 2 = 7, whereas A005271(2) = 2. (End)

Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Per Hakan Lundow, GrafPack (Mathematica package).
Hugo van der Sanden, find2: Proof of concept in perl
Hugo van der Sanden, find2c.c: Fast version in C.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching

For perfect matchings see A005271.
For matching polynomials, see A192437, A302235.
Cf. A033532.

C
```
/* See Links section. */
```
Perl
```
# See Links section.
```

A192437 Triangle of nonzero (even) coefficients of the matching polynomials for the hypercube graphs Q_n.

Original entry on oeis.org

-1, 1, 2, -4, 1, 9, -44, 42, -12, 1, 272, -3712, 11648, -14208, 8256, -2496, 400, -32, 1, 589185, -25108944, 259084440, -1129177840, 2605908220, -3594554960, 3190117800, -1910146160, 795862790, -235146480, 49715240, -7517264, 803580, -59120, 2840, -80, 1, 16332454526976, -2333280165691392, 81808261704974336

Offset: 1

Eric W. Weisstein, Jul 13 2011

			mu(Q_1) = -1+x^2,
mu(Q_2) = 2-4*x^2+x^4,
mu(Q_3) = 9-44*x^2+42*x^4-12*x^6+x^8,
so the triangle begins:
-1,  1;
2,  -4,  1;
9, -44, 42, -12, 1;

Eric Weisstein, Table of n, a(n) for n = 1..69
Krishnan Balasubramanian, Topological Indices, Graph Spectra, Entropies, Laplacians, and Matching Polynomials of n-Dimensional Hypercubes, Symmetry (2023) Vol. 15, No. 2, 557.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Per Hakan Lundow, GrafPack (Mathematica package). [Broken link]
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Matching Polynomial

For numbers of matchings, see A045310.

Cf. A302235.

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

Original entry on oeis.org

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

Krishnan Balasubramanian, Feb 20 2023

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.

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

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

Column k=2 of A302235.
Third from last terms in rows of A192437.
Cf. A001787 (1-matchings), A045310 (matchings).

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

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)

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

cp's OEIS Frontend

A045310 Number of matchings in n-cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Perl

A192437 Triangle of nonzero (even) coefficients of the matching polynomials for the hypercube graphs Q_n.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions