The Moser's formula for the division of the circle by chords problem revisited
Carlos Rodriguez-Lucatero







crodriguez@correo.cua.uam.mx
Departamento de Tecnologías de la Información, Universidad Autónoma Metropolitana-Cuajimalpa,
Torre III,
Av. Vasco de Quiroga 4871,
Col.Santa Fe Cuajimalpa, México, D. F.,
C.P. 05348, México


The enumeration of the regions formed when circle  is divided by secants drawn from points on the circle is one of the examples where the inductive reasoning fails as was pointed out by Leo Moser in the Mathematical Miscellany in 1949. The formula that gives the right number of regions can be deduced by combinatorics reasoning using the Euler's planar graph formula, etc. My contribution in the present work is to reformulate and solve such problem in terms of a  fourth order difference equation and to obtain the formula proposed by Leo Moser. 






Mathematics Subjects Classification: 05A15




Keywords: Exact Enumeration Problems; Generating Functions.




The Moser's formula for the division of the circle by chords problem revisited
    Carlos Rodríguez-Lucatero
    December 30, 2023
==============================================================================







§ INTRODUCTION

A problem sometimes known as Moser's circle problem asks to determine the number of pieces into which a circle is divided if m points on its circumference are joined by chords with no three internally concurrent. 
The number of regions formed inside the circle  when it is divided by the chords as mentioned, can be sketched for the fisrt 5 steps in the following figure:



If we label the regions formed by this division by secants, the sequence of the number of regions generated  in terms of number of points till this point is 1,2,4,8,16. If the number of points is denoted by m and we try to guess the functional behavior of the sequence the induction tell us that it is 2^m-1. By following this procedure if we add one more point and draw the corresponding secants we get 31 regions instead of 32. Let me tabulate this behavior for the seven first points in the following table


 Points      regions 

 m         f(m) 

 1     1 
 
 2     2 
 
 3     4 
 
 4     8 
 
 5     16 
 
 6     31 
 
 7     57 
 
 

As can be seen the functon 2^m-1 no longer describes the behavior of the sequence. That is the reason why Leo Moser in <cit.> pointed that the inductive method for guessing the next element in a numerical sequence can fail.  In fact the title of the section in <cit.> was On the danger of induction. He leaves to the reader as an exercise, to show that the number of regions formed by joining points on a circle by chords is f(m)=∑_j=0^mm-1j.
    

The function that describes the behavior of the sequence is:


    f(m)=m^4-6m^3+23 m^2-18m+24/24


This can be proven in many different forms. In the following sections I will describe how it was demonstrated
 in <cit.> using combinatorial arguments, in <cit.> by using the Euler's planar graphs formula, and finally how it can be proven by using a fourth degree difference equation.




§ DEDUCTION USING A COMBINATORIAL ARGUMENTATION


In this section we will describe a proof of the Moser's formula based on the article <cit.>(see also<cit.>). 
In order to find the actual formula on the number of regions formed, the author of <cit.> states the following 


Result: The number of regions formed is


    1+m2+m4


From the combinatorics it is known that rs=r!/s!(r-s)! and if we apply that to <ref> we obtain the Moser's formula



    f(m)=m^4-6m^3+23m^2-18m+24/24



The proof of <ref> given in <cit.> uses the fact that the binomial coeficient rs counts the ways we can choose s elements from a set of r different elements.

In order to formalize the demonstration, I will start by some basic lemas that can be used for the proof.

 
The total number of chords that can be created from the m points on the circle is

    m2


If we have m points each chord is formed by taking two points of the m lying on the perimeter of the circle. In other words the number of chords is determined by the number of ways in which the m points on the circle can be taken to form a chord.
Then the total number of posible chords equals the total number of different ways in which  m points can be taken in groups of 2 what is equal to m2.



 

The total number of interior crossing points of the chords obtained from the m points on the circle is

    m4


