|
|
A070968
|
|
Number of cycles in the complete bipartite graph K(n,n).
|
|
9
|
|
|
0, 1, 15, 204, 3940, 113865, 4662231, 256485040, 18226108944, 1623855701385, 177195820499335, 23237493232953516, 3605437233380095620, 653193551573628900289, 136634950180317224866335, 32681589590709963123092160, 8863149183726257535369633856
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Also the number of chordless cycles in the n X n rook graph. - Eric W. Weisstein, Nov 27 2017
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI) for(n=1, 50, print1(sum(k=2, n, binomial(n, k)^2 * k! * (k-1)!/2), ", "))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Sharon Sela (sharonsela(AT)hotmail.com), May 17 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|