login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006561 Number of intersections of diagonals in the interior of regular n-gon.
(Formerly M3833)
32

%I M3833

%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

%N Number of intersections of diagonals in the interior of 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 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 B. Poonen and M. Rubinstein, <a href="http://arXiv.org/abs/math.MG/9508209">The number of intersection points made by the diagonals of a regular polygon</a>, arXiv:math/9508209 [math.MG], 1995-2006, which has fewer typos than the SIAM version.

%H B. Poonen and M. Rubinstein, <a href="http://dx.doi.org/10.1137/S0895480195281246">Number of Intersection Points Made by the Diagonals of a Regular Polygon</a>, SIAM J. Discrete Mathematics, Vol. 11, pp. 135-156 (1998). [Copy on SIAM web site]

%H B. Poonen and M. Rubinstein, <a href="http://math.mit.edu/~poonen/papers/ngon.pdf">The number of intersection points made by the diagonals of a regular polygon</a>, SIAM J. on Discrete Mathematics, Vol. 11, No. 1, 135-156 (1998). [Copy on B. Poonen's web site]

%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 R. 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(4,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, binomial(n,4) = (n^4-6n^3+11n^2-6n)/24. 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 is one smaller than a triangular number. - _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) {a(n,m=[4,6,12,18,24,30,42,60,84,90,120,210],v=[-3/2,(262-45*n)/6,42,60,35,-38,-82,-330,-144,-96,-144,-96])=if(n>3, binomial(n,4) + if(n%2==0,(-5*n^2+45*n-70)*n/24+1 + sum(i=1,#m,if(n%m[i]==0,v[i]))*n))} \\ _M. F. Hasler_, Aug 23 2017

%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)

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 12:00 EST 2018. Contains 299452 sequences. (Running on oeis4.)