For calculating the number of interior intersection points inside the circle, we must count the number of ways in which the m points in the circle can be taken such that their related chords intersect, which can be done taking four points to form their chords and their corresponding intersections, what gives a total of m4 ways



 
Let m be the number of points on the circle and f(m) the number of regions formed by the division of a circle by chords. The total number of regions formed is


    f(m)=m^4-6m^3+23m^2-18m+24/24



Let me start by counting the regions formed by taking each chord one by one. Each time a new chord is drawn, it crosses a number of regions dividing them into two. The number of new created regions is equal to the number of regions crossed by the new chord, which is one more than the number of chords crossed. Given that the new chord cannot pass through a previously drawn point of intersection, then the number of chords crossed is equal to the number of interior points of intersection of the new chord. As consequence, the number of new regions created by this new chord equals the number of interior points of intersection of this chord plus one.
Because of that, taking into accont lemma <ref> and lemma <ref> the total number of new regions created by drawing all the chords is equal to the number of added chords plus the number of interior points of intersection as well as the fact that at the begining we have one region, the total number of regions formed is


    f(m)=1+m2+m4=m^4-6m^3+23m^2-18m+24/24







§ DEDUCTION USING THE PLANAR GRAPH EULER'S FORMULA



I found in <cit.> an elegant proof based on the famous planar graph Euler's formula that I will develop in this section. Let me start with the statement of the Euler's result


 
 Let V the number of vertices, E the number of edges and F the number of faces of a planar graph. Then V-E+F=2.


In order to use the planar graphs Euler's for deducing the Leo Moser's formula the author of <cit.> relate the set V with the orginal points on the circle as well as with the interior intersection points, the set E with the chords and arc's formed by the points on the circle and the set F with the formed regions. 
We can formalize this method as follows

 

Let P be the set of m points on the circle, I the set of m4 interior crossing points and f(m) the number of regions formed by the division of the circle by chords. 
Let G=(V,E) be the planar graph obtained from the circle division by chords, where V=P ∪ I, E the edges of the planar graph and F=f(m). The number of regions or faces formed is


    f(m)=m^4-6m^3+23m^2-18m+24/24

 

There are m points on the circle and there are m4 intersections of the chords. Then we have a total of

    V=(P ∪ I)=m+m4


vertices. In order to count the total number of edges it must be noticed that we have m circular arcs. Given that we have m4 interior intresection points where four edges meet then we have 4m4 additional edges. Due to the fact that we have m2 chords corresponding to two edges that meet the circle we have 2m2 more edges. Then we have 2m2+4m4 edges generated by the chords, but due to counting process we have counted them twice. Then this quantity must be divided by 2 giving a total of m2+2m4. Hence the total number of edges is


    E=m+m2+2m4

The number of faces is related with the number of regions f(m) as follows


    F=f(m)+1


From the <ref> we know that


    V-E+F=2


Replacing <ref>,<ref>,<ref> in <ref> we get


    { m+m4}-{ m+m2+2m4}+ f(m)+1 = 2


Simplifying <ref> we get


    -m2-m4 + f(m) = 1


From <ref> we express f(m) in terms of the other elements of the expression as follows


    f(m) = 1 +m2+m4=m^4-6m^3+23m^2-18m+24/24

 
and in that way we have finally mathematically proven the Moser's formula. 





§ MY DEDUCTION OF THE LEO MOSER'S FORMULA BY SOLVING A DIFFERENCE EQUATION
 

An alternative method that I propose for solving the Moser's circle division by chords is by obtaining a recurrence from the numerical sequence of the number of regions formed and then solve the related difference equation. For this end we have to obtain a recurrence relation to be solved. This recurrence relation can be obtained from the succesion of regions, using the technique of successive differences frequently applied in problems of inductive reasoning on numerical sequences. Applying the successive differences technique on the sequence {a_0,a_1,a_2,a_3,a_4,a_5} of six elements to obtain the seventh element a_6. Let me state this first result as a lemma.

 
The elements of the sequence 1,2,4,8,16,31,57, … that represent the growth behavior on the number of regions formed by dividing the circle by chords can be generated by a fourth degree recurrence relation

