%I M4420 N1867 #65 Sep 08 2022 08:44:31
%S 0,0,0,1,7,37,197,1172,8018,62814,556014,5488059,59740609,710771275,
%T 9174170011,127661752406,1904975488436,30341995265036,513771331467372,
%U 9215499383109573,174548332364311563,3481204991988351553,72920994844093191553,1600596371590399671784
%N a(n) = Sum_{k=3..n} (k-1)!*C(n,k)/2.
%C Number of cycles in the complete graph on n nodes K_{n}. - _Erich Friedman_
%C 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
%C Also the number of paths in the (n-1)-triangular honeycomb rook graph. - _Eric W. Weisstein_, Jul 14 2017
%D E.P.C. Kao, An Introduction to Stochastic Processes, Duxbury Press, 1997, 209-210. [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002807/b002807.txt">Table of n, a(n) for n = 0..100</a>
%H P. H. Brill, Chi ho Cheung, Myron Hlynka, Q. Jiang, <a href="https://digitalcommons.lsu.edu/cosa/vol12/iss2/2">Reversibility Checking for Markov Chains</a>, Communications on Stochastic Analysis (2018) Vol. 12, No. 2, Art. 2, 129-135.
%H J. P. Char, <a href="http://dx.doi.org/10.1049/piee.1968.0138">Master circuit matrix</a>, Proc. IEE, 115 (1968), 762-770.
%H F. C. Holroyd and W. J. G. Wingate, <a href="http://dx.doi.org/10.1016/S0012-365X(85)80003-0">Cycles in the complement of a tree or other graph</a>, Discrete Math., 55 (1985), 267-282.
%H Q. Jiang, M. Hlynka, P.H. Brill, C.H. Cheung, <a href="https://arxiv.org/abs/1806.10154">Reversibility Checking for Markov Chains</a>, arXiv:1806.10154 [math.PR], 2018.
%H P. Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, ch. 7. [?Broken link]
%H P. Pollack, <a href="http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, ch. 7.
%H M. Scullard, <a href="http://www.math.ucsd.edu/~williams/courses/m28908/scullardMath289_Reversibility.pdf"> Reversible Markov Chains</a> [From Qian Jiang (jiang1h(AT)uwindsor.ca), Jun 08 2009]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphPath.html">Graph Path</a>
%F E.g.f.: (-1/4)*exp(x)*(2*log(1-x)+2*x+x^2). - _Vladeta Jovovic_, Oct 26 2004
%F a(n) = (n-1)*(n-2)/2 + n*a(n-1) - (n-1)*a(n-2). - _Vladeta Jovovic_, Jan 22 2005
%F 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
%F For n>2, a(n) = Sum_{k=1..n-2} A000522(k-1)*A000217(k). - _Vaclav Kotesovec_, Mar 08 2016
%t Table[Sum[((k-1)!Binomial[n,k])/2,{k,3,n}],{n,0,25}] (* _Harvey P. Dale_, Jun 24 2011 *)
%t 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 *)
%o (Magma) [&+[Factorial(k-1)*Binomial(n,k) div 2: k in [3..n]]: n in [3..30]]; // _Vincenzo Librandi_, Mar 06 2016
%o (PARI) a(n)=sum(k=3,n, (k-1)!*binomial(n,k)/2) \\ _Charles R Greathouse IV_, Feb 08 2017
%Y Cf. A284947 (triangle of k-cycle counts in K_n). - _Eric W. Weisstein_, Apr 06 2017
%Y Cf. A117130, A099198, A099201, A070968.
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_