A045310 Number of matchings in n-cube.

1, 2, 7, 108, 41025, 13803794944, 7174574164703330195841

Offset: 0

Author

Per H. Lundow

Keywords

• nonn
• hard
• more

Comments

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

a(3) = A033516(2) = A033535(2). - Alois P. Heinz, Dec 09 2013

Equivalently, the number of decompositions of an n-dimensional cube of size 2 into (zero or more) unit cubes (1 X 1 X ... X 1) and "dominoes" (2 X 1 X 1 X ... X 1). - Hugo van der Sanden, Nov 30 2016

Examples

			From _Max Alekseyev_, Nov 16 2009: (Start)
E.g., for n=2, we have
1 matching of size 0 (i.e., the empty matching)
4 matchings of size 1 (i.e., an edge)
2 matchings of size 2 (that are the perfect matchings).
So a(2) = 1 + 4 + 2 = 7, whereas A005271(2) = 2. (End)
		

Links

• 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.
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• Per Hakan Lundow, GrafPack (Mathematica package).
• Hugo van der Sanden, find2: Proof of concept in perl
• Hugo van der Sanden, find2c.c: Fast version in C.
• Eric Weisstein's World of Mathematics, Hypercube Graph
• Eric Weisstein's World of Mathematics, Independent Edge Set
• Eric Weisstein's World of Mathematics, Matching

Crossrefs

For perfect matchings see A005271.

For matching polynomials, see A192437, A302235.

Cf. A033532.

Programs

C

/* See Links section. */

Perl

# See Links section.