A360873 Array read by antidiagonals: T(m,n) is the number of (non-null) connected induced subgraphs in the rook graph K_m X K_n.

1, 3, 3, 7, 13, 7, 15, 51, 51, 15, 31, 205, 397, 205, 31, 63, 843, 3303, 3303, 843, 63, 127, 3493, 27877, 55933, 27877, 3493, 127, 255, 14451, 233751, 943095, 943095, 233751, 14451, 255, 511, 59485, 1938517, 15678925, 31450861, 15678925, 1938517, 59485, 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, Rook Graph.

Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph.

Formula

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

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   13     51      205        843        3493 ...
3  |  7   51    397     3303      27877      233751 ...
4  | 15  205   3303    55933     943095    15678925 ...
5  | 31  843  27877   943095   31450861  1033355223 ...
6  | 63 3493 233751 15678925 1033355223 67253507293 ...
  ...

Prog

(PARI) \\ S is A183109, T is A262307, U is this sequence.
G(M, N=M)={ my(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, sum(j=1, n, binomial(m, i)*binomial(n, j)*T[i, j])) )); U
}
{ my(A=G(7)); for(n=1, #A~, print(A[n, ])) }

Crossrefs

Main diagonal is A286189.

Rows 1..2 are A000225, A360874.

Cf. A360850, A360851, A360853, A360875.

Sequence in context: A219211 A088859 A177942 * A116880 A051123 A096188

Adjacent sequences: A360870 A360871 A360872 * A360874 A360875 A360876

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 24 2023

Status

approved