We start by applying the successive differences method for guessing the next element in the sequence on the first six elements of such numerical sequence.



a_0         a_1    •    a_2    •    a_3    •     a_4     •     a_5     •    a_6

 
1          2     •     4     •     8     •     16     •     31     •     57

 
•     1     •     2     •     4     •     8     •     15     •     •     • 
 
•     •     1     •     2     •     4     •     7     •     •     •     •  
 
•     •     •     1     •     2     •     3     •     •     •     •     • 
 
•     •     •     •     1     •     1     •     •     •     •     •     • 
 
 




From the calculations it can be noticed that we stop the successive differences procedure when the differences become constant. Then if we sum the last element of each row plus the last element on the original sequence of numbers we can obtain the next element on the sequence. So in the example, from the summation 1+3+7+15+31 we obtain 57 that correspond to the next value on the sequence.   
From the successive differences table we obtain the following recurrence relation



    [   a_n+4 = a_n+3 +(a_n+3-a_n+2)+((a_n+3-a_n+2)-(a_n+2-a_n+1))+; (((a_n+3-a_n+2)-(a_n+2-a_n+1))-((a_n+2-a_n+1)-(a_n+1-a_n)))+1 ]



The expression <ref> is the desired fourth degree recurrence relationship.




Simplifying and reordering the terms of the equation <ref> we get the next expression

    a_n+4-4 a_n+3 + 6 a_n+2 - 4 a_n+1 + a_n = 1


adding the inicial conditions to <ref> we get the following difference equation


    a_n+4-4 a_n+3 + 6 a_n+2 - 4 a_n+1 + a_n = 1,      a_0=1,a_1=2,a_2=4,a_3=8


Once we have obtained the difference equation <ref> we can solve it by many existing methods <cit.>,<cit.>. The purpose of solving <ref> is to releat it with the deduction of the Leo Moser's formula of the number of regions formed by the division of the circle by chords. In what follows I will do it in two different ways

  
  * By solving <ref> by the generating functions method
  
  * By solving <ref> by the solution of non-homogeneous linear with constant coefficients difference equation method.


To formalize these results I will state them as the following theorems.


Let n the subindex of the recurrence <ref>, m the number of points on the circle and f(m) the number of regions formed by the division of the circle by chords. Let n=m-1. If we solve <ref> by the generating functions method the number of regions formed by the division of the circle by chords
is

    f(m) = m^4-6m^3+23m^2-18m+24/24


 

From <ref> we have <ref>.
The application of equation <ref> for different values of n gives the following results



    [                               (n=0) a_4-4 a_3 + 6 a_2 - 4 a_1 + a_0 = 1;                               (n=1) a_5-4 a_4 + 6 a_3 - 4 a_2 + a_1 = 1;                               (n=2) a_6-4 a_5 + 6 a_4 - 4 a_3 + a_2 = 1;                               (n=3) a_7-4 a_6 + 6 a_5 - 4 a_4 + a_3 = 1;                                   ⋮                                   ⋮ ]


If we multiply <ref> by x^0 the first row, the second row by x^1, the third row by x^2, the fourth row by x^3 and so on we get



    [                                                      (n=0)  a_4 x^0-4 a_3 x^0 + 6 a_2 x^0 - 4 a_1 x^0 + a_0 x^0 = x^0;                                                      (n=1)  a_5 x^1-4 a_4 x^1 + 6 a_3 x^1 - 4 a_2 x^1 + a_1 x^1 = x^1;                                                      (n=2) a_6 x^2-4 a_5 x^2 + 6 a_4 x^2 - 4 a_3 x^2 + a_2 x^2 =  x^2;                                                      (n=3)  a_7 x^3-4 a_6 x^3 + 6 a_5 x^3 - 4 a_4 x^3 + a_3 x^3 = x^3;                                                          ⋮                                                          ⋮ ]



