OFFSET
0,2
COMMENTS
See a comment on V-V and V-S at A249246.
There are a total of 16 combinations as shown in the table below:
+-------------------------------------------------------+
| Even n-th version V-V S-V V-S S-S |
+-------------------------------------------------------+
| Odd n-th version |
+-------------------------------------------------------+
Note: V-V = vertex to vertex, S-V = side to vertex,
V-S = vertex to side, S-S = side to side.
From Manfred Boergens, Sep 21 2021: (Start)
For finite sets of random points in the real plane with exactly n nearest neighbors, a(n) for n >= 2 is a lower bound for the maximal number of points. Conjecturally, a(n) equals this number.
The randomness provides for pairwise different distances with probability = 1.
A point A is called a nearest neighbor if there is a point B with smaller distance to A than to any other point C.
In graph theory terms: Let G be a finite simple digraph; the vertices of G are arbitrary placed points in R^2 with pairwise different distances; the edges of G are arrows joining each point (tail end) to its nearest neighbor (head end). If G contains exactly n nearest neighbors and b(n) is the maximal number of points in any such graph then a(n) is the best lower bound known as yet for b(n).
a(n) for n >= 2 can be seen as an "inverse" to A347941.
a(n) is built by constructing G with m points and n nearest neighbors, m chosen as maximal as possible, then defining a(n)=m. The start is a(2)=9 and a(3)=12. We call the pairs (m,n)=(9,2) and (m,n)=(12,3) "anchor pairs" and proceed to bigger n by combining graphs with these anchor pairs to bigger graphs. So the next anchor pairs are (18,4), (21,5) and (27,6).
We conjecture that a(n) is optimal. This claim is true if the following assumptions hold:
- The anchor pairs (9,2) and (12,3) are optimal.
- All bigger anchor pairs (m,n) are constructed by combining copies of (9,2) if n is even and adding one (12,3) if n is odd.
(End)
LINKS
Kival Ngaokrajang, Illustration of initial terms
Manfred Boergens, Next-neighbours
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
FORMULA
a(0)=1, a(1)=3; for n >= 2, a(n) = a(n-1) + 6, if mod(n,2) = 0, otherwise a(n) = a(n-1) + 3.
From Colin Barker, Sep 10 2015: (Start)
a(n) = (3*(-1+(-1)^n+6*n))/4.
a(n) = a(n-1)+a(n-2)-a(n-3) for n>3.
G.f.: (x^3+5*x^2+2*x+1) / ((x-1)^2*(x+1)).
(End)
a(n) = 3 * A032766(n) for n>=1. - Michel Marcus, Sep 13 2015
a(0)=1; for n >= 1, a(n) = 9n/2 for even n, a(n) = (9n-3)/2 for odd n. - Manfred Boergens, Sep 21 2021
EXAMPLE
If the graph G in the comment by Manfred Boergens has 5 nearest neighbors there are at most 21 vertices in G (conjectured; it is proved that there are G with 5 nearest neighbors and 21 vertices but it is not yet proved that 21 is the maximum). - Manfred Boergens, Sep 21 2021
MATHEMATICA
Join[{1}, Table[If[OddQ[n], (9 n - 3)/2, 9 n/2], {n, 1, 100}]] - Manfred Boergens, Sep 21 2021
PROG
(PARI) {a=3; print1("1, ", a, ", "); for(n=2, 100, if (Mod(n, 2)==0, a=a+6, a=a+3); print1(a, ", "))}
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kival Ngaokrajang, Sep 06 2015
STATUS
approved