A005271 -id:A005271 - cp's OEIS frontend

A233001 a(n) = A005271(n)^2.

1, 4, 81, 73984, 347138964225, 266749070875738835911704576, 153420859074097275505001068428834200016791982521508695409921

Offset: 1

N. J. A. Sloane, Dec 17 2013

Daryl DeFord, Seating rearrangements on arbitrary graphs, Involve, Vol. 7 (2014), No. 6, 787-805. See Table 3.

Cf. A005271.

A045310 Number of matchings in n-cube.

Original entry on oeis.org

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

Offset: 0

Per H. Lundow

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.

A112311 a(1)=1, a(2)=2, a(3)=9; a(n) = n(n - 2)a(n - 1)^2/(n - 1).

Original entry on oeis.org

1, 2, 9, 216, 174960, 146932807680, 125937291507579224064000, 108755666689817047890109782510255885778944000000, 93143885917529328515023382841413836868525118214478405334515136630707122998865821696000000000000

Offset: 1

N. J. A. Sloane, Dec 01 2005

nonn

Lower bound to number of perfect Morse matchings of n-simplex.

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

Cf. A005271.

A220904 Number of equivalence classes of perfect matchings in the n-cube.

Original entry on oeis.org

1, 1, 2, 8, 336, 356788059, 607158046495120886820621

Offset: 1

N. J. A. Sloane, Jan 01 2013

nonn

N. Graham and F. Harary, The number of perfect matchings in a hypercube, Appl. Math. Lett., 1 (1988), 45-48.
Patric R. J. Östergård and V. H. Pettersson, Enumerating Perfect Matchings in n-Cubes, Order, November 2013, Volume 30, Issue 3, pp 821-835.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Preprint 2015.

Cf. A005271.

cp's OEIS Frontend

A233001 a(n) = A005271(n)^2.

Views

Author

Keywords

Links

Crossrefs

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

A112311 a(1)=1, a(2)=2, a(3)=9; a(n) = n(n - 2)a(n - 1)^2/(n - 1).

Views

Author

Keywords

Comments

References

Crossrefs

A220904 Number of equivalence classes of perfect matchings in the n-cube.

Views

Author

Keywords

Links

Crossrefs

cp's OEIS Frontend

A233001 a(n) = A005271(n)^2.

Views

Author

Keywords

Links

Crossrefs

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

A112311 a(1)=1, a(2)=2, a(3)=9; a(n) = n*(n - 2)*a(n - 1)^2/(n - 1).

Views

Author

Keywords

Comments

References

Crossrefs

A220904 Number of equivalence classes of perfect matchings in the n-cube.

Views

Author

Keywords

Links

Crossrefs

A112311 a(1)=1, a(2)=2, a(3)=9; a(n) = n(n - 2)a(n - 1)^2/(n - 1).