

A005271


Number of perfect matchings in ncube.
(Formerly M1955)


4




OFFSET

1,2


COMMENTS

The matchings contain 2^n / 2 = 2^(n1) edges.
a(6) was first found by D. H. Wiedemann, unpublished (see Clark et al., Skupien).


REFERENCES

L. H. Clark, J. C. George and T. D. Porter, On the number of 1factors in the ncube, Congress. Numer., 127 (1997), 6769.
J. Propp, Enumeration of matchings: problems and progress, pp. 255291 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).


LINKS

Table of n, a(n) for n=1..7.
M. K. Chari and M. Joswig, Complexes of discrete Morse functions, Disc. Math. 302 (2005), 3951.
D. Deford, Seating rearrangements on arbitrary graphs, 2013; See Table 3.
N. Graham and F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett., 1 (1988), 4548.
Per Hakan Lundow, Computation of matching polynomials and the number of 1factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
P. R. J. Ostergard and V. H. Pettersson, Enumerating Perfect Matchings in nCubes, Order, November 2013, Volume 30, Issue 3, pp 821835.
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], 19981999.
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, B. Alspach, Problem 298: How many perfect matchings does the graph of the ncube have?, Discrete Math., 191 (1998), 251252. [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, Perfect Matching


EXAMPLE

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


CROSSREFS

Cf. A220904, A112311.
For all matchings see A045310.
Sequence in context: A122894 A042675 A015177 * A258668 A012938 A013093
Adjacent sequences: A005268 A005269 A005270 * A005272 A005273 A005274


KEYWORD

nonn,hard,more,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

a(6) from Per H. Lundow, Jul 15 1996
a(7) from N. J. A. Sloane, Jan 01 2013


STATUS

approved



