|
%I M3833 #158 Nov 07 2023 16:14:24
%S 0,0,0,1,5,13,35,49,126,161,330,301,715,757,1365,1377,2380,1837,3876,
%T 3841,5985,5941,8855,7297,12650,12481,17550,17249,23751,16801,31465,
%U 30913,40920,40257,52360,46981,66045,64981,82251,80881,101270,84841,123410,121441
%N Number of intersections of diagonals in the interior of a regular n-gon.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A006561/b006561.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)
%H Johan Gielis and Ilia Tavkhelidze, <a href="https://arxiv.org/abs/1904.01414">The general case of cutting of GML surfaces and bodies</a>, arXiv:1904.01414 [math.GM], 2019.
%H Jessica Gonzalez, <a href="/A006561/a006561_1.png">Illustration of a(4) through a(9)</a>.
%H M. Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths2/griffiths.html">Counting the regions in a regular drawing of K_{n,n}</a>, J. Int. Seq. 13 (2010) # 10.8.5.
%H M. F. Hasler, <a href="/A006561/a006561.html">Interactive illustration of A006561(n)</a>, Sep 01 2017. (For colored versions see A006533.)
%H Sascha Kurz, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/drawing/drawing.html">m-gons in regular n-gons</a>.
%H Roger Mansuy, <a href="https://www.larecherche.fr/chronique-math%C3%A9matiques/des-croisements-pas-si-faciles-%C3%A0-compter">Des croisements pas si faciles à compter</a>, La Recherche, 547, Mai 2019 (in French).
%H B. Poonen and M. Rubinstein, <a href="http://doi.org/10.1137/S0895480195281246">The Number of Intersection Points Made by the Diagonals of a Regular Polygon</a>, SIAM J. Discrete Mathematics, Vol. 11, No.1 (1998) pp. 135-156; DOI:10.1137/S0895480195281246. <a href="http://math.mit.edu/~poonen/papers/ngon.pdf">[Copy on B. Poonen's web site.]</a>
%H B. Poonen and M. Rubinstein, <a href="https://arxiv.org/abs/math/9508209">The number of intersection points made by the diagonals of a regular polygon</a>, arXiv:math/9508209 [math.MG]: revision from 2006 has a few typos from the published version corrected.
%H B. Poonen and M. Rubinstein, <a href="http://math.mit.edu/~poonen/papers/ngon.m">Mathematica programs for A006561 and related sequences</a>.
%H M. Rubinstein, <a href="/A006561/a006561_3.pdf">Drawings for n=4,5,6,...</a>.
%H N. J. A. Sloane, <a href="/A006561/a006561_4.pdf">Illustrations of a(8) and a(9)</a>.
%H N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, <a href="https://vimeo.com/237029685">Part I</a>, <a href="https://vimeo.com/237030304">Part 2</a>, <a href="https://oeis.org/A290447/a290447_slides.pdf">Slides</a>. (Mentions this sequence)
%H N. J. A. Sloane (in collaboration with Scott R. Shannon), <a href="/A331452/a331452.pdf">Art and Sequences</a>, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.
%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 18.
%H Robert G. Wilson v, <a href="/A006561/a006561_1.pdf">Illustration of a(10)</a>
%H <a href="/index/Pol#Poonen">Index entry for Sequences formed by drawing all diagonals in regular polygon</a>
%F Let delta(m,n) = 1 if m divides n, otherwise 0.
%F For n >= 3, a(n) = binomial(n,4) + (-5*n^3 + 45*n^2 - 70*n + 24)*delta(2,n)/24
%F - (3*n/2)*delta(4,n) + (-45*n^2 + 262*n)*delta(6,n)/6 + 42*n*delta(12,n)
%F + 60*n*delta(18,n) + 35*n*delta(24,n) - 38*n*delta(30,n)
%F - 82*n*delta(42,n) - 330*n*delta(60,n) - 144*n*delta(84,n)
%F - 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
%F 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
%F a(n) = A007569(n) - n. - _T. D. Noe_, Dec 23 2006
%F a(2n+5) = A053126(n+4). - _Philippe Deléham_, Jun 07 2013
%p delta:=(m,n) -> if (n mod m) = 0 then 1 else 0; fi;
%p f:=proc(n) global delta;
%p if n <= 2 then 0 else \
%p binomial(n,4) \
%p + (-5*n^3 + 45*n^2 - 70*n + 24)*delta(2,n)/24 \
%p - (3*n/2)*delta(4,n) \
%p + (-45*n^2 + 262*n)*delta(6,n)/6 \
%p + 42*n*delta(12,n) \
%p + 60*n*delta(18,n) \
%p + 35*n*delta(24,n) \
%p - 38*n*delta(30,n) \
%p - 82*n*delta(42,n) \
%p - 330*n*delta(60,n) \
%p - 144*n*delta(84,n) \
%p - 96*n*delta(90,n) \
%p - 144*n*delta(120,n) \
%p - 96*n*delta(210,n); fi; end;
%p [seq(f(n),n=1..100)]; # _N. J. A. Sloane_, Aug 09 2017
%t 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 *)
%o (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
%o (Python)
%o def d(n,m): return not n % m
%o 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
%Y Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.
%Y See also A101363, A292104, A292105.
%Y See A290447 for an analogous problem on a line.
%K easy,nonn,nice
%O 1,5
%A _N. J. A. Sloane_, Bjorn Poonen (poonen(AT)math.princeton.edu)
|
