A360875 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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 A375404

Adjacent sequences: A360872 A360873 A360874 * A360876 A360877 A360878

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Feb 24 2023

STATUS

approved