A337747 Maximal number of 4-point circles passing through n points on a plane.

0, 0, 0, 1, 1, 3, 6, 12, 14, 22, 30, 45

Offset: 1

Author

Dmitry Kamenetsky, Sep 17 2020

Keywords

• nonn
• more
• nice

Comments

This is a variant of the orchard-planting problem that uses circles instead of straight lines.

The maximal number of 3-point circles passing through n points on a plane is binomial(n,3). Given an arrangement of n points in general position, any choice of three points defines a circle. - Peter Kagey, Oct 05 2020

Paul Panzer provides upper and lower bounds:

a(n) <= floor(n*(n-1)*(n-2)/24).

a(n) >= 2 + n*((n-2)*(n-2) + 4)/32 for n == 0 (mod 4) and n >= 8.

a(n) >= 2 + (n-1)*((n-1)*(n-5) + 16)/32 for n == 1 (mod 4) and n >= 9.

a(n) >= 2 + n*(n-2)*(n-2)/32 for n == 2 (mod 4) and n >= 10.

a(n) >= 2 + (n-1)*((n-3)*(n-3) + 16)/32 for n == 3 (mod 4) and n >= 11.

It seems that a(n) = n*((n-2)*(n-2) + 4)/32 + 2*A008610(n/2-4) if n == 0 (mod 4) and n >= 8. - Zhao Hui Du, Dec 14 2022

The number of 4-point circles passing through n points (2*cos(t_k), sin(t_k)) where t_k = (2k-1)*Pi/n, k=1,2,...,n is A008610(n-4), so A337747(n) >= A008610(n-4), so A337747(n) ~ n^3/24 for sufficiently large n. - Zhao Hui Du, Dec 15 2022

Examples

			See examples in links.
		

Links

• Zhao Hui Du, Source code and running data to show there are at most 30 circles for 11 trees.
• Zhao Hui Du, A group of solutions with 30 circles for 11 trees.
• Zhao Hui Du, Geogebra dynamic graph for a group of solution to 12 trees 45 circles (4 trees per circle).
• Zhao Hui Du, Best known solution for 14 trees (73 circles), removing point I from the solution to form a solution with 13 trees and 53 circles so that a(13) >= 53, a(14) >= 73.
• Zhao Hui Du, Graph for 14 trees 73 circles (all black circles have same patterns as that in that in two co-center regular polygons (Paul Panzer's solution) while red circles are those extra circles).
• Zhao Hui Du, Graph for 16 trees with 120 circles.
• Zhao Hui Du, Geogebra graph for 16 trees with 120 circles (parameter d and m could be any real value and point PP could be moving too), removing any tree to form 15 trees with 90 circles so that a[15]>=90, a[16]>=120.
• Zhao Hui Du, Chinese webpage to show that the number of 4 points circle through the n points in ellipse could be transformed to the number to pick 4 different numbers k1,k2,k3,k4 from 1 to n so that n|2+k1+k2+k3+k4, which is equal to A008610(n-4).
• Dmitry Kamenetsky, Best known solutions for n <= 13.
• Dmitry Kamenetsky, Orchard planting problem, Puzzling StackExchange, August 2020.
• Dmitry Kamenetsky, General orchard planting problem, Puzzling StackExchange, September 2020.

Crossrefs

Cf. A003035 (the original orchard problem), A006065.

Extensions

a(11) from Zhao Hui Du, Nov 22 2022

a(12) from Zhao Hui Du, Dec 01 2022