login
Number of matchings in n-cube.
5

%I #52 May 25 2024 14:36:05

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

%N Number of matchings in n-cube.

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

%C a(3) = A033516(2) = A033535(2). - _Alois P. Heinz_, Dec 09 2013

%C 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

%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 Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.

%H Per Hakan Lundow, <a href="http://abel.math.umu.se/~phl/Mathematica/">GrafPack</a> (Mathematica package).

%H Hugo van der Sanden, <a href="https://github.com/hvds/seq/blob/master/part/find2">find2: Proof of concept in perl</a>

%H Hugo van der Sanden, <a href="https://github.com/hvds/seq/blob/master/part/find2c.c">find2c.c: Fast version in C</a>.

%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/IndependentEdgeSet.html">Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%e From _Max Alekseyev_, Nov 16 2009: (Start)

%e E.g., for n=2, we have

%e 1 matching of size 0 (i.e., the empty matching)

%e 4 matchings of size 1 (i.e., an edge)

%e 2 matchings of size 2 (that are the perfect matchings).

%e So a(2) = 1 + 4 + 2 = 7, whereas A005271(2) = 2. (End)

%o (Perl) # See Links section.

%o (C) /* See Links section. */

%Y For perfect matchings see A005271.

%Y For matching polynomials, see A192437, A302235.

%Y Cf. A033532.

%K nonn,hard,more

%O 0,2

%A _Per H. Lundow_