A006561 Number of intersections of diagonals in the interior of a regular n-gon.

0, 0, 0, 1, 5, 13, 35, 49, 126, 161, 330, 301, 715, 757, 1365, 1377, 2380, 1837, 3876, 3841, 5985, 5941, 8855, 7297, 12650, 12481, 17550, 17249, 23751, 16801, 31465, 30913, 40920, 40257, 52360, 46981, 66045, 64981, 82251, 80881, 101270, 84841, 123410, 121441

Offset: 1

Author

N. J. A. Sloane, Bjorn Poonen (poonen(AT)math.princeton.edu)

Keywords

• easy
• nonn
• nice

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
• Johan Gielis and Ilia Tavkhelidze, The general case of cutting of GML surfaces and bodies, arXiv:1904.01414 [math.GM], 2019.
• Jessica Gonzalez, Illustration of a(4) through a(9).
• M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5.
• M. F. Hasler, Interactive illustration of A006561(n), Sep 01 2017. (For colored versions see A006533.)
• Sascha Kurz, m-gons in regular n-gons.
• Roger Mansuy, Des croisements pas si faciles à compter, La Recherche, 547, Mai 2019 (in French).
• B. Poonen and M. Rubinstein, The Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. Discrete Mathematics, Vol. 11, No.1 (1998) pp. 135-156; DOI:10.1137/S0895480195281246. [Copy on B. Poonen's web site.]
• B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, arXiv:math/9508209 [math.MG]: revision from 2006 has a few typos from the published version corrected.
• B. Poonen and M. Rubinstein, Mathematica programs for A006561 and related sequences.
• M. Rubinstein, Drawings for n=4,5,6,....
• N. J. A. Sloane, Illustrations of a(8) and a(9).
• N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
• N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.
• N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 18.
• Robert G. Wilson v, Illustration of a(10)
• Index entry for Sequences formed by drawing all diagonals in regular polygon

Crossrefs

Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.

See also A101363, A292104, A292105.

See A290447 for an analogous problem on a line.

Programs

Maple

delta:=(m,n) -> if (n mod m) = 0 then 1 else 0; fi;
f:=proc(n) global delta;
if n <= 2 then 0 else \
binomial(n,4)  \
+ (-5*n^3 + 45*n^2 - 70*n + 24)*delta(2,n)/24 \
- (3*n/2)*delta(4,n) \
+ (-45*n^2 + 262*n)*delta(6,n)/6  \
+ 42*n*delta(12,n) \
+ 60*n*delta(18,n) \
+ 35*n*delta(24,n) \
- 38*n*delta(30,n) \
- 82*n*delta(42,n) \
- 330*n*delta(60,n) \
- 144*n*delta(84,n) \
- 96*n*delta(90,n) \
- 144*n*delta(120,n) \
- 96*n*delta(210,n); fi; end;
[seq(f(n),n=1..100)]; # N. J. A. Sloane, Aug 09 2017

Mathematica

del[m_,n_]:=If[Mod[n,m]==0,1,0]; Int[n_]:=If[n<4, 0, Binomial[n,4] + del[2,n](-5n^3+45n^2-70n+24)/24 - del[4,n](3n/2) + del[6,n](-45n^2+262n)/6 + del[12,n]*42n + del[18,n]*60n + del[24,n]*35n - del[30,n]*38n - del[42,n]*82n - del[60,n]*330n - del[84,n]*144n - del[90,n]*96n - del[120,n]*144n - del[210,n]*96n]; Table[Int[n], {n,1,1000}] (* T. D. Noe, Dec 21 2006 *)

PARI

apply( {A006561(n)=binomial(n,4)+if(n%2==0, (n>2) + (-5*n^2+45*n-70)*n/24 + vecsum([t[2] | t<-[4,6,12,18,24,30,42,60,84,90,120,210;-3/2,(262-45*n)/6,42,60,35,-38,-82,-330,-144,-96,-144,-96], n%t[1]==0])*n)}, [1..44]) \\ M. F. Hasler, Aug 23 2017, edited Aug 06 2021

Python

def d(n,m): return not n % m
def A006561(n): return 0 if n == 2 else n*(42*d(n,12) - 144*d(n,120) + 60*d(n,18) - 96*d(n,210) + 35*d(n,24)- 38*d(n,30) - 82*d(n,42) - 330*d(n,60) - 144*d(n,84) - 96*d(n,90)) + (n**4 - 6*n**3 + 11*n**2 - 6*n -d(n,2)*(5*n**3 - 45*n**2 + 70*n - 24) - 36*d(n,4)*n - 4*d(n,6)*n*(45*n - 262))//24 # Chai Wah Wu, Mar 08 2021

Formula

Let delta(m,n) = 1 if m divides n, otherwise 0.

For n >= 3, a(n) = binomial(n,4) + (-5*n^3 + 45*n^2 - 70*n + 24)*delta(2,n)/24

- (3*n/2)*delta(4,n) + (-45*n^2 + 262*n)*delta(6,n)/6 + 42*n*delta(12,n)

+ 60*n*delta(18,n) + 35*n*delta(24,n) - 38*n*delta(30,n)

- 82*n*delta(42,n) - 330*n*delta(60,n) - 144*n*delta(84,n)

- 96*n*delta(90,n) - 144*n*delta(120,n) - 96*n*delta(210,n). [Poonen and Rubinstein, Theorem 1] - N. J. A. Sloane, Aug 09 2017

For odd n, a(n) = binomial(n,4) = n*(n-1)*(n-2)*(n-3)/24, see A053126. For even n, use this formula, but then subtract 2 for every 3-crossing, subtract 5 for every 4-crossing, subtract 9 for every 5-crossing, etc. The number to be subtracted for a d-crossing is (d-1)*(d-2)/2. - Graeme McRae, Dec 26 2004

a(n) = A007569(n) - n. - T. D. Noe, Dec 23 2006

a(2n+5) = A053126(n+4). - Philippe Deléham, Jun 07 2013