# Number of circles in configuration

Consider the $n^2$ lattice points $(i, j)$, where $1 \leq i, j \leq n$.

Let the number of circles that pass through at least 3 points of this set be $C(n)$. What is a good way to count this? Is there a good way to count this? Trivially, there are at most ${n \choose 3}$ such circles. Note that as $n$ gets large, you can have several points that lie on the same circle.

I'm tempted to set up a recurrence relation. By considering the lower left and upper right $n-1$ by $n-1$ square, we can show $C(n) = 2 C(n-1) - C(n-2) +$ some weird additional terms.

Edit: I believe $C(3) = 34$. 14 of the circles contain 4 points, and 20 contain 3 points. 8 sets of 3 points form a line, for a total of $14 \times 4 + 20 + 8 = 84 = { 9 \choose 3 }$ set of 3 points which can form a circle.

Edit: It was slightly surprising when I first found out that $(1, 1), (2,1), (3, 2), (3, 3)$ lie on the same circle. (This follows by symmetry, with center of circle $( 1.5, 2.5)$ ).

I do not know how to approach $C(4)$

-
It may be easier to do the induction if you look at $n\times m$ rectangles. –  Thomas Andrews Jan 9 '13 at 8:26
@ThomasAndrews Yes, that was my next thought. The recurrence seems really ugly though, since there isn't much control over it. You do not know if any of the induction step circles also pass through your new points. The $2 \times 3$ to $3 \times 3$ case illustrates this. –  Calvin Lin Jan 9 '13 at 8:27
The first $20$ terms, starting with $n=1$, are $0$, $1$, $34$, $223$, $997$, $3402$, $9141$, $21665$, $46390$, $90874$, $167539$, $293443$, $487082$, $781537$, $1209469$, $1816528$, $2661113$, $3822203$, $5369662$, $7420495$. This sequence is not in OEIS yet (I'll be entering it). The ratio to $\binom{n^2}3$ seems to be steadily increasing towards $1$; at $N=20$ it's about $0.7$. Here's the code for generating those numbers. –  joriki Jan 9 '13 at 14:29
I verified joriki's numbers up to 9141 with code from [Three Points Determine a Circle][1] and SortBy[Drop[Union[threepoint[#] & /@ Subsets[Tuples[Range[7], {2}], {3}]], 1], N[Last[#]] &] -- another sequence begins 1, 7, 19, 48, 112, 212 -- number of distinct radii. [1]: demonstrations.wolfram.com/ThreePointsDetermineACircle –  Ed Pegg Jan 9 '13 at 16:01
@Ed: The mini markdown code for links is [Three Points Determine a Circle](http://...). –  joriki Jan 9 '13 at 16:02