A099578 -id:A099578 - cp's OEIS frontend

A030077 Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct path lengths.

1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 2869, 6188, 26565, 14502, 167898, 245157, 445507, 1562275, 6055315, 2571120, 44247137, 64512240, 65610820, 362592230, 1850988412, 591652989, 11453679146, 17620076360, 1511122441, 114955808528, 511647729284, 67876359922, 3347789809236, 1882352047787, 1404030562068, 32308782859535

Offset: 1

Daniel Lurie Gittelson, Dec 11 1999

For n points on a circle, there are floor(n/2) distinct line segment lengths. Hence an upper bound for a(n) is the number of compositions of n-1 into floor(n/2) nonnegative parts, which is A099578(n-2). Conjecture: the upper bound is attained if n is prime. There are A052558(n-2) paths to be considered. - T. D. Noe, Jan 09 2007 [Edited by Petros Hadjicostas, Jul 19 2018]

			For n=4 the 3 lengths are: 3 boundary edges (length 3), edge-diagonal-edge (2 + sqrt(2)) and diagonal-edge-diagonal (1 + 2*sqrt(2)).
For n=5, the 4 edges of the path may include 0,...,4 diagonals, so a(5)=5.

Samuel C. Gutekunst, Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds, arXiv:2506.10758 [cs.DM], 2025. See pp. 2-3, 17-18.
Sean A. Irvine, Java program (github)
Brendan D. McKay and Tim Peters, Paths through equally spaced points on a circle, arXiv:2205.06004 [math.CO], 2022.

Cf. A007874 (similar, but with n line segments), A052558, A099578.

See A352568 for the multisets of line lengths.

a(13) - a(16) from T. D. Noe, Jan 09 2007
Removed unnecessary mention of dihedral group from definition. - N. J. A. Sloane, Apr 02 2022
The terms a(1) to a(15) have been verified by Sean A. Irvine and a(1) to a(16) by Brendan McKay. - N. J. A. Sloane, Apr 02 2022
a(17) to a(37) from Brendan McKay, May 14 2022

A099575 Number triangle T(n,k) = binomial(n + floor(k/2) + 1, n + 1), 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 5, 5, 1, 1, 6, 6, 21, 1, 1, 7, 7, 28, 28, 1, 1, 8, 8, 36, 36, 120, 1, 1, 9, 9, 45, 45, 165, 165, 1, 1, 10, 10, 55, 55, 220, 220, 715, 1, 1, 11, 11, 66, 66, 286, 286, 1001, 1001, 1, 1, 12, 12, 78, 78, 364, 364, 1365, 1365, 4368, 1, 1, 13, 13, 91, 91, 455, 455, 1820, 1820, 6188, 6188

Offset: 0

Paul Barry, Oct 23 2004

Original name was: "Number triangle T(n,k) = if(k<=n, Sum_{j=0..floor(k/2)} binomial(n+j,j), 0)."

			Rows start:
  1;
  1, 1;
  1, 1,  4;
  1, 1,  5,  5;
  1, 1,  6,  6, 21;
  1, 1,  7,  7, 28, 28;
  1, 1,  8,  8, 36, 36, 120;
  1, 1,  9,  9, 45, 45, 165, 165;
  1, 1, 10, 10, 55, 55, 220, 220, 715;

Robert Israel, Table of n, a(n) for n = 0..10010 (Rows 0..140, flattened)

Cf. A099573, A099576 (row sums), A099577 (diagonal sums), A099578 (main diagonal).

[Binomial(n+1+Floor(k/2), n+1): k in [0..n], n in [0..15]]; // G. C. Greubel, Jul 24 2022

for n from 0 to 20 do seq(binomial(n+floor(k/2)+1,n+1),k=0..n) od; # Robert Israel, May 08 2018

Table[Binomial[n+Floor[k/2]+1, n+1], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 24 2022 *)

flatten([[binomial(n+(k//2)+1, n+1) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jul 24 2022

T(n, k) = binomial(n + floor(k/2) + 1, n + 1).
T(n, n) = A099578(n).
Sum_{k=0..n} T(n, k) = A099576(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A099577(n).

Definition simplified by Robert Israel, May 08 2018

A127040 a(n) = binomial(floor((3n+4)/2),floor(n/2)).

Original entry on oeis.org

1, 1, 5, 6, 28, 36, 165, 220, 1001, 1365, 6188, 8568, 38760, 54264, 245157, 346104, 1562275, 2220075, 10015005, 14307150, 64512240, 92561040, 417225900, 600805296, 2707475148, 3910797436, 17620076360, 25518731280, 114955808528

Offset: 0

T. D. Noe, Jan 03 2007

nonn

With offset 2, the number of compositions of n into floor(n/2) parts, which is an upper bound for A007874.

T. D. Noe, Table of n, a(n) for n=0..200

Cf. A004319 (bisection), A025174 (bisection), A099578.

seq(sum(binomial(n+k, k-1), k=0..ceil((n+1)/2)), n=0..28); # Zerinvary Lajos, Apr 11 2007

CoefficientList[Series[(-1 + (2 Cos[1/3 ArcSin[(3 Sqrt[3] x)/2]])/Sqrt[4 - 27 x^2] + 3 x^3 Hypergeometric2F1[4/3, 5/3, 5/2, (27 x^2)/4])/(3 x^2), {x, 0, 20}], x] (* Benedict W. J. Irwin, Aug 16 2016 *)
Table[Binomial[Floor[(3 n + 4)/2], Floor[n/2]], {n, 0, 28}] (* Michael De Vlieger, Aug 18 2016 *)

a(n) = binomial((3*n+4)\2, n\2); \\ Michel Marcus, Sep 09 2016

From Benedict W. J. Irwin, Aug 16 2016: (Start)
G.f.: (-1 + (2*cos(arcsin(3*sqrt(3)*x/2)/3))/sqrt(4-27*x^2) + 3*x^3*2F1(4/3,5/3;5/2;27*x^2/4))/(3*x^2).
E.g.f.: 2F3(4/3,5/3;1/2,3/2,2;27*x^2/16) + x*2F3(4/3,5/3;1,3/2,5/2;27*x^2/16).
(End)
D-finite with recurrence 8*(n+2)*(n+1)*a(n) -84*(n-1)*(n+1)*a(n-1) +6*(-33*n^2+54*n-8)*a(n-2) +9*(63*n^2-63*n-16)*a(n-3) +108*(3*n-5)*(3*n-7)*a(n-4)=0. - R. J. Mathar, Feb 08 2021

cp's OEIS Frontend

A030077 Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct path lengths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A099575 Number triangle T(n,k) = binomial(n + floor(k/2) + 1, n + 1), 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A127040 a(n) = binomial(floor((3n+4)/2),floor(n/2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula