cp's OEIS Frontend

A077588 Maximum number of regions into which the plane is divided by n triangles.

%I A077588 #90 Jul 13 2025 17:49:53
%S A077588 1,2,8,20,38,62,92,128,170,218,272,332,398,470,548,632,722,818,920,
%T A077588 1028,1142,1262,1388,1520,1658,1802,1952,2108,2270,2438,2612,2792,
%U A077588 2978,3170,3368,3572,3782,3998,4220,4448,4682,4922,5168,5420,5678,5942,6212,6488
%N A077588 Maximum number of regions into which the plane is divided by n triangles.
%H A077588 Keyang Li, <a href="/A077588/a077588.svg">figures for n=1,2,3,4,5</a>
%H A077588 Luis Manuel Rivera, <a href="http://arxiv.org/abs/1406.3081">Integer sequences and k-commuting permutations</a>, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
%F A077588 a(n) = 3n^2 - 3n + 2 for n > 0.
%F A077588 Proof (from _Joshua Zucker_ and _N. J. A. Sloane_, Dec 01 2017)
%F A077588 Represent the configuration of n triangles by a planar graph with a node for each vertex of the triangles and for each intersection point. Let there be v_n nodes and e_n edges. By classical graph theory, a(n) = e_n - v_n + 2. When we go from n to n+1 triangles, each side of the new triangle can meet each side of the existing triangles at most twice, so Dv_n := v_{n+1}-v_n <= 6n.
%F A077588 Each of these intersection points increases the number of edges in the graph by 2, so De_n := e_{n+1}-e_n = 3 + 2*Dv_n, Da_n := a(n+1)-a(n) = 3 + Dv_n <= 3+6*n.
%F A077588 These upper bounds can be achieved by taking 3n points equally spaced around a circle and drawing n concentric overlapping equilateral triangles in the obvious way, and we achieve a(n) = 3n^2 - 3n + 2 (and v_n = 3n^2, e_n = 3n(2n-1)) for n>0. QED
%F A077588 a(n) is the nearest integer to (Sum_{k>=n} 1/k^2)/(Sum_{k>=n} 1/k^4). - _Benoit Cloitre_, Jun 12 2003
%F A077588 a(n) = a(n-1) + 6*n - 6 (with a(1) = 2). - _Vincenzo Librandi_, Dec 07 2010
%F A077588 For n > 0, a(n) = A002061(n-1) + A056220(n); and for n > 1, a(n) = A002061(n+1) + A056220(n-1). - _Bruce J. Nicholson_, Sep 22 2017
%e A077588 a(2) = 8 because a Star of David divides the plane into 8 regions: 6 triangles at the vertices, the interior hexagon, and the exterior.
%t A077588 CoefficientList[Series[(-z^3 - 5*z^2 + z - 1)/(z - 1)^3, {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jul 11 2011 *)
%Y A077588 Cf. A005448, A077591.
%Y A077588 a(n) = A096777(3*n-1) for n > 0. - _Reinhard Zumkeller_, Dec 29 2007
%Y A077588 For n > 0, a(n) = 2 * A005448(n). - _Jon Perry_, Apr 14 2013
%Y A077588 a(n) = A242658(n) for n > 0. - _Eric W. Weisstein_, Nov 29 2017
%K A077588 easy,nonn
%O A077588 0,2
%A A077588 _Joshua Zucker_ and the Castilleja School MathCounts club, Nov 07 2002