A360851 -id:A360851 - cp's OEIS frontend

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

1, 3, 3, 6, 12, 6, 10, 33, 33, 10, 15, 72, 135, 72, 15, 21, 135, 438, 438, 135, 21, 28, 228, 1140, 2224, 1140, 228, 28, 36, 357, 2511, 8850, 8850, 2511, 357, 36, 45, 528, 4893, 27480, 55725, 27480, 4893, 528, 45, 55, 747, 8700, 70462, 265665, 265665, 70462, 8700, 747, 55

Offset: 1

Andrew Howroyd, Feb 23 2023

T(m,n) is the number of induced paths including zero length paths in the m X n rook graph. This is also the number of induced trees in these graphs since these are the only induced trees.

			Array begins:
===================================================
m\n|  1   2    3     4      5        6        7 ...
---+-----------------------------------------------
1  |  1   3    6    10     15       21       28 ...
2  |  3  12   33    72    135      228      357 ...
3  |  6  33  135   438   1140     2511     4893 ...
4  | 10  72  438  2224   8850    27480    70462 ...
5  | 15 135 1140  8850  55725   265665   962010 ...
6  | 21 228 2511 27480 265665  2006316 11158203 ...
7  | 28 357 4893 70462 962010 11158203 98309827 ...
   ...

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

Main diagonal is A288035.
Rows 1..2 are A000217, A054602.
Cf. A360849 (cycles), A360851.

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

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

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

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

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 4, 5, 5, 4, 10, 14, 21, 14, 10, 20, 30, 58, 58, 30, 20, 35, 55, 125, 236, 125, 55, 35, 56, 91, 231, 720, 720, 231, 91, 56, 84, 140, 385, 1754, 4040, 1754, 385, 140, 84, 120, 204, 596, 3654, 15550, 15550, 3654, 596, 204, 120

Offset: 1

Andrew Howroyd, Feb 24 2023

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

			Array begins:
==========================================================
m\n|  1   2   3    4      5       6        7         8 ...
---+------------------------------------------------------
1  |  0   0   1    4     10      20       35        56 ...
2  |  0   1   5   14     30      55       91       140 ...
3  |  1   5  21   58    125     231      385       596 ...
4  |  4  14  58  236    720    1754     3654      6808 ...
5  | 10  30 125  720   4040   15550    45395    109840 ...
6  | 20  55 231 1754  15550  114105   526505   1776676 ...
7  | 35  91 385 3654  45395  526505  4662721  24865260 ...
8  | 56 140 596 6808 109840 1776676 24865260 256485936 ...
  ...

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

Main diagonal is A360854.
Rows 1..2 are A000292(n-2), A000330(n-1).
Cf. A360196, A360849, A360851 (induced paths), A360855 (triangles).

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

T(m,n) = A360849(m,n) + A360855(m,n).

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

A360852 Number of induced paths in the n X n rook graph.

Original entry on oeis.org

0, 8, 126, 2208, 55700, 2006280, 98309778, 6291829376, 509638185288, 50963818537800, 6166622043087110, 887993574204562848, 150070914040571147676, 29413899151951944980168, 6618127309189187620585050, 1694240591152432030869834240, 489635530843052856921382173968

Offset: 1

Andrew Howroyd, Feb 24 2023

nonn

Paths of length zero are not counted here.

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

Main diagonal of A360851.

Cf. A000290, A286189 (induced connected subgraphs), A288035, A288967.

a(n) = {sum(k=0, n-1, n!^2*(1 + k)/(k!^2)) - n^2}

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

a(n) = A288035(n) - n^2 = A288035(n) - A000290(n).

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

Original entry on oeis.org

0, 1, 1, 6, 12, 6, 30, 129, 129, 30, 160, 1984, 4536, 1984, 160, 975, 45945, 310542, 310542, 45945, 975, 6846, 1524156, 38298270, 111933456, 38298270, 1524156, 6846

Offset: 1

Andrew Howroyd, Feb 25 2023

			Array begins:
==============================================
m\n|   1     2        3         4        5 ...
---+------------------------------------------
1  |   0     1        6        30      160 ...
2  |   1    12      129      1984    45945 ...
3  |   6   129     4536    310542 38298270 ...
4  |  30  1984   310542 111933456 ...
5  | 160 45945 38298270 ...
  ...

Eric Weisstein's World of Mathematics, Graph Path.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A288967.
Rows 1..2 are A038155, A360878.
Cf. A269562, A269565, A286418, A360851, A360855.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A360853 Array read by antidiagonals: T(m,n) is the number of induced cycles 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

A360852 Number of induced paths in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs