A006184 Number of cycles in the complement of a path.

0, 0, 0, 0, 0, 3, 23, 153, 1077, 8490, 75234, 742710, 8084990, 96192405, 1241588865, 17277139383, 257810397243, 4106342523108, 69531388662932, 1247182219179900, 23622547999002444, 471129863595453495, 9868783491120925755, 216617163296681315685, 4971829898824570284305, 119096935551493905531438, 2972224576868227286710038, 77153543251103295197353938

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Number of cycles in K_n - P_n. - Sean A. Irvine, Jan 17 2017

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
• Eric Weisstein's World of Mathematics, Graph Cycle
• Eric Weisstein's World of Mathematics, Path Complement Graph

Crossrefs

Cf. A302734.

Programs

Mathematica

Array[(1/2)Sum[Sum[Sum[(-1)^(k - i) (i - 1)!*2^j*Binomial[# + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {j, 0, k - i}], {i, k}], {k, 3, #}] &, 28, 0] (* Michael De Vlieger, Apr 21 2018 *)
Table[Sum[(-1)^(k - i) Gamma[i] 2^j Binomial[n + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {k, 3, n}, {i, k}, {j, 0, k - i}]/2, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)

PARI

a(n)={sum(k=3, n, sum(i=1, k, sum(j=0, min(i,k-i), (-1)^(k-i)*(i-1)!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j))))/2} \\ Andrew Howroyd, Apr 21 2018

Formula

a(n) = (1/2)*Sum_{k=3..n} Sum_{i=1..k} Sum_{j=0..k-i} (-1)^(k-i)*(i-1)!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j). - Andrew Howroyd, Apr 21 2018

a(n) ~ (n-1)! / (2*exp(1)). - Vaclav Kotesovec, Apr 22 2018

Extensions

a(0)-a(3) prepended, a(4) corrected, and more terms from Sean A. Irvine, Jan 17 2017