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,3

Links

Table of n, a(n) for n=1..54.

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).

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

Example

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

Crossrefs

Cf. A057979, A128223.

Sequence in context: A281171 A190713 A288347 * A325647 A367403 A049753

Adjacent sequences: A109091 A109092 A109093 * A109095 A109096 A109097

Keyword

nonn,easy

Author

Ryan Propper, Jun 18 2005

Status

approved