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,12

Comments

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

Links

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

Formula

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

Example

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

Crossrefs

Rows n=1..4 are A133221(n+1), A081919, A341851, A341852.

Main diagonal is A289197.

Cf. A270227 (matchings), A286070, A341847 (maximal matchings).

Sequence in context: A106693 A107335 A375782 * A341847 A200223 A394690

Adjacent sequences: A341847 A341848 A341849 * A341851 A341852 A341853

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 21 2021

Status

approved