A141834 Sum of the lengths of the cycles at a vertex of the complete graph K_n.

6, 42, 252, 1620, 11730, 95886, 876792, 8877672, 98640990, 1193556210, 15624736116, 220048367292, 3317652307242, 53319412081110, 909984632851440, 16436597430879696, 313262209859119542, 6282647653285675962

Offset: 3

Author

Peter Bala, Jul 09 2008

Keywords

• easy
• nonn

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.

Examples

			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.
		

Links

• Mehdi Hassani, Counting and computing by e

Crossrefs

Cf. A000522, A038154.

Programs

Maple

a:= n -> 2 - 2*n + (n-1)*(n-1)!*add(1/k!,k = 0..n-1): seq(a(n), n = 3..22);

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! + ... .