A360853 -id:A360853 - cp's OEIS frontend

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

0, 0, 0, 1, 0, 1, 4, 2, 2, 4, 10, 8, 6, 8, 10, 20, 20, 16, 16, 20, 20, 35, 40, 35, 32, 35, 40, 35, 56, 70, 66, 60, 60, 66, 70, 56, 84, 112, 112, 104, 100, 104, 112, 112, 84, 120, 168, 176, 168, 160, 160, 168, 176, 168, 120, 165, 240, 261, 256, 245, 240, 245, 256, 261, 240, 165

Offset: 1

Andrew Howroyd, Feb 24 2023

A triangle is a clique of size 3. Also, a 3-cycle.

			Array begins:
=======================================
m\n|  1   2   3   4   5   6   7   8 ...
---+-----------------------------------
1  |  0   0   1   4  10  20  35  56 ...
2  |  0   0   2   8  20  40  70 112 ...
3  |  1   2   6  16  35  66 112 176 ...
4  |  4   8  16  32  60 104 168 256 ...
5  | 10  20  35  60 100 160 245 360 ...
6  | 20  40  66 104 160 240 350 496 ...
7  | 35  70 112 168 245 350 490 672 ...
8  | 56 112 176 256 360 496 672 896 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A288961.
Rows n=1..3 are A000292(n-2), A007290, A060354.
Cf. A286418, A360853.

T(m, n) = m*binomial(n,3) + n*binomial(m,3)

T(m,n) = m*binomial(n,3) + n*binomial(m,3).

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

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.

Original entry on oeis.org

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

Andrew Howroyd, Feb 24 2023

			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 ...
  ...

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.

Main diagonal is A286189.
Rows 1..2 are A000225, A360874.
Cf. A360850, A360851, A360853, A360875.

\\ 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,])) }

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).

A360849 Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 3, 3, 0, 0, 6, 15, 6, 0, 0, 10, 42, 42, 10, 0, 0, 15, 90, 204, 90, 15, 0, 0, 21, 165, 660, 660, 165, 21, 0, 0, 28, 273, 1650, 3940, 1650, 273, 28, 0, 0, 36, 420, 3486, 15390, 15390, 3486, 420, 36, 0, 0, 45, 612, 6552, 45150, 113865, 45150, 6552, 612, 45, 0

Offset: 1

Andrew Howroyd, Feb 23 2023

Also, T(m,n) is the number of chordless cycles of length >= 4 in the m X n rook graph.

			Array begins:
========================================================
m\n| 1  2   3    4      5       6        7         8 ...
---+----------------------------------------------------
1  | 0  0   0    0      0       0        0         0 ...
2  | 0  1   3    6     10      15       21        28 ...
3  | 0  3  15   42     90     165      273       420 ...
4  | 0  6  42  204    660    1650     3486      6552 ...
5  | 0 10  90  660   3940   15390    45150    109480 ...
6  | 0 15 165 1650  15390  113865   526155   1776180 ...
7  | 0 21 273 3486  45150  526155  4662231  24864588 ...
8  | 0 28 420 6552 109480 1776180 24864588 256485040 ...
  ...
Lower half of array as triangle T(n,k) for 1 <= k <= n begins:
  0;
  0,  1;
  0,  3,  15;
  0,  6,  42,  204;
  0, 10,  90,  660,  3940;
  0, 15, 165, 1650, 15390, 113865;
  0, 21, 273, 3486, 45150, 526155, 4662231;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Chordless Cycle.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Graph Cycle.
Eric Weisstein's World of Mathematics, Rook Graph.

Rows 1..3 are A000004, A000217(n-1), A059270(n-1).
Main diagonal is A070968.
Cf. A269562, A286418, A360850 (paths), A360853.

T(m,n) = sum(j=2, min(m,n), binomial(m,j)*binomial(n,j)*j!*(j-1)!/2)

T(m,n) = Sum_{j=2..min(m,n)} binomial(m,j)*binomial(n,j)*j!*(j-1)!/2.

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

A360854 Number of induced cycles in the n X n rook graph.

Original entry on oeis.org

0, 1, 21, 236, 4040, 114105, 4662721, 256485936, 18226110456, 1623855703785, 177195820502965, 23237493232958796, 3605437233380103056, 653193551573628910481, 136634950180317224879985, 32681589590709963123110080, 8863149183726257535369656976

Offset: 1

Andrew Howroyd, Feb 24 2023

nonn

Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4). See A070968 for the version that excludes triangles.

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Rook Graph.
Wikipedia, Cycle (graph theory).

Main diagonal of A360853.

Cf. A070968, A234624, A288961, A360852.

a(n) = 2*n*binomial(n,3) + sum(k=2, n, binomial(n,k)^2 * k! * (k-1)!)/2

a(n) = A288961(n) + A070968(n).

a(n) = 2*n*binomial(n,3) + Sum_{k=2..n} binomial(n,k)^2 * k! * (k-1)! / 2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A360849 Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A360854 Number of induced cycles in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula