login
This site is supported by donations 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)
4
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).

REFERENCES

M. K. Chari and M. Joswig, Complexes of discrete Morse functions, Disc. Math. 302 (2005), 39-51.

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. Deford, Seating rearrangements on arbitrary graphs, 2013; http://www.math.dartmouth.edu/~ddeford/graphs.pdf. See Table 3.

N. Graham and F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett., 1 (1988), 45-48.

P. R. J. Ostergard and V. H. Pettersson, Enumerating Perfect Matchings in n-Cubes, http://users.tkk.fi/~pat/papers/matching.pdf, 2012.

Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Preprint 2015, https://aaltodoc.aalto.fi/bitstream/handle/123456789/17688/isbn9789526063652.pdf?sequence=1

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

Z. Skupien, 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]

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.

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.

J. Propp, Twenty open problems in enumeration of matchings.

J. Propp, Updated article

J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics

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,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

n=6 term from Per H. Lundow, Jul 15 1996.

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 01:22 EDT 2017. Contains 283984 sequences.