A341848 -id:A341848 - cp's OEIS frontend

A341847 Array read by antidiagonals: T(n,m) is the number of maximal 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, 10, 10, 3, 1, 1, 15, 40, 84, 40, 15, 1, 1, 15, 296, 852, 852, 296, 15, 1, 1, 105, 1576, 11580, 22368, 11580, 1576, 105, 1, 1, 105, 15352, 197640, 822528, 822528, 197640, 15352, 105, 1, 1, 945, 104000, 4314240, 38772864, 84961440, 38772864, 4314240, 104000, 945, 1

Offset: 0

Andrew Howroyd, Feb 21 2021

			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     10       40         296          1576 ...
  3 | 1  3   10     84      852       11580        197640 ...
  4 | 1  3   40    852    22368      822528      38772864 ...
  5 | 1 15  296  11580   822528    84961440   12002446080 ...
  6 | 1 15 1576 197640 38772864 12002446080 5429866337280 ...
  ...

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

Rows n=1..4 are A133221(n+1), A281433, A341848, A341849.
Main diagonal is A289198.
Cf. A270227 (matchings), A297471, A341850 (maximum matchings).

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

A341851 Number of maximum matchings in the 3 X n rook graph.

Original entry on oeis.org

1, 3, 4, 72, 132, 7020, 17280, 1920240, 6022800, 1154366640, 4421511360, 1303028052480, 5906331224640, 2481613890275520, 13003380449579520, 7385997122881977600, 43944212734316294400, 32440254625217626387200, 216088204725662645376000

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

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

Row n=3 of A341850.

Cf. A341502, A341848.

a(n)={my(v=vector((n+1)\2+1, i, i--; (2*i)!/(2^i*i!))); if(n%2,3,1)*sum(i=0, n\2, sum(j=0, n\2, sum(k=abs(i-j), min(i+j, n-i-j), n!/((i+k-j)!*(i+j-k)!*(n-i-j-k)!*(j+k-i)!)*v[1+(n+1)\2-i]*v[1+j]*v[1+k] )))} \\ Andrew Howroyd, Mar 14 2021

A341502 Number of matchings in the 3 X n rook graph.

Original entry on oeis.org

1, 4, 32, 370, 5950, 122984, 3175696, 98815588, 3638940860, 155377163440, 7598445388096, 420034502219864, 26014375783223272, 1788772035008337760, 135644687161742899520, 11268192704027639350384, 1020100484786824631520016, 100126060947226759050509888

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

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

Row 3 of A270227.

Cf. A000085, A341848, A341851.

\\ here b(n) is A000085.
b(n)={sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
a(n)={my(v=vector(n+1, i, b(i-1))); sum(i=0,n, sum(j=0, n-i, sum(k=0, n-i-j, n!/(i!*j!*k!*(n-i-j-k)!)*v[1+n-i-j]*v[1+n-i-k]*v[1+n-j-k] )))}

a(n) = Sum{i,j,k>=0, i+j+k<=n} n!/(i!*j!*k!*(n-i-j-k)!) * A000085(n-i-j) * A000085(n-i-k) * A000085(n-j-k).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A341851 Number of maximum matchings in the 3 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A341502 Number of matchings in the 3 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula