|
%I #49 Apr 06 2018 15:53:30
%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 For Perl and C programs 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_
| 