Summing up the rows of <ref> we obtain



    ∑_n=0^∞a_n+4 x^n - 4 ∑_n=0^∞a_n+3 x^n + 6 ∑_n=0^∞a_n+2 x^n - 4 ∑_n=0^∞a_n+1 x^n + ∑_n=0^∞a_n x^n = ∑_n=0^∞ x^n
 

 
Trying to equate the subindex of the coeficientes and the powers of the variables we rewrite <ref> as



    [ x^-4∑_n=0^∞a_n+4 x^n+4 - 4 x^-3∑_n=0^∞a_n+3 x^n+3 + 6 x^-2∑_n=0^∞a_n+2 x^n+2;                    - 4 x^-1∑_n=0^∞a_n+1 x^n+1 + ∑_n=0^∞a_n x^n = ∑_n=0^∞ x^n ]
 


The generating function is defined as 



    f(x)=∑_n=0^∞a_n x^n



Before trying to put equation <ref> in terms of <ref> it should be noticed that the righthand side of equation <ref> is the generating function of the geometrical series whose corresponding succesion is 1,1,1,1,…. If we multiply each side of equation <ref> by x^4 we obtain



    [ ∑_n=0^∞a_n+4 x^n+4 - 4 x ∑_n=0^∞a_n+3 x^n+3 + 6 x^2∑_n=0^∞a_n+2 x^n+2;        - 4 x^3∑_n=0^∞a_n+1 x^n+1 + x^4∑_n=0^∞a_n x^n = x^4∑_n=0^∞ x^n ]
 


It can be noticed that by this operation the righthand side of <ref> correspond to a right shift of the corresponding succession what gives as result the cancelation of the four first places of this succession and the result is the succession 0,0,0,0,1,1,1,1,…. Rewriting <ref> in terms of the generating function <ref> we get



    [  (f(x)-a_0-a_1x-a_2x^2-a_3x^3)-4x(f(x)-a_0-a_1x-a_2x^2); +6x^2(f(x)-a_0-a_1x)-4x^3(f(x)-a_0) + x^4f(x)=x^4/(1-x) ]



Replacing the a_0=1,a_1=2 and a_2=4,a_3=8 <ref> we get



    [          (f(x)-1-2x-4x^2-8x^3)-4x(f(x)-1-2x-4x^2); +6x^2(f(x)-1-2x)-4x^3(f(x)-1) + x^4f(x)=x^4/(1-x) ]



By algebraic simplification and factorization of <ref> we obtain



    f(x)(1-x)^4+(-1+2x-2x^2)=x^4/(1-x)
 


From <ref> we can obtain f(x) 



    f(x)=x^4/(1-x)^5+1/(1-x)^4-2x/(1-x)^4+2x^2/(1-x)^4


 
By partial fraction decomposition <cit.> <cit.> we have that



    x^4/(1-x)^5=1/(1-x)-4/(1-x)^2+6/(1-x)^3-4/(1-x)^4+1/(1-x)^5




    -2x/(1-x)^4=2/(1-x)^3-2/(1-x)^4




    -2x^2/(1-x)^4=2/(1-x)^2-4/(1-x)^3+2/(1-x)^4

Substituing <ref>,<ref> and <ref> in <ref> we get


    f(x)=1/(1-x)^5-3/(1-x)^4+4/(1-x)^3-2/(1-x)^2+1/(1-x)



From the generating functions theory it is known that <cit.> <cit.>



    [          1/(1-x)^r=-r0+-r1(-x)+-r2(-x)^2+…; =∑_i=0^∞-rix^i=1+(-1)r+1-11+(-1)^2r+2-12+…;                          =∑_i=0^∞r+i-1ix^i ]



Taking into account <ref> and using it in the equation <ref> we can calculate the n-th coeficient of each term and obtain



    f(n)=n+4n- 3 n+3n + 4 n+2n - 2 n+1n + nn



