A367701 Number of degree 3 vertices in the n-Menger sponge graph.

8, 152, 2744, 49688, 941624, 18381464, 363917240, 7248334616, 144725667128, 2892582307736, 57836189374136, 1156600107729944, 23131012640050232, 462612336455034008, 9252183397644168632, 185043161299165038872, 3700859172747355380536, 74017151029040948253080

Offset

1,1

Comments

The level 0 Menger sponge graph is a single vertex. The level n Menger sponge graph is formed from 20 copies of level n-1 in the shape of a cube with middle faces removed by joining boundary vertices between adjacent copies.

Links

Table of n, a(n) for n=1..18.

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.

Index entries for linear recurrences with constant coefficients, signature (32,-275,724,-480).

Formula

a(n) = (24/85)*20^n + (6/5)*8^n - (432/85)*3^n + 8.

a(n) = 20*a(n-1) - (9/5)*8^n + (144/5)*3^n - 152.

a(n) = 20^n - A367700(n) - A367702(n) - A367706(n) - A367707(n).

3*a(n) = 2*A291066(n) - 2*A367700(n) - 4*A365602(n) - 5*A367706(n) - 6*A367707(n).

G.f.: 8*x*(1 - 13*x + 10*x^2 - 264*x^3)/((1 - x)*(1 - 3*x)*(1 - 8*x)*(1 - 20*x)). - Stefano Spezia, Nov 27 2023

Example

The level 1 Menger sponge graph is a cube with each edge subdivided, which has 12 degree 2 vertices and 8 degree 3 vertices.  Thus a(1) = 8.

Mathematica

LinearRecurrence[{32, -275, 724, -480}, {8, 152, 2744, 49688}, 25] (* Paolo Xausa, Nov 28 2023 *)

Prog

(Python)
def A367701(n): return ((3*5**n<<(n<<1)+3)+(51<<(3*n+1))-(3**(n+3)<<4))//85+8 # Chai Wah Wu, Nov 28 2023

Crossrefs

Cf. A009964 (number of vertices), A291066 (number of edges).

Cf. A359452, A359453 (numbers of corner and non-corner vertices).

Cf. A291066, A083233, A332705 (surface area).

Cf. A367700, A367701, A367702, A367706, A367707 (degrees 2 through 6).

Cf. A001018, A271939, A365606, A365607, A365608 (Sierpinski carpet graphs).

Sequence in context: A249481 A003491 A053606 * A221732 A249931 A123770

Adjacent sequences: A367698 A367699 A367700 * A367702 A367703 A367704

Keyword

nonn,easy

Author

Allan Bickle, Nov 27 2023

Status

approved