login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005271 Number of perfect matchings in n-cube.
(Formerly M1955)
6
1, 2, 9, 272, 589185, 16332454526976, 391689748492473664721077609089 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
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
REFERENCES
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).
LINKS
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.
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
EXAMPLE
G.f. = x + 2*x^2 + 9*x^3 + 272*x^4 + 589185*x^5 + 16332454526976*x^6 + ...
CROSSREFS
For all matchings see A045310.
Sequence in context: A042675 A308647 A015177 * A258668 A012938 A302251
KEYWORD
nonn,hard,more,nice
AUTHOR
EXTENSIONS
a(6) from Per H. Lundow, Jul 15 1996
a(7) from N. J. A. Sloane, Jan 01 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)