We calculate the polynomials in n from the terms of equation <ref>



    nn=1




    n+1n=(n+1)n!/n!(n+1-n)!=n+1




    n+2n=(n+2)(n+1)n!/n!(n+2-n)!=n^2+3n+1/2




    n+3n=(n+3)(n+2)(n+1)n!/n!(n+3-n)!=n^3+6n^2+11n+6/6




    n+4n=(n+4)(n+3)(n+2)(n+1)n!/n!(n+4-n)!=n^4+10n^3+35n^2+50n+24/24



Replacing <ref>,<ref>,<ref>,<ref> and <ref> in equation <ref> and simplifying we obtain



    f(n)=n^4-2n^3+11n^2+14n-48/24



Recalling that the number of regions m formed in the circle is related with n by n=m-1 as well as the fact that for setting the recurrence we have introduced a right shift of four places in <ref> we replace n by m-1 in <ref> and add 3 to this new expression for the recuperation of the terms that we have missed because of this right shift in the succession we get

    f(m)=m^4-6m^3+23m^2-18m+24/24


That is the desired result.






Let n the subindex of the recurrence <ref>, m the number of points on the circle and f(m) the number of regions formed by the division of the circle by chords. Let n=m-1. If we solve <ref> by the solution of linear non-homogeneous with constant coeficients method the number of regions formed by the division of the circle by chords
is

    f(m) = m^4-6m^3+23m^2-18m+24/24


 

From <ref> we have <ref> .
From the discrete mathematics methods, it is known that the general solution of equation like <ref> consist of two parts, the solution of the associated  homogeneous equation and a particular solution of <ref> that is <cit.> <cit.>
 

    a^g_n=a^p_n + a^h_n


where the superscript g means general, p means particular and h means homogeneous solutions respectively.
The form of the linear non-homogeneus is


    a_n+4-4 a_n+3 + 6 a_n+2 - 4 a_n+1 + a_n = f(n)


where f(n)=1. Then our non homogeneus equation with the corresponding four initial conditions will be


    a_n+4-4 a_n+3 + 6 a_n+2 - 4 a_n+1 + a_n = 1,   a_0=1,a_1=2,a_3=4,a_4=8


Let me start with the particular solution.
As will be shown later, when the homogeneous solution is obtained, the characteristic polynomial have as root r=1 with multiplicity four. It means that, in order to have the corresponding 
four linearly independent solutions for the homogeneous associateed equations we will have a polynomial function of third degree as solution <cit.>. In order to have a particular solution beeing linearly independent from the associated homogeneus solution, the form of the particular solution will be a^p_n= An^4 for A constant. Replacing such solution in <ref> we get


    An^4-4A(n-1)^4+6A(n-2)^4-4A(n-3)^4+A(n-4)^4=1


algebraically developing the fourth degree binomials in <ref> we obtain


    [     A(n^4-4(n^4-4n^3+6n^2-4n+1)+6(n^4-8n^3+24n^2-32n+16); -4(n^4-12n^3+54n^2-108n+1)+(n^4-16n^3+96n^2-256n+256))=1 ]
   
 

Simplifying <ref> we get the value

    A=1/24


and from <ref> we subtitute this value in the particular solution and obtain 


    a^p_n= n^4/24


The associated homogenous equation is


    a_n+4-4 a_n+3 + 6 a_n+2 - 4 a_n+1 + a_n = 0,   a_0=1,a_1=2,a_3=4,a_4=8


It is known from the discrete mathematics metodology <cit.> <cit.> for solving homogeneous recurrence as <ref> that their solutions have the form


    a^h_n=Cr^n


Applying <ref> to <ref> it is obtained


    Cr^n+4-4Cr^n+3+6Cr^n+2-4Cr^n+1+4Cr^n=0


Dividing each member of <ref> by Cr^n we obtain the following characteristic polynomial


    r^4-4r^3+6r^2-4r+4=0


