login
A006561
Number of intersections of diagonals in the interior of a regular n-gon.
(Formerly M3833)
45
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,5
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.
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.)
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.
M. Rubinstein, Drawings for n=4,5,6,....
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)
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
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 *)
PROG
(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
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.
Sequence in context: A294841 A092647 A171262 * A146845 A192310 A167710
KEYWORD
easy,nonn,nice
AUTHOR
N. J. A. Sloane, Bjorn Poonen (poonen(AT)math.princeton.edu)
STATUS
approved