A337747 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

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

LINKS

Table of n, a(n) for n=1..12.

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.

EXAMPLE

See examples in links.

CROSSREFS

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

Sequence in context: A232485 A232486 A077152 * A067759 A331068 A310122

Adjacent sequences: A337744 A337745 A337746 * A337748 A337749 A337750