A378935 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the rook graph K_m X K_n.

0, 1, 1, 3, 6, 3, 7, 22, 22, 7, 15, 84, 150, 84, 15, 31, 346, 1276, 1276, 346, 31, 63, 1476, 11538, 23214, 11538, 1476, 63, 127, 6322, 102772, 418912, 418912, 102772, 6322, 127, 255, 26844, 890130, 7290534, 14673870, 7290534, 890130, 26844, 255, 511, 112666, 7525876, 123174016, 496484776, 496484776, 123174016, 7525876, 112666, 511

Offset

1,4

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)

Eric Weisstein's World of Mathematics, Minimal Edge Cut.

Eric Weisstein's World of Mathematics, Rook Graph.

Formula

T(m,n) = A360873(m,n) + (2^(m-1) - 1)*(2^(n-1) - 1) - 2^(m*n-1).

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

Example

Array begins:
======================================================
m\n |  1    2      3       4         5           6 ...
----+-------------------------------------------------
  1 |  0    1      3       7        15          31 ...
  2 |  1    6     22      84       346        1476 ...
  3 |  3   22    150    1276     11538      102772 ...
  4 |  7   84   1276   23214    418912     7290534 ...
  5 | 15  346  11538  418912  14673870   496484776 ...
  6 | 31 1476 102772 7290534 496484776 32893769886 ...
  ...

Prog

(PARI) \\ Needs G from A360873.
T(M, N=M) = {G(M, N) + matrix(M, N, m, n, (2^(m-1) - 1)*(2^(n-1) - 1) - 2^(m*n-1))}
{ my(A=T(7)); for(n=1, #A~, print(A[n, ])) }

Crossrefs

Main diagonal is A378936.

Rows 1..2 are A000225(n-1), A378937.

Cf. A143088, A360873, A378932.

Sequence in context: A123146 A016661 A376827 * A201143 A326935 A135003

Adjacent sequences: A378932 A378933 A378934 * A378936 A378937 A378942

Keyword

nonn,tabl,new

Author

Andrew Howroyd, Dec 12 2024

Status

approved