%I #21 Sep 08 2022 08:45:24
%S 1,2,12,31,59,96,142,197,261,334,416,507,607,716,834,961,1097,1242,
%T 1396,1559,1731,1912,2102,2301,2509,2726,2952,3187,3431,3684,3946,
%U 4217,4497,4786,5084,5391,5707,6032,6366,6709,7061,7422,7792
%N Maximum number of regions defined by n zigzag-lines in the plane when a zigzag-line is defined as consisting of two parallel infinite half-lines joined by a straight line segment.
%C Note that the requirements imposed on the zigzag-line are neither the weakest nor the strongest imaginable. To relax the conditions, one might allow non-parallel half-lines. 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.
%D R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd Edition, p. 19, Addison-Wesley Publishing
%H Vincenzo Librandi, <a href="/A117625/b117625.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F Recurrence: a(n) = a(n-1) + 9*n - 8 Closed Form: a(n) = 4.5*n^2 - 3.5*n + 1
%F O.g.f: -(1-x+9*x^2)/(-1+x)^3 = -17/(-1+x)^2-9/(-1+x)^3-9/(-1+x) . - _R. J. Mathar_, Dec 05 2007
%F a(n) = (9*n^2-7*n+2)/2 = 3*a(n-1) -3*a(n-2) +a(n-3). - _Vincenzo Librandi_, Jul 08 2012
%e a(0)= 1 because the plane is one region.
%p seq((9*k^2-7*k+2)/2, k=0..42);
%t CoefficientList[Series[(1-x+9*x^2)/(1-x)^3,{x,0,50}],x] (* _Vincenzo Librandi_, Jul 08 2012 *)
%o (Magma) [(9*n^2-7*n+2)/2: n in [0..50]]; // _Vincenzo Librandi_, Jul 08 2012
%o (PARI) a(n)=n*(9*n-7)/2+1 \\ _Charles R Greathouse IV_, Jun 17 2017
%Y Cf. A000124.
%K easy,nonn
%O 0,2
%A Peter C. Heinig (algorithms(AT)gmx.de), Apr 08 2006