A109094 Length of the longest path (repeated edges not allowed) between two arbitrary, distinct nodes in K_n, the complete graph on n vertices.

0, 1, 2, 5, 9, 13, 20, 25, 35, 41, 54, 61, 77, 85, 104, 113, 135, 145, 170, 181, 209, 221, 252, 265, 299, 313, 350, 365, 405, 421, 464, 481, 527, 545, 594, 613, 665, 685, 740, 761, 819, 841, 902, 925, 989, 1013, 1080, 1105, 1175, 1201, 1274, 1301, 1377, 1405

Offset: 1

Author

Ryan Propper, Jun 18 2005

Keywords

• nonn
• easy

Examples

			a(4) = 5 because the length of the longest path between any two distinct vertices in K_4 is 5.
		

Links

• R. J. Mathar, Comments on this sequence
• Eric Weisstein's World of Mathematics, Complete Graph.
• Eric Weisstein's World of Mathematics, Euler Path.
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Crossrefs

Cf. A057979, A128223.

Formula

a(1)=0; a(2n+1) = n*(n-1)/2-1 = A014107(n+1), n>0; a(2n)=n*(n-2)/2+1= A001844(n-1). - Martin Fuller, R. J. Mathar and Mitch Harris, Dec 06 2007

O.g.f.: x^2*(x^4-2*x^3-x^2-x-1)/((-1+x)^3 *(x+1)^2) . - R. J. Mathar, Jan 17 2008