A270229 -id:A270229 - cp's OEIS frontend

A270228 Number of matchings in the n X n rook graph K_n X K_n.

1, 7, 370, 270529, 3337807996, 855404716021831, 5352265402523357926168, 940288991338542314571521981185, 5236753179470435264288904589157765055760, 1029720447530443779943631183186535523331685533812231

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

K_n X K_n is also called the rook graph or lattice graph.

Andrew Howroyd, Table of n, a(n) for n = 1..16
Andrew Howroyd, C# software related to this sequence
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Rook Graph
Wikipedia, Rook's graph, Hosoya index

Cf. A270227, A270229, A085537 (Wiener index), A002720 (independent vertex sets), A269561, A028420.

A270227 Array read by antidiagonals: T(n,m) is the number of matchings in the rook graph K_n X K_m.

Original entry on oeis.org

1, 2, 2, 4, 7, 4, 10, 32, 32, 10, 26, 193, 370, 193, 26, 76, 1382, 5950, 5950, 1382, 76, 232, 11719, 122984, 270529, 122984, 11719, 232, 764, 112604, 3175696, 16873930, 16873930, 3175696, 112604, 764, 2620, 1221889, 98815588, 1384880065, 3337807996, 1384880065, 98815588, 1221889, 2620

Offset: 1

Andrew Howroyd, Mar 13 2016

Observations: (for n+m <= 32)
Examination of values modulus a small prime yields several patterns.
T(n,m) == (n+1)*(m+1) (mod 2) for n+m>2.
T(n,m) == T(n,m+6) (mod 3).
T(n,m) is not divisible by 3.
T(n,m) == 0 (mod 5) for n==4 (mod 5) and m<>2 and except when m=n=4.
T(5,m) == 0 (mod 208) for m >= 13.
T(6,m) == 0 (mod 19) for m >= 19.

			The start of the sequence as table:
*   1     2       4         10           26              76 ...
*   2     7      32        193         1382           11719 ...
*   4    32     370       5950       122984         3175696 ...
*  10   193    5950     270529     16873930      1384880065 ...
*  26  1382  122984  168739305   3337807996    909046586596 ...
*  76 11719 3175696 1384880065 909046586596 855404716021831 ...
* ...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A270228. Rows include A000085, A270229.

A281433 Number of maximal matchings in the 2 X n rook graph.

Original entry on oeis.org

1, 1, 2, 10, 40, 296, 1576, 15352, 104000, 1276480, 10556416, 156843776, 1533722752, 26777626240, 302395339520, 6068829396736, 77740741758976, 1763457842941952, 25267740818452480, 639308368122204160, 10131932297407840256, 282891828731667890176

Offset: 0

Andrew Howroyd, Oct 05 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..100 (corrected by Ray Chandler, Jan 19 2019)

Row n=2 of A341847.

Cf. A081919 (perfect matchings), A270229, A289198.

a[n_] := Sum[(2*k-1)!!^2 * Binomial[n, 2*k] * (1 + 2*k*(n-2*k)), {k, 0, n/2} ]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

a(n) = sum(k=0, n\2, ((2*k)!/(2^k*k!))^2 * binomial(n,2*k) * (1 + 2*k*(n-2*k)));

a(n) = Sum_{k=0..n/2} (2*k-1)!!^2 * binomial(n,2*k) * (1 + 2*k*(n-2*k)).

cp's OEIS Frontend

A270228 Number of matchings in the n X n rook graph K_n X K_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A270227 Array read by antidiagonals: T(n,m) is the number of matchings in the rook graph K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A281433 Number of maximal matchings in the 2 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula