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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

References

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

Links

• 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

Crossrefs

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

Cf. A117130, A099198, A099201, A070968.

Programs

Magma

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

Mathematica

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

PARI

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

Formula

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