A030077 -id:A030077 - cp's OEIS frontend

A052558 a(n) = n! ((-1)^n + 2n + 3)/4.

1, 1, 4, 12, 72, 360, 2880, 20160, 201600, 1814400, 21772800, 239500800, 3353011200, 43589145600, 697426329600, 10461394944000, 188305108992000, 3201186852864000, 64023737057280000, 1216451004088320000, 26761922089943040000, 562000363888803840000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Stirling transform of (-1)^(n+1)*a(n-1) = [1, -1, 4, -12, 72, -360, ...] is A052841(n-1) = [1,0,2,6,38,270,...]. - Michael Somos, Mar 04 2004
The Stirling transform of this sequence is A258369. - Philippe Deléham, May 17 2005; corrected by Ilya Gutkovskiy, Jul 25 2018
Ignoring reflections, this is the number of ways of connecting n+2 equally-spaced points on a circle with a path of n+1 line segments. See A030077 for the number of distinct lengths. - T. D. Noe, Jan 05 2007
From Gary W. Adamson, Apr 20 2009: (Start)
Signed: (+ - - + + - - + +, ...) = eigensequence of triangle A002260.
Example: -360 = (1, 1, -1, -4, 12, 71) dot (1, -2, 3, -4, 5, -6) = (1, -2, -3, 16, 60, -432). (End)
a(n) is the number of odd fixed points in all permutations of {1, 2, ..., n+1}, Example: a(2)=4 because we have 1'23', 1'32, 312, 213', 231, and 321, where the odd fixed points are marked. - Emeric Deutsch, Jul 18 2009
a(n) is also the number of permutations of [n+1] starting with an even number. - Olivier Gérard, Nov 07 2011

T. D. Noe, Table of n, a(n) for n=0..100
A. Moreno Canadas, P. F. Fernandez Espinoza, and I. D. M. Gaviria, Categorification of some integer sequences via Kronecker Modules, JP J. Algebra, Number Theory and Applic. 38 (4) (2016) 339-347
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 500.

Cf. A174548, A052841.
Cf. A002260. - Gary W. Adamson, Apr 20 2009
Cf. A052591. - Emeric Deutsch, Jul 18 2009
Cf. A052618, A077611, A199495. - Olivier Gérard, Nov 07 2011

List([0..30], n-> ((-1)^n +2*n +3)*Factorial(n)/4); # G. C. Greubel, May 07 2019

[((-1)^n +2*n +3)*Factorial(n)/4: n in [0..30]]; // G. C. Greubel, May 07 2019

