A341847 -id:A341847 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 3, 4, 4, 3, 1, 1, 15, 16, 72, 16, 15, 1, 1, 15, 56, 132, 132, 56, 15, 1, 1, 105, 376, 7020, 2016, 7020, 376, 105, 1, 1, 105, 1912, 17280, 44928, 44928, 17280, 1912, 105, 1, 1, 945, 17984, 1920240, 1551744, 22615200, 1551744, 1920240, 17984, 945, 1

Offset: 0

Andrew Howroyd, Feb 21 2021

In the case that both m and n are odd a single vertex is not covered, otherwise the maximum matchings are perfect matchings.

			Array begins:
======================================================
n\m | 0  1   2     3       4         5           6
----+-------------------------------------------------
  0 | 1  1   1     1       1         1           1 ...
  1 | 1  1   1     3       3        15          15 ...
  2 | 1  1   2     4      16        56         376 ...
  3 | 1  3   4    72     132      7020       17280 ...
  4 | 1  3  16   132    2016     44928     1551744 ...
  5 | 1 15  56  7020   44928  22615200   243319680 ...
  6 | 1 15 376 17280 1551744 243319680 61903180800 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..527
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Rook Graph

Rows n=1..4 are A133221(n+1), A081919, A341851, A341852.
Main diagonal is A289197.
Cf. A270227 (matchings), A286070, A341847 (maximal matchings).

T(n,m) = T(m,n).

A289198 Number of maximal matchings in the n X n rook graph.

Original entry on oeis.org

1, 2, 84, 22368, 84961440, 5429866337280, 7315512116927938560, 235781588994736418036121600, 207456452048917943576497565466624000, 5583211401338046269360238971594326671360000000, 5098207942457032504011606690585598401287135271321600000000

Offset: 1

Eric W. Weisstein, Jun 28 2017

nonn

Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A341847.

Cf. A270228, A281433, A289197, A292196.

a(1) changed and a(5)-a(11) from Andrew Howroyd, Oct 05 2017

A341848 Number of maximal matchings in the 3 X n rook graph.

Original entry on oeis.org

1, 3, 10, 84, 852, 11580, 197640, 4314240, 100855440, 3342895920, 98070406560, 4652556511680, 163444377096000, 10568979882901440, 431650452829115520, 36599310178253222400, 1702185892636880851200, 183500657952824967955200, 9569677207227878912371200

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Row n=3 of A341847.

Cf. A341502, A341851.

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)).

A341849 Number of maximal matchings in the 4 X n rook graph.

Original entry on oeis.org

1, 3, 40, 852, 22368, 822528, 38772864, 2462728320, 189512165376, 18739021676544, 2147802505795584, 305748136551647232, 48922389407097077760, 9484975881651606847488, 2021636445616137313124352, 512419728510195503179825152, 140423343538080744846410121216

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..30

Row n=4 of A341847.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A289198 Number of maximal matchings in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A341848 Number of maximal matchings in the 3 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A341849 Number of maximal matchings in the 4 X n rook graph.

Views

Author

Keywords

Links

Crossrefs