By factorization of <ref> we get


    (r-1)^4=0


Then the roots of <ref> are r=1 with multiplicity of four. In order to have four linearly independent homogeneous solutions the homogeneous solution will have the next form


    a^h_n=C_11^n+C_2n1^n+C_3n^21^n+C_4n^31^n=C_1+C_2n+C_3n^2+C_4n^3
 

Where C_1,C_2,C_3 and C_4 are constants that can be determined by the application of the
initial conditions a_0=1,a_1=2,a_3=4 and a_4=8. From <ref> we know that a^g_n=a^p_n+a^h_n and the we can establis the following relation


    a^g_n=a^h_n+a^p_n=C_1+C_2n+C_3n^2+C_4n^3+n^4/24
 

By application of the initial conditions to <ref> we establish the following relations

    [ a_0=C_1+C_2(0)+C_3(0)^2+C_4(0)^3+(0)^4/24=1; a_1=C_1+C_2(1)+C_3(1)^2+C_4(1)^3+(1)^4/24=2; a_2=C_1+C_2(2)+C_3(2)^2+C_4(2)^3+(2)^4/24=4; a_3=C_1+C_2(3)+C_3(3)^2+C_4(3)^3+(3)^4/24=8 ]


From the relations <ref> we establish the following linear relations


    [                 C_1=1;     C_2+C_3+C_4=23/24;  2C_2+4C_3+8C_4=56/24; 3C_2+9C_3+27C_4=87/24 ]


For obtaining the values of C_2,C_3 and C_4 we solve the following linear system


    ( [  1  1  1;  2  4  8;  3  9 27;    ])
    (
    [ C_2; C_3; C_4 ])
    =
    (
    [ 23/24; 56/24; 87/24 ])


Solving the linear system <ref> we obtain


    [ C_2=14/24; C_3=11/24; C_4=-2/24 ]


Replacing the values obtained in <ref> we get the following expression


    a^g_n=1+14/24n+11/24n^2-2/24n^3+n^4/24


We know that the relation between the number m of points in the circle from where the chords are traced, and
n is n=m-1 so we can express <ref> in terms of m as follows


    a^g_n=1+14/24(m-1)+11/24(m-1)^2-2/24(m-1)^3+(m-1)^4/24


Algebraically developing each term of <ref> we get


    [         a^g_n=1+14/24m-14/24+11/24(m^2-2m+1); -2/24(m^3-3m^2+3m-1)+(m^4-4m^3+6m^2-4m+1)/24 ]


Simplifying <ref> we finally obtain


    a^g_n=24-18m+23m^2-6m^3+m^4/24


Reversing the order of the numerator terms we finally obtain the desired result


    f(m)=m^4-6m^3+23m^2-18m+24/24








§ CONCLUSIONS


In this article, I proposed a deduction of the Leo Moser's known formula for counting the number of regions that are formed by dividing the circle by chords, by solving a fourth order difference equation obtained by the successive differences method. I solved this recurrence equation by two different methods. This article illustrate how a classical problem can lead to different and creative developments. That is what makes mathematics so exciting.  





1












Grimaldi1
Ralph P. Grimaldi: Discrete and Combinatorial Mathematics: An applied introduction
Addison-Wesley, 3th Ed. (1994), .

Jobbings1
Andrew Jobbings: A selection of mathematical articles and notes by Andrew Jobbings.
,http://www.arbelos.co.uk/Papers/Chords-regions.pdf,27 December (2008)

Maier1
Eugene Maier: Counting Pizza Pieces and Other Combinatorial Problems.
Mathematics Teacher, 81 (1988), 22–26.

Moser1
Leo Moser and W. Bruce Ross: Mathematical Miscellany.
Mathematics Magazine, 23 (1949), 109–114.

Sedgewick1
Robert Segdewick and Philippe Flajolet: Introduction to the Analysis of Algorithms.
Addison-Wesley, 2nd Printing (2001), .


