A360854 -id:A360854 - cp's OEIS frontend

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

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

A361185 Number of chordless cycles in the n X n rook complement graph.

Original entry on oeis.org

0, 0, 15, 264, 1700, 6900, 21315, 54880, 123984, 253800, 480975, 856680, 1450020, 2351804, 3678675, 5577600, 8230720, 11860560, 16735599, 23176200, 31560900, 42333060, 56007875, 73179744, 94530000, 120835000, 152974575, 191940840, 238847364, 294938700

Offset: 1

Eric W. Weisstein, Mar 03 2023

nonn

Using the convention that chordless cycles have length >= 4.

All chordless cycles in the rook complement graph have a cycle length of either 4 or 6. - Andrew Howroyd, Mar 03 2023

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Rook Complement Graph
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A070968, A360854.

Table[(n - 2) (n - 1)^2 n^2 (6 n - 13)/12, {n, 20}]
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 0, 15, 264, 1700, 6900, 21315}, 20]
CoefficientList[Series[x^2 (15 + 159 x + 167 x^2 + 19 x^3)/(1 - x)^7, {x, 0, 20}], x]

a(n) = 2*binomial(n,2)*binomial(n,3) + 9*binomial(n,3)^2 + 12*binomial(n,4)*binomial(n,2) \\ Andrew Howroyd, Mar 03 2023

a(n) = 2*binomial(n,2)*binomial(n,3) + 9*binomial(n,3)^2 + 12*binomial(n,4)*binomial(n,2). - Andrew Howroyd, Mar 03 2023
a(n) = (n - 2)*(n - 1)^2*n^2*(6*n - 13)/12.
a(n) = 7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7).
G.f.: x^3*(15+159*x+167*x^2+19*x^3)/(1-x)^7.

Terms a(8) and beyond from Andrew Howroyd, Mar 03 2023

cp's OEIS Frontend

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