spec := [S,{S=Prod(Sequence(Z),Sequence(Prod(Z,Z)))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

Table[n!((-1)^n+2n+3)/4,{n,0,30}] (* Harvey P. Dale, Aug 16 2014 *)

PARI
```
a(n)=if(n<0,0,(1+n\2)*n!)
```

a(n)=if(n<0, 0, n!*polcoeff(1/(1-x)/(1-x^2)+x*O(x^n), n))

[((-1)^n +2*n +3)*factorial(n)/4 for n in (0..30)] # G. C. Greubel, May 07 2019

D-finite with recurrence a(n) = a(n-1) + (n^2-1)*a(n-2), with a(1)=1, a(0)=1.
a(n) = ((-1)^n + 2*n + 3)*n!/4.
Let u(1)=1, u(n) = Sum_{k=1..n-1} u(k)*k*(-1)^(k-1) then a(n) = abs(u(n+2)). - Benoit Cloitre, Nov 14 2003
E.g.f.: 1/((1-x)*(1-x^2)).
From Emeric Deutsch, Jul 18 2009: (Start)
a(n) = (n+1)!/2 if n is odd; a(n) = n!(n+2)/2 if n is even.
a(n) = (n+1)! - A052591(n). (End)
E.g.f.: G(0)/(1+x) where G(k) = 1 + 2*x*(k+1)/((2*k+1) - x*(2*k+1)*(2*k+3)/(x*(2*k+3) + 2*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 21 2012
Sum_{n>=0} 1/a(n) = e - 1/e = 2*sinh(1) (A174548). - Amiram Eldar, Jan 22 2023

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

Original entry on oeis.org

1, 1, 4, 5, 21, 28, 120, 165, 715, 1001, 4368, 6188, 27132, 38760, 170544, 245157, 1081575, 1562275, 6906900, 10015005, 44352165, 64512240, 286097760, 417225900, 1852482996, 2707475148, 12033222880, 17620076360, 78378960360, 114955808528

Offset: 0

Paul Barry, Oct 23 2004

Main diagonal of triangle A099575.
With offset 2, this is the number of compositions of n-1 into floor(n/2) parts. - T. D. Noe, Jan 05 2007
From Petros Hadjicostas, Jul 19 2018: (Start)
We clarify the above comment by T. D. Noe. The number of compositions of N into K positive parts is C(N-1, K-1). This was proved by MacMahon in 1893 (and probably by others before him). The number of compositions of N into K nonnegative parts is C(N+K-1, K-1) because for every composition b_1 + ... + b_K = N with b_i >= 0 for all i, we may create another composition c_1 + ... + c_K = N+K with c_i = b_i + 1 >= 1.
The statement of T. D. Noe above means that, for n>=2, a(n-2) is the number of compositions of N = n-1 into K = floor(n/2) nonnegative parts. Thus, a(n-2) = C(N+K-1, K-1) = C(n-1+floor(n/2)-1, floor(n/2)-1) = C(floor((3(n-2)+2)/2), floor((n-2)/2)).
This interpretation is important for T. D. Noe's comments for sequence A030077, whose unknown general formula remains an unsolved problem (as of July 2018).
It should be noted, however, that for most authors "composition" means "composition into positive parts". The phrase "weak composition" is sometimes used for a "composition into nonnegative parts".
(End)

			From _Petros Hadjicostas_, Jul 19 2018: (Start)
With n=2 there are a(2-2) = a(0) = 1 compositions of 2-1 = 1 into floor(2/2) = 1 nonnegative parts, namely 1 (only).
With n=3 there are a(3-2) = a(1) = 1 compositions of 3-1 = 2 into floor(3/2) = 1 nonnegative parts, namely 2 (only).
With n=4 there are a(4-2) = a(2) = 4 compositions of 4-1 = 3 into floor(4/2) = 2 nonnegative parts, namely 0+3, 3+0, 1+2, and 2+1.
With n=5 there are a(5-2) = a(3) = 5 compositions of 5-1 = 4 into floor(5/2) = 2 nonnegative parts, namely 0+4, 4+0, 1+3, 3+1, and 2+2.
With n=6 there are a(6-2) = a(4) = 21 compositions of 6-1 = 5 into floor(6/2) = 3 nonnegative parts, namely the 3 permutations of 1+1+3, the 3 permutations of 1+2+2, the 3 permutations of 0+0+5, the 6 permutations of 0+1+4, and the 6 permutations of 0+2+3.
(End)

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

Cf. A025174 (bisection), A030077, A045721 (bisection), A099575, A127040.

[(&+[Binomial(n+j, j): j in [0..Floor(n/2)]]): n in [0..40]]; // G. C. Greubel, Jul 24 2022

A099578:=n->binomial(floor((3*n+2)/2), floor(n/2)); seq(A099578(k), k=0..50); # Wesley Ivan Hurt, Nov 01 2013

Table[Binomial[Floor[(3n+2)/2], Floor[n/2]], {n, 0, 50}] (* Wesley Ivan Hurt, Nov 01 2013 *)
CoefficientList[Series[-((Sqrt[4 -27 x^2] -2(Cos[1/3 ArcSin[(3 Sqrt[3] x)/2]] + Sqrt[3] Sin[2/3 ArcSin[(3 Sqrt[3] x)/2]]))/(3 x Sqrt[4 -27 x^2])), {x, 0, 20}], x] (* Benedict W. J. Irwin, Aug 15 2016 *)
a[n_] := Binomial[2*n+1, n]*Hypergeometric2F1[-n, n+1, -2*n-1, -1]; Flatten[Table[a[n], {n, 0, 29}]] (* Detlef Meya, Dec 25 2023 *)

a(n) = binomial((3*n+2)\2, n\2); \\ Michel Marcus, Nov 02 2013

[binomial((3*n+2)//2, n//2) for n in (0..40)] # G. C. Greubel, Jul 24 2022

a(n) = Sum_{k=0..floor(n/2)} binomial(n+k, k).
40*n*(n+1)*a(n) +36*n*(n-2)*a(n-1) -6*(45*n^2-23)*a(n-2) -27*(3*n-4)*(3*n-5)*a(n-3) = 0. - R. J. Mathar, Oct 30 2014
From Benedict W. J. Irwin, Aug 15 2016: (Start)
G.f.: -( (sqrt(4-27*x^2) - 2*(cos(arcsin(3*sqrt(3)*x/2)/3) + sqrt(3)*sin(2*arcsin(3*sqrt(3)*x/2)/3)) )/( 3*x*sqrt(4-27*x^2)) ).
E.g.f.: Hypergeometric2F3(2/3,4/3;1/2,1,3/2;27*x^2/16) + x*Hypergeometric2F3(4/3,5/3;3/2,3/2,2;27*x^2/16).
(End)
Recurrence: 4*n*(n+1)*(6*n-1)*a(n) = 18*n*a(n-1) + 3*(3*n-2)*(3*n-1)*(6*n+5)*a(n-2). - Vaclav Kotesovec, Aug 15 2016
a(n) = binomial(2*n+1, n)*hypergeom([-n, n+1], [-2*n-1], -1). - Detlef Meya, Dec 25 2023

A007874 Distinct perimeter lengths of polygons with regularly spaced vertices.

Original entry on oeis.org

1, 1, 1, 2, 4, 10, 24, 63, 177, 428, 1230, 2556, 8202, 18506, 18162, 119069

Offset: 1

Peter H. Borcherds (p.h.borcherds(AT)bham.ac.uk)

nonn

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 into floor(n/2) nonnegative parts, which is A127040(n-2). To find a(n), the length of A052558(n-2) paths must be computed. - T. D. Noe, Jan 13 2007 [edited by Petros Hadjicostas, Jul 19 2018]

			Consider n=4. Label the points on the circle A,B,C and D. Suppose that AB has unit length. Then a(4)=2 because the two 4-gons are ABCDA and ACBDA, with perimeters 4 and 2+2*sqrt(2), respectively.

Cf. A030077.

More terms from T. D. Noe, Jan 13 2007

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

Original entry on oeis.org

1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 4129, 6188, 26565, 38591, 167898, 245157, 1072730, 1562275, 6871780, 10011302, 44247137, 64512240, 285599304, 417219530, 1850988412, 2707392498, 12026818454, 17620076360, 78356395953, 114955808528, 511647729284, 751614362180, 3347789809236, 4923688862065, 21944254861680, 32308782859535

Offset: 1

N. J. A. Sloane, Apr 02 2022

nonn

This sequence is different from A030077 because there we only look at how many different total path lengths occur, whereas here we look at which individual segment lengths occur in the path. The latter count may be larger, because it can happen that two paths whose compositions are distinct can have the same total length. For n <= 16 this happens just when n is 12 and 15.
Say the type of a segment is its position in the increasing list of floor(n/2) possible segment lengths. The Buratti-Horak-Rosa conjecture is that the following condition is necessary and sufficient for a multiset to be realizable as a path: for each divisor d of n, the number of segments of type divisible by d is at most n-d. The sequence confirms the conjecture up to n=37. - Brendan McKay, May 14 2022
If the Buratti-Horak-Rosa conjecture is true, the values of a(38)-a(50) are 144079707346575, 212327989773900, 947309492837400, 1397281501935165, 6236646703759395, 9206478467454345, 41107996877935680, 60727722660586800, 271250494550621040, 400978991944396320, 1791608261879217600, 2650087220696342700, 11844267374132633700. - Brendan McKay, Jun 14 2022

			For n = 4 there are two possible edge lengths, the side and the diagonal of the square. For a path with three line segments, we can have 3 sides, 2 sides and one diagonal, or 2 diagonals and one side. So a(4) = 3.

Brendan McKay, Posting to Sequence Fans Mailing List, April 02 2022.

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, 6, 17-18.
P. Horak and A. Rosa, On a problem of Marco Burrati, Electronic J. Combinatorics, 16 (2009) R20.
Brendan D. McKay and Tim Peters, Paths through equally spaced points on a circle, arXiv:2205.06004 [math.CO], 2022.
A. Pasotti and M. A. Pellegrini, On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs, Electronic J. Combinatorics, 21 (2014) P2.30.

Cf. A030077.

Definition adjusted by Brendan McKay, Apr 03 2022

a(17) to a(37) from Brendan McKay, May 14 2022

cp's OEIS Frontend

A052558 a(n) = n! *((-1)^n + 2*n + 3)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A007874 Distinct perimeter lengths of polygons with regularly spaced vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A052558 a(n) = n! ((-1)^n + 2n + 3)/4.