|
Search: id:A141834
|
|
|
| A141834 |
|
Sum of the lengths of the cycles at a vertex of the complete graph K_n. |
|
+0
2
|
|
| 6, 42, 252, 1620, 11730, 95886, 876792, 8877672, 98640990, 1193556210, 15624736116, 220048367292, 3317652307242, 53319412081110, 909984632851440, 16436597430879696, 313262209859119542, 6282647653285675962
(list; graph; listen)
|
|
|
OFFSET
|
3,1
|
|
|
COMMENT
|
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: A054642 A082139 A054613 this_sequence A105281 A074429 A062310
Adjacent sequences: A141831 A141832 A141833 this_sequence A141835 A141836 A141837
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Peter Bala (pbala(AT)toucansurf.com), Jul 09 2008
|
|
|
Search completed in 0.002 seconds
|
