|
| |
|
|
A141834
|
|
Sum of the lengths of the cycles at a vertex of the complete graph K_n.
|
|
1
| |
|
|
6, 42, 252, 1620, 11730, 95886, 876792, 8877672, 98640990, 1193556210, 15624736116, 220048367292, 3317652307242, 53319412081110, 909984632851440, 16436597430879696, 313262209859119542, 6282647653285675962
(list; graph; refs; listen; history; internal format)
|
|
|
|
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
| Cf. A000522, A038154.
Sequence in context: A082139 A180286 A054613 * A180355 A105281 A158797
Adjacent sequences: A141831 A141832 A141833 * A141835 A141836 A141837
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Peter Bala (pbala(AT)toucansurf.com), Jul 09 2008
|
| |
|
|
