an interesting new sequence!

[Richard Guy]

Apologies for anything repetitious, but
perhaps more needs to be said and some
further clarifications made.

In what follows we have  n  lines in the
Euclidean plane, and, for fairly obvious
reasons, we will assume that no two are
parallel and that no three go through the
same point.

A naive question is:  how many triangles?
The answer is   binom{n}{3}.  How is
it that when I searched OEIS (with
0 0 1 4 10 20 35 ) it only came up with
A101552 ??

But here we're interested in REGIONS.

The  n  lines each intersect the others
in  n-1  points, cutting each into  n
segments, two of which are infinite and
n-2  of which are finite.  There are
2n  infinite regions.  The  n(n-2)
finite segments connect pairs of the
binom{n}{2}  points of intersection
and Euler tells us that there are

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

finite regions.

There are several questions that one
may ask, and several possible resulting 
sequences.  Perhaps they're already all
in OEIS.

How many essentially (combinatorially,
topologically) different configurations
are there?  This is a vague question,
for which I suggest several different
answers, each leading to a different (?)
sequence:

1.  Two configurations may be considered
equivalent if it is possible to get from
one to the other by translation, rotation
(and reflexion?) and by any motion of an
individual line which doesn't cause it to
pass through the intersection of two
other lines.

2.  Two configurations may be considered
to be equivalent if the  n  partitions of
(n-1)(n-2)/2  of the points of intersection
into two parts (one on either side of the
line, which itself contains  n-1  of the
points) by each of the  n  lines, are the
same for each configuration.

3.  As 2., but with the same cyclic order.
(again, counting reverse cyclic order as
equivalent may give a different result).

4.  Two configurations may be considered
as equivalent if the they have the same
numbers of triangular, quadrangular,
pentangular, ... regions.

5.  As 4., but with the same arrangement.
This may be a loose way of saying 1.

The immediate question was: what is the maximum
possible number of triangular regions.  There
were some false starts, but I believe we
are agreed as far as

    (0)  0  0  1  2  5  7  10  ...

which, strangely, didn't come up when I
tried it on OEIS.

Note that each finite segment is the edge
of at most one triangle, so that an
upper bound is  floor{n(n-2)/3}.  This
is A32765, tho this formula doesn't appear
explicitly.  The formula under `Name:'
simplifies to the above with `+' in
place of `-'.  I believe that this bound
is attained only for  n = 2, 3, 4 and 5.

I must leave the other questions to those
with more patience & competence than I,
but I believe that the configurations are
``essentially unique'' for  n = 0, 1, 2,
3 and 4, and, for  n = 5, there seem to be
at least three different ones by each of
the criteria. For example, the 6 regions
can be 5 triangles & a pentagon;
        3 triangles & 3 quadrilaterals; or
   3 triangles, 2 quads & a pentagon.

The difference between the numbers of segments
in the last two comes about from the fact that
the outer boundary of the set of finite
regions may comprise  2n  segments, but it may
also be less (& is indeed so for  n = 3 and
4).   Let me know how you go  ...  R.

On Fri, 27 May 2005, Robert G. Wilson v wrote:

> Neil,
>
> 	He is only counting the smaller triangles. When you go to the 
> hyper-links you will see that there are other "super" triangles - triangles 
> made by two or more smaller triangles. a(5) would then equal 8 and a(6) 
> would then be 13.
>
> Bob.
>
> N. J. A. Sloane wrote:
>
>> This just came in - at first I rejected it,
>> thinking it was the same as A000124.  But it isn't!
>> 
>> Can it really be new?
>> 
>> NJAS
>> 
>> %I A107427
>> %S A107427 
>> 0,0,1,2,4,7,10,14,18,22,27,32,38,44,50,54,60,72,76,84,92,110,114,122,
>> %T A107427 130,156,160,210
>> %N A107427 Maximal number of triangles that can be formed by n straight 
>> lines in the Euclidian plane.
>> %C A107427 A000124 is a related sequence, but that sequence refers to 
>> regions whereas here we only consider triangles.
>> %H A107427 David Coles, <a href="http://davcoles.tripod.com">Triangle 
>> Puzzle</a>.
>> %H A107427 Jim Loy, <a 
>> href="http://www.jimloy.com/puzz/cole.htm">Triangle Puzzle</a>.
>> %e A107427 7 lines can make at most 10 triangles, so a(7) = 10.
>> %Y A107427 Cf. A000124.
>> %K A107427 nonn,nice,more,new
>> %O A107427 1,4
>> %A A107427 Bill Blewett (billble(AT)comcast.net), May 22 2005
>> 
>