A291066 Number of edges in the n-Menger sponge graph.

24, 672, 14976, 311808, 6334464, 127475712, 2555805696, 51166445568, 1023731564544, 20477852516352, 409582820130816, 8191862561046528, 163838900488372224, 3276791203906977792, 65535929631255822336, 1310719437050046578688, 26214395496400372629504, 524287963971202981036032

Offset: 1

Author

Eric W. Weisstein, Aug 17 2017

Keywords

• nonn
• easy

Comments

Also the number of maximal and maximum cliques in the n-Menger sponge graph. - Eric W. Weisstein, Dec 01 2017

This is the "inside surface area" of the level n Menger sponge, that is, the number of unit square faces that are on the exterior, but not on the convex hull of the Menger sponge. - Allan Bickle, Nov 28 2022

Examples

			The level 1 Menger sponge graph can be formed by subdividing every edge of a cube graph.  This produces a graph with 24 edges, so a(1) = 24.
		

Links

• Allan Bickle, Degrees of Menger and Sierpinski Graphs, Congr. Num. 227 (2016) 197-208.
• Allan Bickle, MegaMenger Graphs, The College Mathematics Journal, 49 1 (2018) 20-26.
• Eric Weisstein's World of Mathematics, Edge Count
• Eric Weisstein's World of Mathematics, Maximal Clique
• Eric Weisstein's World of Mathematics, Maximum Clique
• Eric Weisstein's World of Mathematics, Menger Sponge Graph
• Index entries for linear recurrences with constant coefficients, signature (28, -160).

Crossrefs

Cf. A009964 (vertex count).

Cf. A291066, A083233, and A332705 on the surface area of the n-Menger sponge graph.

Programs

Mathematica

Table[2^(2 n + 1) (5^n - 2^n), {n, 20}]
LinearRecurrence[{28, -160}, {24, 672}, 20]
CoefficientList[Series[24/(1 - 28 x + 160 x^2), {x, 0, 20}], x]

PARI

a(n)=2*(20^n-8^n) \\ Charles R Greathouse IV, Nov 29 2022

Python

def A291066(n): return (5**n-(1<Chai Wah Wu, Nov 27 2023

Formula

a(n) = 2^(2*n + 1)*(5^n - 2^n).

a(n) = 28*a(n-1) - 160*a(n-2).

G.f.: (24 x)/(1 - 28 x + 160 x^2).

a(n) = 2 * (20^n - 8^n). - Allan Bickle, Nov 28 2022

a(n) = 20*a(n-1) + 24*8^(n-1). - Allan Bickle, Nov 28 2022

a(n) = A332705(n) - A083233(n+1). - Allan Bickle, Nov 28 2022