A045310 -id:A045310 - cp's OEIS frontend

A005271 Number of perfect matchings in n-cube.

1, 2, 9, 272, 589185, 16332454526976, 391689748492473664721077609089

Offset: 1

The matchings contain 2^n / 2 = 2^(n-1) edges.
a(6) was first found by D. H. Wiedemann, unpublished (see Clark et al., Skupien).
Also the number of minimum edge covers and minimum clique coverings in the n-hypercube graph. - Eric W. Weisstein, Dec 24 2017

			G.f. = x + 2*x^2 + 9*x^3 + 272*x^4 + 589185*x^5 + 16332454526976*x^6 + ...

L. H. Clark, J. C. George and T. D. Porter, On the number of 1-factors in the n-cube, Congress. Numer., 127 (1997), 67-69.
J. Propp, Enumeration of matchings: problems and progress, pp. 255-291 in L. J. Billera et al., eds, New Perspectives in Algebraic Combinatorics, Cambridge, 1999 (see Problem 18).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. K. Chari and M. Joswig, Complexes of discrete Morse functions, Disc. Math. 302 (2005), 39-51.
D. Deford, Seating rearrangements on arbitrary graphs, Involve 7(6): 787-805 (2014); See Table 3.
N. Graham and F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett., 1 (1988), 45-48.
N. Graham and F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett. 1.1 (1988), 45-48. (Annotated scanned copy)
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.
Patric R. J. Östergård and V. H. Pettersson, Enumerating Perfect Matchings in n-Cubes, Order, November 2013, Volume 30, Issue 3, pp 821-835.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Preprint 2015.
J. Propp, Twenty open problems in enumeration of matchings, arXiv:math/9801061 [math.CO], 1998-1999.
J. Propp, Updated article
J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
H. Sachs and B. Alspach, Problem 298: How many perfect matchings does the graph of the n-cube have?, Discrete Math., 191 (1998), 251-252. [From _N. J. A. Sloane_, Feb 18 2012]
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Minimum Clique Covering
Eric Weisstein's World of Mathematics, Minimum Edge Cover
Eric Weisstein's World of Mathematics, Perfect Matching

Cf. A220904, A112311.

For all matchings see A045310.

a(6) from Per H. Lundow, Jul 15 1996

a(7) from N. J. A. Sloane, Jan 01 2013

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.

A302235 Triangle T(n,k) of the numbers of k-matchings in the n-hypercube graph (0 <= k <= 2^(n-1)).

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein, Apr 03 2018

			Rows as matching-generating polynomials:
1 + x,
1 + 4*x + 2*x^2
1 + 12*x + 42*x^2 + 44*x^3 + 9*x^4
1 + 32*x + 400*x^2 + 2496*x^3 + 8256*x^4 + 14208*x^5 + 11648*x^6 + 3712*x^7 + 272*x^8
...

Eric W. Weisstein, Table of n, a(n) for n = 1..68
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Row sums are A045310.
Columns k=0..2 are A000012, A001787, A360786.
Cf. A005271 (rightmost terms), A192437.

A033532 Number of matchings in graph C_{4} X C_{4} X P_{n}.

Original entry on oeis.org

1, 41025, 13803794944, 3952450882750401, 1149377449671217283137, 333818434084936656186187776, 96963347585045688551801772350785, 28164412862777096850129871275625835649, 8180769830636914759269721968659872494731776, 2376225290581931684771439975937521777947501317377

Offset: 0

Per H. Lundow

nonn

a(1) = A045310(4), a(2) = A045310(5).

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

a(8)-a(9) from Alois P. Heinz, Dec 09 2013

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

A005271 Number of perfect matchings in n-cube.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A302235 Triangle T(n,k) of the numbers of k-matchings in the n-hypercube graph (0 <= k <= 2^(n-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

A033532 Number of matchings in graph C_{4} X C_{4} X P_{n}.

Views

Author

Keywords

Comments

References

Links

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions