cp's OEIS Frontend

A117625 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.

%I A117625 #36 May 20 2025 23:42:49
%S A117625 1,2,12,31,59,96,142,197,261,334,416,507,607,716,834,961,1097,1242,
%T A117625 1396,1559,1731,1912,2102,2301,2509,2726,2952,3187,3431,3684,3946,
%U A117625 4217,4497,4786,5084,5391,5707,6032,6366,6709,7061,7422,7792
%N A117625 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 A117625 Here is the sketched solution from Concrete Mathematics, second edition, p. 499. Consider n straight lines in general position in the plane. As shown in Section 1.2 of the book, this divides the plane into r(n) = n*(n+1)/2 + 1 regions, the maximum possible (cf. A000124). There are n*(n-1)/2 intersection points. Replace these n lines by extremely narrow zig-zags with segments sufficiently long that there are nine intersections between each pair of zigzags. Each of the n*(n-1)/2 intersection points now gives eight new regions. So a(n) = n*(n+1)/2 + 1 + 8*n*(n-1)/2 = 9*n^2/2 - 7*n/2 + 1. - _N. J. A. Sloane_, May 19 2025
%C A117625 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 A117625 R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd Edition, Chapter 1, Problem 13, pages 19 and 499, Addison-Wesley Publishing
%H A117625 Vincenzo Librandi, <a href="/A117625/b117625.txt">Table of n, a(n) for n = 0..1000</a>
%H A117625 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F A117625 Recurrence: a(n) = a(n-1) + 9*n - 8 for n > 0.
%F A117625 Closed Form: a(n) = 9*n^2/2 - 7*n/2 + 1.
%F A117625 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 A117625 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - _Vincenzo Librandi_, Jul 08 2012
%F A117625 E.g.f.: exp(x)*(2 + 2*x + 9*x^2)/2. - _Stefano Spezia_, May 20 2025
%e A117625 a(0)= 1 because the plane is one region.
%p A117625 seq((9*k^2-7*k+2)/2, k=0..42);
%t A117625 CoefficientList[Series[(1-x+9*x^2)/(1-x)^3,{x,0,50}],x] (* _Vincenzo Librandi_, Jul 08 2012 *)
%o A117625 (Magma) [(9*n^2-7*n+2)/2: n in [0..50]]; // _Vincenzo Librandi_, Jul 08 2012
%o A117625 (PARI) a(n)=n*(9*n-7)/2+1 \\ _Charles R Greathouse IV_, Jun 17 2017
%Y A117625 Cf. A000124.
%K A117625 easy,nonn
%O A117625 0,2
%A A117625 Peter C. Heinig (algorithms(AT)gmx.de), Apr 08 2006