

A117625


Maximum number of regions defined by n zigzaglines in the plane when a zigzagline is defined as consisting of two parallel infinite halflines joined by a straight line segment.


4



1, 2, 12, 31, 59, 96, 142, 197, 261, 334, 416, 507, 607, 716, 834, 961, 1097, 1242, 1396, 1559, 1731, 1912, 2102, 2301, 2509, 2726, 2952, 3187, 3431, 3684, 3946, 4217, 4497, 4786, 5084, 5391, 5707, 6032, 6366, 6709, 7061, 7422, 7792
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Note that the requirements imposed on the zigzagline are neither the weakest nor the strongest imaginable. To relax the conditions, one might allow nonparallel halflines. To strengthen them, one might demand the connecting line segment to be perpendicular to both half lines but still allow an arbitrary length of it, or go even further and additionally demand that all line segments be of equal length. The two latter cases would lend the problem a metrical nature.


REFERENCES

R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd Edition, p. 19, AddisonWesley Publishing


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,3,1).


FORMULA

Recurrence: a(n) = a(n1) + 9*n  8 Closed Form: a(n) = 4.5*n^2  3.5*n + 1
O.g.f: (1x+9*x^2)/(1+x)^3 = 17/(1+x)^29/(1+x)^39/(1+x) .  R. J. Mathar, Dec 05 2007
a(n) = (9*n^27*n+2)/2 = 3*a(n1) 3*a(n2) +a(n3).  Vincenzo Librandi, Jul 08 2012


EXAMPLE

a(0)= 1 because the plane is one region.


MAPLE

seq((9*k^27*k+2)/2, k=0..42);


MATHEMATICA

CoefficientList[Series[(1x+9*x^2)/(1x)^3, {x, 0, 50}], x] (* Vincenzo Librandi, Jul 08 2012 *)


PROG

(MAGMA) [(9*n^27*n+2)/2: n in [0..50]]; // Vincenzo Librandi, Jul 08 2012


CROSSREFS

Cf. A000124.
Sequence in context: A116655 A085892 A101177 * A254962 A139323 A225525
Adjacent sequences: A117622 A117623 A117624 * A117626 A117627 A117628


KEYWORD

easy,nonn


AUTHOR

Peter C. Heinig (algorithms(AT)gmx.de), Apr 08 2006


STATUS

approved



