A360875 Array read by antidiagonals: T(m,n) is the number of connected dominating sets in the rook graph K_m X K_n.

1, 3, 3, 7, 9, 7, 15, 39, 39, 15, 31, 177, 325, 177, 31, 63, 783, 2931, 2931, 783, 63, 127, 3369, 26077, 51465, 26077, 3369, 127, 255, 14199, 225459, 894675, 894675, 225459, 14199, 255, 511, 58977, 1901725, 15195897, 30331861, 15195897, 1901725, 58977, 511

Offset

1,2

Links

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

Eric Weisstein's World of Mathematics, Connected Dominating Set

Eric Weisstein's World of Mathematics, Rook Graph

Formula

T(m,n) = (Sum_{i=1..m} binomial(m,i) * A262307(n,i)) + (Sum_{j=1..n} binomial(n,j) * A262307(m,j)) - A262307(m,n).

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

Example

Array begins:
=======================================================
m\n|  1    2      3        4          5           6 ...
---+---------------------------------------------------
1  |  1    3      7       15         31          63 ...
2  |  3    9     39      177        783        3369 ...
3  |  7   39    325     2931      26077      225459 ...
4  | 15  177   2931    51465     894675    15195897 ...
5  | 31  783  26077   894675   30331861  1010163363 ...
6  | 63 3369 225459 15195897 1010163363 66273667449 ...
  ...

Prog

(PARI) \\ S is A183109, T is A262307, U is this sequence.
G(M, N=M)={S=matrix(M, N); T=matrix(M, N); U=matrix(M, N);
for(m=1, M, for(n=1, N,
  S[m, n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
  T[m, n]=S[m, n]-sum(i=1, m-1, sum(j=1, n-1, T[i, j]*S[m-i, n-j]*binomial(m-1, i-1)*binomial(n, j)));
  U[m, n]=sum(i=1, m, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n, j)*T[m, j])-T[m, n] )); U
}
{ my(A=G(7)); for(n=1, #A~, print(A[n, ])) }

Crossrefs

Main diagonal is A289196.

Rows 1..2 are A000225, A360876.

Cf. A287274, A360873.

Sequence in context: A177936 A337975 A143088 * A131036 A331788 A206433

Adjacent sequences: A360872 A360873 A360874 * A360876 A360877 A360878

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 24 2023

Status

approved