|
%I M1955 #66 Oct 23 2023 12:26:08
%S 1,2,9,272,589185,16332454526976,391689748492473664721077609089
%N Number of perfect matchings in n-cube.
%C The matchings contain 2^n / 2 = 2^(n-1) edges.
%C a(6) was first found by D. H. Wiedemann, unpublished (see Clark et al., Skupien).
%C Also the number of minimum edge covers and minimum clique coverings in the n-hypercube graph. - _Eric W. Weisstein_, Dec 24 2017
%D 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.
%D 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).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H M. K. Chari and M. Joswig, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.027">Complexes of discrete Morse functions</a>, Disc. Math. 302 (2005), 39-51.
%H D. Deford, <a href="https://doi.org/10.2140/involve.2014.7.787">Seating rearrangements on arbitrary graphs</a>, Involve 7(6): 787-805 (2014); See Table 3.
%H N. Graham and F. Harary, <a href="https://doi.org/10.1016/0893-9659(88)90173-5">The number of perfect matchings in a hypercube</a>, Appl. Math. Lett., 1 (1988), 45-48.
%H N. Graham and F. Harary, <a href="/A005271/a005271.pdf">The number of perfect matchings in a hypercube</a>, Appl. Math. Lett. 1.1 (1988), 45-48. (Annotated scanned copy)
%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors.pdf">Computation of matching polynomials and the number of 1-factors in polygraphs</a>, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
%H Patric R. J. Östergård and V. H. Pettersson, <a href="https://doi.org/10.1007/s11083-012-9279-8">Enumerating Perfect Matchings in n-Cubes</a>, Order, November 2013, Volume 30, Issue 3, pp 821-835.
%H Ville Pettersson, <a href="https://aaltodoc.aalto.fi/bitstream/handle/123456789/17688/isbn9789526063652.pdf?sequence=1">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Preprint 2015.
%H J. Propp, <a href="https://arxiv.org/abs/math/9801061">Twenty open problems in enumeration of matchings</a>, arXiv:math/9801061 [math.CO], 1998-1999.
%H J. Propp, <a href="http://faculty.uml.edu/jpropp/update.pdf">Updated article</a>
%H J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), <a href="http://www.msri.org/publications/books/Book38/contents.html">New Perspectives in Algebraic Combinatorics</a>
%H H. Sachs and B. Alspach, <a href="https://doi.org/10.1016/S0012-365X(98)90041-3">Problem 298: How many perfect matchings does the graph of the n-cube have?</a>, Discrete Math., 191 (1998), 251-252. [From _N. J. A. Sloane_, Feb 18 2012]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentEdgeSet.html">Maximum Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimumCliqueCovering.html">Minimum Clique Covering</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimumEdgeCover.html">Minimum Edge Cover</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectMatching.html">Perfect Matching</a>
%e G.f. = x + 2*x^2 + 9*x^3 + 272*x^4 + 589185*x^5 + 16332454526976*x^6 + ...
%Y Cf. A220904, A112311.
%Y For all matchings see A045310.
%K nonn,hard,more,nice
%O 1,2
%A _N. J. A. Sloane_
%E a(6) from _Per H. Lundow_, Jul 15 1996
%E a(7) from _N. J. A. Sloane_, Jan 01 2013
| 