A077591 Maximum number of regions into which the plane can be divided using n (concave) quadrilaterals.

1, 2, 18, 50, 98, 162, 242, 338, 450, 578, 722, 882, 1058, 1250, 1458, 1682, 1922, 2178, 2450, 2738, 3042, 3362, 3698, 4050, 4418, 4802, 5202, 5618, 6050, 6498, 6962, 7442, 7938, 8450, 8978, 9522, 10082, 10658, 11250, 11858, 12482, 13122, 13778

Offset

0,2

Comments

Sequence found by reading the segment (1, 2) together with the line from 2, in the direction 2, 18, ..., in the square spiral whose vertices are the triangular numbers A000217. - Omar E. Pol, Sep 05 2011

For a(n) > 1, a(n) are the numbers such that phi(sum of the odd divisors of a(n)) = phi(sum of even divisors of a(n)). - Michel Lagneau, Sep 14 2011

Apart from first term, subsequence of A195605. - Bruno Berselli, Sep 21 2011

Engel expansion of 1F2(1; 1/2, 1/2; 1/8). - Benedict W. J. Irwin, Jun 21 2018

Let f(n) = 4*n^2 - 5, then (x, y, z) = (a(n+1), -f(n), -f(n + 1)) are solutions of the Diophantine equation x^3 + 4*y^3 + 4*z^3 = 512. - XU Pingya, Apr 25 2022

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..10000

Keyang Li, when n=3, maximum number of regions is 50

Keyang Li, when n=1, number of regions is 2; when n=2, maximum number of regions is 18

Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Formula

a(n) = 8*n^2 - 8*n + 2 = 2*(2*n-1)^2, n > 0, a(0)=1. [It would be nice to have a proof, or even a reference to a proof. - N. J. A. Sloane, Nov 30 2017]

Proof from Keyang Li, Jun 18 2022: (Start)

Represent the configuration of n concave quadrilaterals by a planar graph with a node for each vertex of the quadrilaterals and for each intersection point. Let there be v_n nodes and e_n edges. By Euler's formula for planar graphs, a(n) = e_n - v_n + 2. When we go from n to n+1 quadrilaterals, each side of the new quadrilateral can meet each side of the existing quadrilaterals at most 4 times, so Dv_n := v_{n+1} - v_n <= 4*4n = 16n.

Each of these intersection points increases the number of edges in the graph by 2, so De_n := e_{n+1} - e_n = 4 + 2*Dv_n, Da_n := a(n+1) - a(n) = 4 + Dv_n <= 4+16*n.

These upper bounds can be achieved by taking n interwoven concave quadrilaterals (for n=1,2,3 see the attached Keyang Li links), and we achieve a(n) = 8n^2 - 8n + 2 (and v_n = 8n^2 - 4n, e_n = 4n*(4n-3)) for n > 0. QED (End)

For n > 0: A071974(a(n)) = 2*n+1, A071975(a(n)) = 2. - Reinhard Zumkeller, Jul 10 2011

a(n) = 1 + A069129(n), if n >= 1. - Omar E. Pol, Sep 05 2011

a(n) = 2*A016754(n-1), if n >= 1. - Omar E. Pol, Sep 05 2011

G.f.: (1 - x + 15*x^2 + x^3)/(1-x)^3. - Colin Barker, Feb 23 2012

E.g.f.: (8*x^2 + 2)*exp(x) - 1. - G. C. Greubel, Jul 15 2017

From Amiram Eldar, Jan 29 2021: (Start)

Sum_{n>=1} 1/a(n) = Pi^2/16.

Sum_{n>=1} (-1)^(n+1)/a(n) = G/2, where G is Catalan constant (A006752).

Product_{n>=1} (1 + 1/a(n)) = cosh(Pi/sqrt(8)).

Product_{n>=1} (1 - 1/a(n)) = cos(Pi/sqrt(8)). (End)

Example

a(2) = 18 if you draw two concave quadrilaterals such that all four sides of one cross all four sides of the other.

Maple

A077591:=n->`if`(n=0, 1, 8*n^2 - 8*n + 2); seq(A077591(n), n=0..50); # Wesley Ivan Hurt, Mar 12 2014

Mathematica

Table[2*(4*n^2 - 4*n + 1), {n, 0, 50}] (* G. C. Greubel, Jul 15 2017 *)

Prog

(PARI) isok(n) = (sod = sumdiv(n, d, (d%2)*d)) && (sed = sumdiv(n, d, (1 - d%2)*d)) && (eulerphi(sod) == eulerphi(sed)); \\ from Michel Lagneau comment; Michel Marcus, Mar 15 2014
(GAP) Concatenation([1], List([1..2000], n->8*n^2 - 8*n + 2)); # Muniru A Asiru, Jan 29 2018

Crossrefs

Cf. A006752, A077588, A239186.

Cf. A071974, A071975.

Cf. A016754, A069129.

Sequence in context: A223469 A048910 A356712 * A050808 A058653 A058794

Adjacent sequences: A077588 A077589 A077590 * A077592 A077593 A077594

Keyword

nonn,easy

Author

Joshua Zucker and the Castilleja School MathCounts club, Nov 07 2002

Status

approved