|
|
A360853
|
|
Array read by antidiagonals: T(m,n) is the number of induced cycles in the rook graph K_m X K_n.
|
|
5
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,7
|
|
COMMENTS
|
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.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Rook Graph.
|
|
FORMULA
|
T(m,n) = T(n,m).
|
|
EXAMPLE
|
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 ...
...
|
|
PROG
|
(PARI) 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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|