A192437 -id:A192437 - cp's OEIS frontend

A045310 Number of matchings in n-cube.

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

Offset: 0

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

			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)

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

For perfect matchings see A005271.
For matching polynomials, see A192437, A302235.
Cf. A033532.

C
```
/* See Links section. */
```
Perl
```
# See Links section.
```

A302235 Triangle T(n,k) of the numbers of k-matchings in the n-hypercube graph (0 <= k <= 2^(n-1)).

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 12, 42, 44, 9, 1, 32, 400, 2496, 8256, 14208, 11648, 3712, 272, 1, 80, 2840, 59120, 803580, 7517264, 49715240, 235146480, 795862790, 1910146160, 3190117800, 3594554960, 2605908220, 1129177840, 259084440, 25108944, 589185, 1, 192, 17376, 986240

Offset: 1

Eric W. Weisstein, Apr 03 2018

			Rows as matching-generating polynomials:
1 + x,
1 + 4*x + 2*x^2
1 + 12*x + 42*x^2 + 44*x^3 + 9*x^4
1 + 32*x + 400*x^2 + 2496*x^3 + 8256*x^4 + 14208*x^5 + 11648*x^6 + 3712*x^7 + 272*x^8
...

Eric W. Weisstein, Table of n, a(n) for n = 1..68
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Row sums are A045310.
Columns k=0..2 are A000012, A001787, A360786.
Cf. A005271 (rightmost terms), A192437.

A360786 Number of ways to place two dimers on an n-cube.

Original entry on oeis.org

0, 2, 42, 400, 2840, 17376, 97440, 516608, 2634624, 13058560, 63320576, 301707264, 1417009152, 6575120384, 30195425280, 137430827008, 620604391424, 2783097520128, 12403773407232, 54975376916480, 242441862512640, 1064326263734272, 4653131038195712, 20266193591992320

Offset: 1

Krishnan Balasubramanian, Feb 20 2023

Equivalently, a(n) is the number of 2-matchings in the n-hypercube graph. A 2-matching is a pair of edges that do not share a vertex.

			The a(2) = 2 2-matchings are:
    o---o     o   o
              |   |
    o---o     o   o

Krishnan Balasubramanian, Topological Indices, Graph Spectra, Entropies, Laplacians, and Matching Polynomials of n-Dimensional Hypercubes, Symmetry. 2023; 15(2):557.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial.
Index entries for linear recurrences with constant coefficients, signature (18,-132,504,-1056,1152,-512).

Column k=2 of A302235.
Third from last terms in rows of A192437.
Cf. A001787 (1-matchings), A045310 (matchings).

a(n) = 2^(n-2)*n*(1 - 2*n + n*2^(n-1)) \\ Andrew Howroyd, Feb 20 2023

a(n) = A192437(n, 2^(n-1)-2) for n > 1.
From Andrew Howroyd, Feb 20 2023: (Start)
a(n) = 2^(n-2)*n*(1 - 2*n + n*2^(n-1)).
a(n) = 18*a(n-1) - 132*a(n-2) + 504*a(n-3) - 1056*a(n-4) + 1152*a(n-5) - 512*a(n-6) for n > 6.
G.f.: 2*x^2*(1 + 3*x - 46*x^2 + 88*x^3)/((1 - 2*x)*(1 - 4*x))^3.
(End)

Terms a(13) and beyond from Andrew Howroyd, Feb 20 2023

cp's OEIS Frontend

A045310 Number of matchings in n-cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Perl

A302235 Triangle T(n,k) of the numbers of k-matchings in the n-hypercube graph (0 <= k <= 2^(n-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

A360786 Number of ways to place two dimers on an n-cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions