OFFSET
3,1
COMMENTS
In graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices is denoted by K_n. The number of simple cycles through a vertex of K_n equals A038154(n-1). See A000522 for the number of paths between a pair of distinct vertices of K_n.
LINKS
Mehdi Hassani, Counting and computing by e
FORMULA
a(n) = floor(n!*e) - floor((n-1)!*e) - 2*n + 1 [Hassani]. a(n) = 2 - 2*n + (n-1)*(n-1)!*sum {k = 0..n-1} 1/k!. E.g.f.: sum {n = 0..inf} a(n+3)*x^n/n! = (6+12*x-21*x^2+8*x^3+3*x^4-2*x^5)*exp(x)/(1-x)^4 = 6 + 42*x + 252*x^2/2! + ... .
EXAMPLE
a(4) = 42. In the complete graph K_4 with vertex set {A,B,C,D} there are 12 simple cycles at the vertex A, namely the six 3-cycles ABCA, ABDA, ACBA, ACDA, ADBA and ADCA and the six 4-cycles ABCDA, ABDCA, ACBDA, ACDBA, ADBCA and ADCBA. The sum of the lengths of these cycles is 6*3 + 6*4 = 42.
MAPLE
a:= n -> 2 - 2*n + (n-1)*(n-1)!*add(1/k!, k = 0..n-1): seq(a(n), n = 3..22);
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Peter Bala, Jul 09 2008
STATUS
approved