A070968 -id:A070968 - cp's OEIS frontend

A002807 a(n) = Sum_{k=3..n} (k-1)!*C(n,k)/2.

0, 0, 0, 1, 7, 37, 197, 1172, 8018, 62814, 556014, 5488059, 59740609, 710771275, 9174170011, 127661752406, 1904975488436, 30341995265036, 513771331467372, 9215499383109573, 174548332364311563, 3481204991988351553, 72920994844093191553, 1600596371590399671784

Offset: 0

N. J. A. Sloane

Number of cycles in the complete graph on n nodes K_{n}. - Erich Friedman
Number of equations that must be checked to verify reversibility of an n state Markov chain using the Kolmogorov criterion. - Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009
Also the number of paths in the (n-1)-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

E.P.C. Kao, An Introduction to Stochastic Processes, Duxbury Press, 1997, 209-210. [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
P. H. Brill, Chi ho Cheung, Myron Hlynka, Q. Jiang, Reversibility Checking for Markov Chains, Communications on Stochastic Analysis (2018) Vol. 12, No. 2, Art. 2, 129-135.
J. P. Char, Master circuit matrix, Proc. IEE, 115 (1968), 762-770.
F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
Q. Jiang, M. Hlynka, P.H. Brill, C.H. Cheung, Reversibility Checking for Markov Chains, arXiv:1806.10154 [math.PR], 2018.
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, ch. 7. [?Broken link]
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, ch. 7.
M. Scullard, Reversible Markov Chains [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Graph Path

Cf. A284947 (triangle of k-cycle counts in K_n). - Eric W. Weisstein, Apr 06 2017

Cf. A117130, A099198, A099201, A070968.

[&+[Factorial(k-1)*Binomial(n,k) div 2: k in [3..n]]: n in [3..30]]; // Vincenzo Librandi, Mar 06 2016

Table[Sum[((k-1)!Binomial[n,k])/2,{k,3,n}],{n,0,25}] (* Harvey P. Dale, Jun 24 2011 *)
a[n_] := n/4*(2*HypergeometricPFQ[{1, 1, 1 - n}, {2}, -1] - n - 1); a[0] = 0; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Oct 05 2012 *)

a(n)=sum(k=3,n, (k-1)!*binomial(n,k)/2) \\ Charles R Greathouse IV, Feb 08 2017

E.g.f.: (-1/4)*exp(x)*(2*log(1-x)+2*x+x^2). - Vladeta Jovovic, Oct 26 2004
a(n) = (n-1)*(n-2)/2 + n*a(n-1) - (n-1)*a(n-2). - Vladeta Jovovic, Jan 22 2005
a(n) ~ exp(1)/2 * (n-1)! * (1 + 1/n + 2/n^2 + 5/n^3 + 15/n^4 + 52/n^5 + 203/n^6 + 877/n^7 + 4140/n^8 + 21147/n^9 + ...). Coefficients are the Bell numbers (A000110). - Vaclav Kotesovec, Mar 08 2016
For n>2, a(n) = Sum_{k=1..n-2} A000522(k-1)*A000217(k). - Vaclav Kotesovec, Mar 08 2016

A234616 Numbers of undirected cycles in the complete tripartite graph K_{n,n,n}.

Original entry on oeis.org

1, 63, 6705, 1960804, 1271288295, 1541975757831, 3135880743480163, 9904953891455450640, 45915662047529291081589, 299038026557168514632822455, 2642895689915240835222121682301, 30814273315381549790551229559722628

Offset: 1

Eric W. Weisstein, Dec 28 2013

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..100 (terms 1..50 from Andrew Howroyd)
Andrew Howroyd, Formula for the number of cycles
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A234365, A234633, A070968.

Cf. A296546 (cycle polynomial coefficients of K_n,n,n).

Table[(Sum[Binomial[n, k] Binomial[n, i + p] Binomial[n, j + p] Binomial[k, i] Binomial[k - i, j] (k - 1)! (i + p)! (j + p)! 2^(k - i - j) Binomial[p + i + j - 1, k - 1], {k, n}, {i, 0, k}, {j, 0, k - i}, {p, k - i - j, n}] + Sum[Binomial[n, k]^2 k! (k - 1)!, {k, 2, n}])/2 - n^2, {n, 10}] (* Eric W. Weisstein, May 26 2017 *)
Table[(n^2 (HypergeometricPFQ[{1, 1, 1 - n, 1 - n}, {2}, 1] - 3) + Sum[2^(k - i - j) Binomial[k, i] Binomial[k - i, j] Binomial[n, k] Binomial[n, i + p] Binomial[n, j + p] Binomial[i + j + p - 1, k - 1] (k - 1)! (i + p)! (j + p)!, {k, n}, {i, 0, k}, {j, 0, k - i}, {p, k - i - j, n}])/2, {n, 10}] (* Eric W. Weisstein, May 25 2023 *)

c(n,k,i,j,p) = {binomial(n,k)*binomial(n,i+p)*binomial(n,j+p)*binomial(k,i)*binomial(k-i,j)*(k-1)!*(i+p)!*(j+p)!*2^(k-i-j)*binomial(p+i+j-1,k-1)}
a(n)={(sum(k=1,n,sum(i=0,k,sum(j=0,k-i,sum(p=k-i-j,n, c(n,k,i,j,p) )))) + sum(k=2,n,binomial(n,k)^2*k!*(k-1)!))/2 - n^2} \\ Andrew Howroyd, May 25 2017

from sympy import binomial, factorial
def c(n, k, i, j, p): return binomial(n, k)*binomial(n, i + p)*binomial(n, j + p)*binomial(k, i)*binomial(k - i, j)*factorial(k - 1)*factorial(i + p)*factorial(j + p)*2**(k - i - j)*binomial(p + i + j - 1, k - 1)
def a(n): return (sum([sum([sum([sum([c(n, k, i, j, p) for p in range(k - i - j, n + 1)]) for j in range(k - i + 1)]) for i in range(k + 1)]) for k in range(1, n + 1)]) + sum(binomial(n, k)**2*factorial(k)*factorial(k - 1) for k in range(2, n + 1)))/2 - n**2
print([a(k) for k in range(1, 13)]) # Indranil Ghosh, Aug 14 2017, after PARI

Row sums of A296546.

a(n) ~ sqrt(3*Pi) * 2^(3*n - 1/2) * n^(3*n - 1/2) / exp(3*n - 3/2). - Vaclav Kotesovec, Feb 17 2024

a(7)-a(12) from Andrew Howroyd, May 25 2017

A288035 Number of (undirected) paths in the complete bipartite graph K_n,n.

Original entry on oeis.org

1, 12, 135, 2224, 55725, 2006316, 98309827, 6291829440, 509638185369, 50963818537900, 6166622043087231, 887993574204562992, 150070914040571147845, 29413899151951944980364, 6618127309189187620585275, 1694240591152432030869834496, 489635530843052856921382174257

Offset: 1

Eric W. Weisstein, Jun 04 2017

nonn

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

Main diagonal of A307027 and A360850.

Cf. A070968, A048617, A010790.

Table[Sum[(n!)^2/((n - Ceiling[k/2])! (n - Floor[k/2])!), {k, 2, 2 n}], {n, 20}] (* Eric W. Weisstein, Jun 13 2017 *)
Table[n!^2 (BesselI[0, 2] + BesselI[1, 2] - HypergeometricPFQRegularized[{1}, {1 + n, 1 + n}, 1]) - n HypergeometricPFQ[{1}, {n, 1 + n}, 1], {n, 20}] // FunctionExpand (* Eric W. Weisstein, Jun 13 2017 *)

a(n) = sum(k=2, 2*n, n!^2/((n-(k+1)\2)!*(n-k\2)!)); \\ Andrew Howroyd, Jun 10 2017

a(n) = n!^2*sum(k=0, n-1, (1 + k)/(k!)^2) \\ Andrew Howroyd, Feb 24 2023

a(n) = Sum_{k=2..2*n} n!^2/((n-ceiling(k/2))!*(n-floor(k/2))!). - Andrew Howroyd, Jun 10 2017

a(n) = n!^2 * Sum_{k=0..n-1} (1 + k)/(k!^2). - Andrew Howroyd, Feb 24 2023

Terms a(8) and beyond from Andrew Howroyd, Jun 10 2017

A291909 Triangle read by rows: T(n,k) is the coefficient of x^(2*k) in the cycle polynomial of the complete bipartite graph K_{n,n}, 1 <= k <= n.

Original entry on oeis.org

0, 0, 1, 0, 9, 6, 0, 36, 96, 72, 0, 100, 600, 1800, 1440, 0, 225, 2400, 16200, 51840, 43200, 0, 441, 7350, 88200, 635040, 2116800, 1814400, 0, 784, 18816, 352800, 4515840, 33868800, 116121600, 101606400, 0, 1296, 42336, 1143072, 22861440, 304819200, 2351462400, 8230118400, 7315660800

Offset: 1

Eric W. Weisstein, Sep 05 2017

Also the coefficients of x^(2*k) in the chordless cycle polynomial of the n X n rook graph. - Eric W. Weisstein, Feb 21 2018

			Cycle polynomials are
        0
      x^4
    9 x^4 +   6 x^6
   36 x^4 +  96 x^6 +   72 x^8
  100 x^4 + 600 x^6 + 1800 x^8 + 1440 x^10
  ...
so the first few rows are
  0;
  0,  1;
  0,  9,  6;
  0, 36, 96, 72;
  ...

Pontus von Brömssen, Rows n = 1..100, flattened (rows n = 1..60 from Vincenzo Librandi).
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Cycle Polynomial

Cf. A070968 (row sums), A010796 (main diagonal).

CoefficientList[Table[Sum[Binomial[n, k]^2 k! (k - 1)! x^k, {k, 2, n}]/2, {n, 10}], x] // Flatten
Join[{0}, CoefficientList[Table[n^2 (HypergeometricPFQ[{1, 1, 1 - n, 1 - n}, {2}, x] - 1)/2, {n, 2, 10}], x]] // Flatten (* Eric W. Weisstein, Feb 21 2018 *)

T(n, k) = if(k>1, binomial(n, k)^2*k!*(k - 1)!/2, 0) \\ Andrew Howroyd, Apr 29 2018

T(n, k) = binomial(n, k)^2*k!*(k - 1)!/2 for k > 1.

Terms T(n,0) for n >= 3 deleted (in order to have a regular triangle) by Pontus von Brömssen, Sep 06 2022

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

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 3, 3, 0, 0, 6, 15, 6, 0, 0, 10, 42, 42, 10, 0, 0, 15, 90, 204, 90, 15, 0, 0, 21, 165, 660, 660, 165, 21, 0, 0, 28, 273, 1650, 3940, 1650, 273, 28, 0, 0, 36, 420, 3486, 15390, 15390, 3486, 420, 36, 0, 0, 45, 612, 6552, 45150, 113865, 45150, 6552, 612, 45, 0

Offset: 1

Andrew Howroyd, Feb 23 2023

Also, T(m,n) is the number of chordless cycles of length >= 4 in the m X n rook graph.

			Array begins:
========================================================
m\n| 1  2   3    4      5       6        7         8 ...
---+----------------------------------------------------
1  | 0  0   0    0      0       0        0         0 ...
2  | 0  1   3    6     10      15       21        28 ...
3  | 0  3  15   42     90     165      273       420 ...
4  | 0  6  42  204    660    1650     3486      6552 ...
5  | 0 10  90  660   3940   15390    45150    109480 ...
6  | 0 15 165 1650  15390  113865   526155   1776180 ...
7  | 0 21 273 3486  45150  526155  4662231  24864588 ...
8  | 0 28 420 6552 109480 1776180 24864588 256485040 ...
  ...
Lower half of array as triangle T(n,k) for 1 <= k <= n begins:
  0;
  0,  1;
  0,  3,  15;
  0,  6,  42,  204;
  0, 10,  90,  660,  3940;
  0, 15, 165, 1650, 15390, 113865;
  0, 21, 273, 3486, 45150, 526155, 4662231;
  ...

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

Rows 1..3 are A000004, A000217(n-1), A059270(n-1).
Main diagonal is A070968.
Cf. A269562, A286418, A360850 (paths), A360853.

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

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

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

A303542 Number of chordless cycles in the n X n white bishop graph.

Original entry on oeis.org

0, 1, 3, 19, 97, 678, 5098, 52170, 582342, 8221455, 125339157, 2312227461, 45664819407, 1056675718876, 26022340062564, 734233350312484, 21939269071805596, 738213020202917421, 26196923530426606903, 1032994592794340235015, 42808941242555092330701

Offset: 2

Eric W. Weisstein, Apr 25 2018

nonn

The chordless cycles in a bishop graph are those cycles which have at most one edge on any diagonal or antidiagonal. - Andrew Howroyd, Apr 29 2018

Andrew Howroyd, Table of n, a(n) for n = 2..200
Eric Weisstein's World of Mathematics, Chordless Cycle.
Eric Weisstein's World of Mathematics, White Bishop Graph.

Cf. A070968.

Cf. A370210 (black bishop), A370224 (bishop).

SafeMat(m)={my(d=matsize(m));((j,k)->if(j>0&&j<=d[1]&&k>0&&k<=d[2], m[j,k]))}
CC(sig,x)={my(v=SafeMat([;]), total=0);
forstep(i=#sig, 2, -1, my(t=sig[i]);
   v=SafeMat(matrix(t, t\2, j, k, v(j,k) + x*(if(j==2&&k==1, binomial(t,2)) + v(j-2,k-1)*binomial(t-j+2,2) + v(j-1,k)*2*k*(t-j+1) + v(j,k+1)*2*k*(k+1))));
   total+=sum(j=1,t,v(j,1)) );
total}
Bishop(n, white)=vector(n-if(white, n%2, 1-n%2), i, n-i+if(white, 1-i%2, i%2));
a(n) = CC(Bishop(n,1),1) \\ Andrew Howroyd, Apr 29 2018

\\ CCGenRook, Bishop defined in A370224 (slightly faster version).
a(n) = subst(CCGenRook(Bishop(n,1)), y, 1) \\ Andrew Howroyd, May 27 2025

For n > 1, a(n) = A370224(n) - A370210(n).

a(8)-a(22) from Andrew Howroyd, Apr 29 2018

A360854 Number of induced cycles in the n X n rook graph.

Original entry on oeis.org

0, 1, 21, 236, 4040, 114105, 4662721, 256485936, 18226110456, 1623855703785, 177195820502965, 23237493232958796, 3605437233380103056, 653193551573628910481, 136634950180317224879985, 32681589590709963123110080, 8863149183726257535369656976

Offset: 1

Andrew Howroyd, Feb 24 2023

nonn

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

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

Main diagonal of A360853.

Cf. A070968, A234624, A288961, A360852.

a(n) = 2*n*binomial(n,3) + sum(k=2, n, binomial(n,k)^2 * k! * (k-1)!)/2

a(n) = A288961(n) + A070968(n).

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

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

A002807 a(n) = Sum_{k=3..n} (k-1)!*C(n,k)/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A234616 Numbers of undirected cycles in the complete tripartite graph K_{n,n,n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A288035 Number of (undirected) paths in the complete bipartite graph K_n,n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A291909 Triangle read by rows: T(n,k) is the coefficient of x^(2*k) in the cycle polynomial of the complete bipartite graph K_{n,n}, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303542 Number of chordless cycles in the n X n white bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A360854 Number of induced cycles in the n X n rook graph.

Views

Author

Keywords

Comments

Links