A360849 -id:A360849 - cp's OEIS frontend

A070968 Number of cycles in the complete bipartite graph K(n,n).

0, 1, 15, 204, 3940, 113865, 4662231, 256485040, 18226108944, 1623855701385, 177195820499335, 23237493232953516, 3605437233380095620, 653193551573628900289, 136634950180317224866335, 32681589590709963123092160, 8863149183726257535369633856

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), May 17 2002

nonn

Also the number of chordless cycles in the n X n rook graph. - Eric W. Weisstein, Nov 27 2017

Andrew Howroyd, Table of n, a(n) for n = 1..100
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

Row sums of A291909.
Main diagonal of A360849.
Cf. A002807, A068087, A288035.

seq(simplify((1/4)*hypergeom([1, 2, 2-n, 2-n], [3], 1)*(n-1)^2*n^2), n=1..20); # Robert Israel, Jan 09 2018

Table[Sum[Binomial[n, k]^2*k!*(k - 1)!, {k, 2, n}]/2, {n, 1, 17}]
Table[n^2 (HypergeometricPFQ[{1, 1, 1 - n, 1 - n}, {2}, 1] - 1)/2, {n, 20}] (* Eric W. Weisstein, Dec 14 2017 *)

for(n=1,50,print1(sum(k=2,n,binomial(n,k)^2 * k! * (k-1)!/2),","))

a(n) = Sum_{k=2..n} C(n,k)^2 * k! * (k-1)! / 2.
Recurrence: (n-2)^2*(2*n^3 - 19*n^2 + 58*n - 59)*a(n) = 2*(2*n^7 - 31*n^6 + 200*n^5 - 700*n^4 + 1442*n^3 - 1764*n^2 + 1205*n - 363)*a(n-1) - (n-1)^2*(2*n^7 - 35*n^6 + 266*n^5 - 1139*n^4 + 2962*n^3 - 4671*n^2 + 4130*n - 1578)*a(n-2) + 2*(n-2)^2*(n-1)^2*(2*n^5 - 26*n^4 + 134*n^3 - 342*n^2 + 431*n - 217)*a(n-3) - (n-3)^2*(n-2)^2*(n-1)^2*(2*n^3 - 13*n^2 + 26*n - 18)*a(n-4). - Vaclav Kotesovec, Mar 08 2016
a(n) ~ c * n! * (n-1)!, where c = BesselI(0,2)/2 = 1.1397926511680336337186... . - Vaclav Kotesovec, Mar 08 2016

More terms from Benoit Cloitre and Robert G. Wilson v, May 20 2002

a(16)-a(17) from Andrew Howroyd, Jan 08 2018

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

Original entry on oeis.org

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

cp's OEIS Frontend

A070968 Number of cycles in the complete bipartite graph K(n,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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